Упражнения

Разминочные упражнения

1 Какова вероятность дублетов при распределении вероятностей из (8.3), когда один кубик правильный, а у другого центр масс смещен? Какова вероятность выбросить сумму ?

2 Какова вероятность того, что в случайно перетасованной колоде карт и верхняя и нижняя карты окажутся тузами? (Все 52! перестановок имеют вероятность

3 Студентов, изучавших конкретную математику в Станфорде в 1979 г., попросили подбрасывать монету до тех пор, пока дважды подряд не выпадет решка, и записать потребовавшееся число бросаний. В результате получилось:

Студентов, изучавших конкретную математику в Принстоне в 1987 г., попросили сделать то же, и они получили такие результаты:

Оцените математическое ожидание и дисперсию, основываясь (а) на Станфордских данных; на данных из Принстона.

4 Пусть где Докажите, что, по аналогии с (8.38) и (8.39),

если указанные производные существуют при

5 Пусть Алиса и Билл играют в игру (8.78), используя кривую монету, которая выпадает решкой вверх с вероятностью . Существует ли значение , для которого игра станет справедливой?

6 К чему сведется закон дисперсии для условных распределений (8.106), если случайные величины X и Y будут независимы.

Обязательные упражнения

7 Покажите, что если у обоих кубиков смещен центр масс, причем распределение вероятностей у них одинаковое, то вероятность дубля всегда будет не меньше

8 Пусть А и В — события, такие, что Докажите, что

9 Докажите или опровергните: если X и Y — независимые случайные величины, то таковыми являются также где — любые функции.

10 Сколько элементов, самое большее, могут являться медианами случайной величины X в соответствии с определением

11 Постройте случайную величину, имеющую конечное математическое ожидание и бесконечную дисперсию.

12 а Пусть — ПФСВ случайной величины X. Докажите, что

(Эти важные соотношения называются оценками хвоста.) В частном случае используйте первую оценку хвоста для доказательства того, что

13 Докажите, что если независимые случайные величины с одинаковым распределением, а — произвольное вещественное число, то

14 Пусть F(z) и G(z) - производящие функции случайных величин и пусть

где (Такая функция называется смесью соответствующая ей случайная величина получается, если подбросить монету и затем выбрать распределение или в зависимости от того, какой стороной вверх упадет монета.) Выразите математическое ожидание и дисперсию Н через и математическое ожидание и дисперсию

15 Если — производящие функции случайных величин, то можно определить новую ПФСВ при помощи их „композиции":

Выразите через (Уравнение (8.93) будет тогда частным случаем.)

16 Найдите замкнутую форму для суперпроизводящей функции где футбольная производящая функция, определенная в (8.53).

17 Пусть имеют, соответственно, биномиальное и отрицательное биномиальное распределения с параметрами (Эти распределения определены в (8.57) и Докажите, что Какое тождество для биномиальных коэффициентов отсюда вытекает?

18 Говорят, что случайная величина X имеет распределение Пуассона с параметром если для всех .

а Какова производящая функция такой случайной величины?

b Чему равны ее математическое ожидание, дисперсия и остальные кумулянты?

19 Продолжая предыдущее упражнение, допустим, что случайная величина X] имеет распределение Пуассона с параметром а случайная величина независима от X] и имеет распределение Пуассона с параметром

а Какова вероятность того, что Чему равны среднее, дисперсия и другие кумулянты случайной величины

20 Докажите (8.74) и (8.75) — общие формулы для математического ожидания и дисперсии времени до появления заданной последовательности решек и орлов.

21 Что выражает значение если в (8.77) положить оба символа Р и 0 равными

22 Докажите закон условного математического ожидания и дисперсии.

Домашние задания

23 Пусть Ргоо распределение вероятностей двух правильных кубиков, а — распределение вероятностей двух неуравновешенных кубиков, определенное в (8.2). Найдите все такие события А, что . Какие из этих событий зависят только от случайной величины (Вероятностное пространство с включает 236 событий; лишь 211 из них зависят только от

24 Игрок бросает правильных кубиков и убирает кубики, на которых выпало Затем игрок К называет число от 1 до 6, бросает оставшиеся кубики и убирает те, на которых выпало названное число очков. Этот процесс повторяется до тех пор, пока в игре не останется ни одного кубика. Выигрывает игрок, убравший в совокупности большее число кубиков (т. е. или больше).

а Чему равно математическое ожидание и дисперсия общего числа кубиков, убранных игроком Указание: кубики независимы.

b С какой вероятностью выигрывает в случае

25 Рассмотрим следующую азартную игру. Вы ставите определенную сумму А и бросаете правильный кубик. Если выпало к очков, то ваша ставка умножается на (В частности, ставка удваивается, если выпадет но вы проигрываете

все, если выпадет ) В любой момент вы можете остановиться и потребовать текущую сумму ставки. Чему равно среднее значение и дисперсия суммы ставки после бросаний? (Пренебрегите эффектами округления суммы до целого числа.)

26 Найдите математическое ожидание и дисперсию числа циклов длины в случайной перестановке элементов. (Задача о победе футбольной команды, ответ на которую дан в (8.23), (8.24) и (8.53), есть частный случай

27 Пусть X], — независимые значения случайной величины X. Уравнения (8.19) и (8.20) говорят, как оценить математическое ожидание и дисперсию X по результатам этих наблюдений. Дайте аналогичную формулу для оценки третьего кумулянта (Ваша формула должна давать „несмещенную" оценку в том смысле, что ожидаемое значение оценки должно равняться

28 Какова средняя продолжительность игры в монету (8.78), а при условии, что выигрывает Алиса?

b при условии, что выигрывает Билл?

29 Алиса, Билл и Компьютер бросают правильную монету до тех пор, пока не появится одна из следующих последовательностей: (Если в игре участвуют только две из этих последовательностей, то, как мы знаем из (8.82), А, вероятно, выиграет у В, В, вероятно, выиграет , вероятно, выиграет у А; но в данной игре участвуют сразу все три последовательности.) Каковы шансы каждого игрока на выигрыш?

30 Мы рассматривали три вида дисперсии, связанные с успешным поиском в хеш-таблице. В действительности есть еще два вида: мы можем рассмотреть среднее (по к) дисперсий (по числа проб , а также дисперсию (по к) средних (по Вычислите эти величины.

31 В вершине А пятиугольника находится яблоко, а на расстоянии двух ребер, в вершине С, находится червяк. Каждый день червяк переползает в одну из двух соседних вершин с равной вероятностью. Так, через один день червяк окажется в вершине В с вероятностью вершине с вероятностью По прошествии двух дней червяк может вновь оказаться в С, поскольку он не запоминает предыдущих положений. Достигнув вершины А, червяк останавливается пообедать.

а Чему равны математическое ожидание и дисперсия числа дней, прошедших до обеда?

b Какую оценку дает неравенство Чебышёва для вероятности того, что это число дней будет 100 или больше? с Что позволяет сказать о величине оценка хвоста (упр. 12)?

32 Алиса и Билл находятся в войсковых частях, дислоцированных в одном из пяти штатов: Канзас, Небраска, Миссури, Оклахома и Колорадо. Первоначально Алиса находится в Небраске, а Билл — в Оклахоме. Каждый месяц каждого из них переводят в соседний штат, причем любой из соседних штатов выбирается с равной вероятностью. (Ниже нарисована диаграмма соседства:

Начальные штаты обведены кружком.) Например, Алиса через один месяц будет переведена с вероятностью 1/3 в любой из штатов Колорадо, Канзас или Миссури. Найдите математическое ожидание и дисперсию числа месяцев, которое потребуется Алисе и Биллу, чтобы встретить друг друга. (Возможно, вы захотите прибегнуть к помощи компьютера.)

33 Независимы ли случайные величины из

34 Джина играет в гольф и на каждом ударе с вероятностью имеет „супер-шот“ и выигрывает один удар, с вероятностью имеет обычный и с вероятностью имеем „саб-шот“ который стоит ей одного удара в сравнении с расчетным числом ударов. (Для не играющих в гольф: На каждом круге она делает 2, 1 или 0 шагов к цели с вероятностями, соответственно, . В игре с -ударной лункой ее результат есть минимальное такое, что она продвигается на или больше шагов за кругов. Маленький результат лучше большого.)

а Покажите, что Джина выигрывает игру с четырехударной лункой чаще, чем проигрывает, когда она встречается с игроком, делающим всегда обычные удары. (Иными словами вероятность получения результата меньше четырех должна быть больше, чем вероятность результата больше четырех.)

b Покажите, что ее средний результат в игре с четырехударной лункой больше четырех. (Таким образом, она в среднем проигрывает „стабильному" игроку по общей сумме очков, хотя она в среднем выигрывает в матче с зачетом по лункам.)

Контрольные работы

35 Центр масс кубика смещен в соответствии с распределением вероятностей

Пусть означает сумму очков после -кратного бросания этого кубика. Найдите необходимые и достаточные условия на распределение вероятностей, чтобы две случайные величины были независимы друг от друга при всех

36 На шести гранях некоторого кубика вместо обычных высечены следующие метки:

а Покажите, что можно так расставить очки на шести гранях второго кубика, чтобы сумма очков при бросании этих двух кубиков имела бы то же самое распределение вероятностей, что и при бросании пары обычных кубиков. (Считайте, что все 36 комбинаций граней равновероятны.) Обобщая предыдущий пункт, найдите все способы расстановки очков на гранях кубиков, такие, что распределение суммы очков будет совпадать с распределением суммы очков обычных кубиков. (На каждой грани должно быть целое положительное число очков.)

37 Пусть обозначает вероятность того, что правильную монету придется бросить ровно раз, прежде чем два раза подряд встретится решка, и пусть Найдите замкнутое выражение для через числа Фибоначчи.

38 Чему равна производящая функция случайной величины для числа бросаний правильного кубика, требуемых для выпадания всех шести граней? Рассмотрите общий случай правильного кубика“ с гранями и дайте замкнутое выражение для числа бросаний, требуемых для появления I из граней. Чему равна вероятность, что потребуется ровно бросаний?

39 Производящая функция Дирихле случайной величины имеет вид

Таким образом, Пусть X — случайная величина с Выразите через и ее производные.

40 Для биномиального распределения кумулянт имеет вид где — многочлен степени т. (Например, поскольку математическое ожидание и дисперсия равны

а Найдите замкнутое выражение для коэффициента при

Докажите, что где число Бернулли.

41 Пусть случайная величина равняется числу бросаний правильной монеты до появления в совокупности решек. Покажите, что Используя методы гл. 9, оцените это значение с абсолютной погрешностью

42 Один человек испытывает трудности с устройством на работу. Если он является безработным утром любого дня, то с некоторой постоянной вероятностью (не зависящей от прошедших событий) он нанимается на работу в течение дня; но если он имеет работу в начале дня, то с постоянной вероятностью его уволят к вечеру. Найдите среднее число вечеров, когда его ожидает работа на следующий день в предположении, что первоначально он принят на работу и что этот процесс продолжается дней. (Если, например, то ответ равен

43 Найдите замкнутое выражение для ПФСВ , где есть вероятность того, что случайная перестановка объектов имеет ровно циклов. Чему равны математическое ожидание и стандартное отклонение числа циклов?

44 Атлетический клуб проводит среди своих членов турнир по теннису с выбыванием. В турнире участвуют игроков. В первом круге игроки случайным образом разбиваются на пары, так что любое разбиение равновероятно, и играется матчей. Победители переходят на следующий круг, где с помощью такого же процесса выявляется победителей. И так далее; в круге играется случайно выбираемых матчей между до сих пор не побежденными участниками. В круге определяется чемпион. Хотя устроителям турнира об этом неизвестно, все игроки в действительности упорядочены по силе игры, так что играет лучше всех, — лучше всех, кроме играет хуже всех. Когда игрок играет с то с вероятностью побеждает и с вероятностью побеждает причем результат их игры не зависит от исходов других встреч. Мы считаем, что для всех и к имеется одна и та же вероятность .

а С какой вероятностью игрок выиграет турнир?

b С какой вероятностью в круге (финальной встрече) будут участвовать два лучших игрока, и с С какой вероятностью в от конца круге (-финале) будут соревноваться лучших игроков? (Предыдущие вопросы — это частные случаи Пусть обозначает число существенно различных результатов турнира; два турнира считаются по-существу совпадающими, если в них все матчи играются между теми же игроками и победители одни и те же. Докажите, что

С какой вероятностью выиграет турнир?

f Докажите, что если то вероятность выигрыша

турнира игроком строго больше, чем игроком при

45 Настоящее шерри производят в Испании в строгом соответствии с многостадийной системой, называемое „Солера" Для простоты мы будем считать, что у винодела имеется всего три бочки, А, В и С. Каждый год третья часть вина из бочки С разливается в бутылки и замещается вином из В; затем бочку В дополняют, переливая в нее третью часть вина из А; наконец, бочку А доливают доверху новым вином. Пусть — ПФСВ, в которых коэффициентом при служит доля вина выдержки лет в соответствующей бочке сразу же после переливаний.

а Пусть описанные операции выполняются с незапамятных времен, так что мы достигли установившегося состояния, в котором одни и те же в начале каждого года. Найдите замкнутое выражение для этих производящих функций.

b При тех же условиях найдите математическое ожидание и стандартное отклонение возраста вина в каждой бочке. Каков средний возраст вина, разливаемого в бутылки? Какая доля вина имеет возраст ровно 25 лет? с Теперь примите во внимание конечность времени. Пусть во все три бочки в начале нулевого года залили новое вино. Каким будет средний возраст вина, разливаемого в начале года

46 Стефан Банах имел обыкновение носить с собой две коробки спичек; в каждой из коробок первоначально находилось по спичек. Когда ему был нужен огонь, он выбирал одну из коробок случайным образом, с вероятностью независимо от предыдущего выбора. Взяв спичку, он клал коробку обратно в карман (даже если в ней не оставалось ни одной спички — так поступают все великие математики). Если выбранная коробка оказывалась пустой, Банах выбрасывал ее и доставал другую, а Однажды он обнаружил, что и вторая коробка пуста. Какова вероятность такого события? (При это происходит в половине случаев, а при — с вероятностью Для ответа на этот вопрос найдите замкнутое выражение производящей функции где есть вероятность, начав с спичек в одной коробке и — в другой, получить обе пустые коробки, когда впервые выбирается пустая коробка. Затем найдите замкнутое выражение для

Обобщая ваш ответ в , найдите замкнутое выражение для вероятности того, что в момент выбрасывания первой пустой коробки в другой будет ровно к спичек, с Найдите замкнутое выражение для среднего числа спичек в этой другой коробке.

47 Несколько физиологов в сотрудничестве с несколькими физиками открыли недавно две разновидности микробов, для которых характерен очень странный способ размножения. Мужской микроб, называемый дифагом, имеет на своей поверхности два рецептора; женский микроб, трифаг, имеет три рецептора:

Когда культуру дифагов и трифагов облучают пси-частицами, то каждая частица поглощается ровно в одном рецепторе одного из фагов; при этом все рецепторы равновероятны. Если частица попадает в рецептор дифага, то этот дифаг превращается в трифаг; если же частица попадает в рецептор трифага, то трифаг делится на два дифага. Так, если в начале эксперимента имеется один дифаг, то первая пси-частица вызовет его превращение в трифаг, вторая частица разделит трифаг на два дифага и третья частица превратит одного из дифагов в трифаг. Четвертая частица попадет либо в дифаг, либо в трифаг; в результате получается либо два трифага (с вероятностью либо три дифага (с вероятностью Найдите замкнутое выражение для среднего числа дифагов, если мы начали с одного дифага и облучили культуру раз одиночными пси-частицами.

Пять человек стоят в вершинах пятиугольника и бросают друг другу диски Фрисби (разновидность летающей тарелки).

У них имеется два диска, первоначально расположенные в соседних вершинах, как показано на рисунке. В очередной отрезок времени каждый диск бросают либо влево, либо вправо с одинаковой вероятностью. Этот процесс продолжается до тех пор, пока в одного человека не бросят сразу два диска одновременно, и в этом случае игра кончается. (Все броски не зависят от предыдущих.)

а Найдите математическое ожидание и дисперсию числа пар бросков.

b Найдите замкнутое выражение через числа Фибоначчи для вероятности того, что игра продлится более 100 шагов.

49 Люк Снегоход проводит зимний отпуск в своей горной хижине. На передней веранде хижины стоит пар ботинок, а на задней веранде пар. Каждый раз, собираясь на прогулку, Снегоход бросает (правильную) монету и решает, с какой веранды он отправится —с передней или задней. На выбранной веранде он надевает ботинки и выходит из дому. Возвращается он к любой веранде с вероятностью 1/2 независимо от того, откуда он вышел, и оставляет ботинки на этой веранде. Так, после первой прогулки на передней веранде будет пар ботинок, а на задней . Если все ботинки соберутся на одной веранде, а решит выйти на прогулку из другой, то он идет без ботинок, обмораживает ноги и на этом его отпуск кончается. Считая, что он продолжает свои прогулки до такого печального конца, обозначим через вероятность завершения ровно прогулок без обморожений, если сначала на передней веранде было пар, а на задней Тогда, если оба числа тип положительные, имеем

поскольку первая прогулка является передне-задней, переднепередней, задне-задней или задне-передней с вероятностью в каждом случае, и еще остается прогулок, а Дополните рекуррентное соотношение для выписав формулы для случаев или Используя это соотношение, найдите уравнение, связывающее ПФСВ

Продифференцируйте ваши уравнения и положите в них получая тем самым соотношения относительно величин Решите полученные уравнения и найдите среднее число прогулок до обморожения, с Покажите, что для имеет место следующее замкнутое выражение, если выполнить замену

50 Рассмотрим функцию

Цель этого упражнения — доказать, что является производящей функцией случайной величины, и выяснить основные ее свойства.

а Положим Докажите, что

при любом 10. Указание: воспользуйтесь тождеством

и разложите последний множитель по степеням Используя и упр. 5.81, покажите, что все коэффициенты функции положительны, с Докажите следующее любопытное тождество:

Чему равны математическое ожидание и дисперсия Н?

51 В государственной лотерее в Эльдорадо используется распределение выигрышей Н, описанное в предыдущей задаче. Каждый лотерейный билет стоит один дублон, а выплата по этому билету составляет к дублонов с вероятностью Ваши шансы на выигрыш по каждому билету абсолютно не зависят от выигрыша по другим билетам; иными словами, выигрыш или проигрыш по одному билету не оказывает влияния на вероятность выигрыша по любому другому билету, который вы, возможно, приобрели для участия в том же тираже, а Допустим, вы начинаете играть в эту игру, имея один дублон. Если вы выигрываете к дублонов, то во второй раз вы покупаете к билетов; затем вы берете весь выигрыш во второй игре и целиком вкладываете его в третий тираж и т. д. Если ни один из ваших билетов не выигрывает, то вы разоряетесь и вынуждены прекратить игру. Докажите, что ПФСВ вашей суммы денег после кругов такой игры дается выражением

b Пусть — вероятность того, что вы впервые проигрываете все деньги на игре, Докажите, что (Это означает, что, рано или поздно, вы все равно проиграете с вероятностью 1, хотя до того вы можете получить от игры немало удовольствия.) Чему равны математическое ожидание и дисперсия ?

с Сколько в среднем билетов вы купите, если продолжите играть до полного разорения?

d Чему равно среднее число игр до разорения, если в начале у вас не один дублон, а два?

Конкурсные задачи

52 Покажите, что определенные в тексте медиана и мода случайных величин соответствуют в некотором разумном смысле медиане и моде последовательностей, если вероятностное пространство конечно.

53 Докажите или опровергните: если X, Y и Z — случайные величины, обладающие тем свойством, что все три пары независимы, то X + У и Z независимы.

54 Уравнение (8.20) показывает, что среднее значение VX равняется VX. Чему равняется дисперсия VX?

55 В обычной колоде игральных карт 52 карты, по четыре карты каждого из возможных значений Обозначим через X и Y значения, соответственно, верхней и нижней карты в колоде и рассмотрим следующий алгоритм тасования:

51 Перемешать колоду случайно, так чтобы любая перестановка появлялась с вероятностью

52 Если , подбросить несимметричную монету с вероятностью выпадания решки и, если выпадет решка, вернуться к шагу . В противном случае остановиться.

Все бросания монеты и все перемешивания колоды предполагаются независимыми. При каком значении после остановки описанной процедуры значения X и Y будут независимыми случайными величинами?

56 Обобщите задачу о дисках Фрисби из упр. 48 на случай -угольника вместо пятиугольника. Чему равняется в общем случае математическое ожидание и дисперсия числа бросаний без коллизий, если первоначально диски находятся в соседних вершинах? Докажите, что если нечетно, то ПФСВ для числа бросаний можно записать в виде произведения распределений для бросания монеты:

где

Указание: попробуйте выполнить подстановку

57 Докажите, что в игре Пенни последовательность всегда уступает последовательности если 13 и монета правильная.

58 Существует ли последовательность из 13 решек и орлов, такая, что обе последовательности дают одинаковые результаты при сравнении с А в игре Пенни?

59 Существуют ли последовательности А и В из решек и орлов, такие, что А длиннее В, однако А более чем в половине случаев встречается раньше В, если подбрасывать правильную монету?

60 Пусть к и — фиксированные положительные целые и а Найдите замкнутое выражение для ПФСВ

выражающей совместное распределение числа проб, требуемых для поиска элементов, вставленных в хеш-таблицу с списками, Хотя случайные величины зависимы, покажите, что они в каком-то смысле независимы:

61 Используя результат предыдущего упражнения, докажите (8.104).

62 Продолжая упр. 47, найдите дисперсию числа дифагов после облучения частицами.

Исследовательская проблема

63 Нормальное распределение — это недискретное распределение вероятностей, характеризуемое тем свойством, что все его кумулянты равны нулю, за исключением математического ожидания и дисперсии. Имеется ли простой способ, позволяющий по заданной последовательности кумулянтов узнать, не происходит ли эта последовательность из дискретного распределения? (Все вероятности в дискретном распределении должны быть „атомарными!)