Falcão (falcao) wrote,
Falcão
falcao

  • Mood:
  • Music:

ответы к прошлому посту

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

Начну я с того, что сообщу ответы, коротко напомнив то, о чём спрашивалось.

1. Вопрос был о том, сколько раз нужно "в среднем" бросить монетку, чтобы дождаться выпадения трёх "орлов" подряд.

ОТВЕТ: 14.

2. Здесь вопрос был похожий, но спрашивалось, сколько бросаний нужно до выпадения двух "орлов" и следующей за ними "решки". Может показаться, что ответ такой же, однако это не так.

ОТВЕТ: 8.

3. Задано было два вопроса о том, как долго надо собирать (опять-таки, "в среднем") полный комплект этикеток, карт и т.п. Сформулирую условие в общем виде. Есть n видов, например, игральных карт. Мы приобретаем какой-то товар, в который вложена одна из этих карт, причём вероятность встретить данную карту считается равной 1/n, то есть всё "по-честному". Спрашивается тогда, как долго надо "в среднем" собирать полный комплект.

Общий ОТВЕТ даётся такой арифметической формулой: n(1+1/2+1/3+...+1/n). Соответственно, при n=6 имеем

а) около 15 (точное значение 14,7),

а при n=36, то есть для колоды карт получается

б) около 150.

Для тех, кого интересуют объяснения, они приводятся под "катом".


Прежде всего, начну с объяснения "парадокса": почему ответы в пунктах 1 и 2 разные, и это при том, что 000 выпадает с такой же "частотой" как и 001.

Если мы рассмотрим какую-то длинную "случайную" строку и прочитаем её со "случайно" выбранного места, то нам с равной вероятностью встретится каждый из указанных выше случаев. Можно сказать, что средняя "плотность" появления как 000, так и 001 "на единицу длины" будет одинаковой. Однако именно здесь и заметна разница: если вхождения 001 между собой не могут "перекрываться", то 0 может встречаться не три раза подряд, а четыре, пять или больше. И если где-то мы видим 0000, то это даёт уже два вхождения 000 при той же самой средней "норме". Это значит, что следующие такие вхождения будут встречаться относительно далеко. То есть дело в том, что вхождения 000 могут образовывать "сгустки", и за счёт этого у самих "сгустков" будет более низкая "плотность".

А точный подсчёт вот какой (я опускаю "технические" детали). Начнём с пункта 1. Пусть S -- это то "среднее" значение, которое надо найти. Рассмтрим первое бросание, при котором с вероятностью 1/2 выпадает "решка", обозначаемая нами далее как 1. Сколько надо "в среднем" сделать бросаний, чтобы после этого выпало 000? Ясно, что 1 нам никак не "помогает", и что весь процесс начинается заново. И требует он, как мы сами обозначили, S бросаний. Это значит, что при первом выпадании "решки", с учётом этого первого бросания, процесс займёт "в среднем" 1+S шагов.

Теперь рассмотрим случай, когда в самом начале выпал "орёл". Если далее выпала "решка", и получилось 01 после двух бросаний, то дальнейшее ожидание будет составлять S шагов, как и выше, а общее число, с учётом двух дополнительных бросаний, будет равно 2+S. Событие же, которое мы сейчас проанализировали, наступает с вероятностью 1/4.

Теперь пусть в начале выпало два "орла". Далее будет либо 1, либо 0. Если первые три бросания дали 001, то опять всё начинается заново, то есть весь процесс с начала займёт теперь 3+S шагов, и произойдёт это с вероятностью 1/8. Наконец, осталось расмотреть случай, когда сразу выпало 000. Вероятность равна 1/8, а число бросаний равно 3.

Теперь нам надо сложить все полученные оценки вместе, и приравнять это к величине S, которую мы оцениваем. Получится такое уравнение:

S = (1/2)*(1+S)+(1/4)*(2+S)+(1/8)*(3+S)+(1/8)*3,

что после упрощений приводит к ответу S=14.

Аналогично рассматривается пункт 2. Здесь мы сначала разберём такой случай: пусть у нас уже выпал подряд 0 не менее двух раз. Сколько тогда бросаний осталось сделать "в среднем" до выпадения 001? Обозначим эту величину через S'. С вероятностью 1/2 нам сразу выпадет 1, то есть понадобится один "шаг". Если же снова выпадет 0, то мы окажемся в прежнем положении, когда ждать надо S' раз, и всего процесс здесь у нас займёт 1+S' шагов. Это приводит к уравнению

S' = (1/2)*1+(1/2)*(1+S'),

откуда S'=2.

Далее пусть S означает "среднее" число бросаний до выпадения 001, если считать с самого начала. Как и выше, разбиваем всё на случаи выпадения 1, 01, 00 на первых шагах. Это исчерпывает все ситуации, а вероятности равны 1/2, 1/4 и 1/4 соответственно. В первом случае у нас после 1 всё начинается сначала, и весь процесс продлится "в среднем" 1+S шагов, если считать количество бросков с самого первого. Второй случай так же точно приводит к величине 2+S. Наконец, в третьем случае нам останется ждать S'=2 бросаний "в среднем", а потому общий итог составит 4 (с учётом двух бросков, затраченных на выпадение 00). Уравнение имеет теперь вид

S = (1/2)*(1+S)+(1/4)*(2+S)+(1/4)*4,

откуда S=8. Это и есть ответ из пункта 2.

Прежде чем разбирать пункт 3, рассмотрим такую простую ситуацию. Пусть мы проводим независимые испытания, и нас ждёт некий "успех" с вероятностью p. Соответственно, с вероятностью q=1-p нас ожидает "неуспех". Спрашивается,
как долго надо "в среднем" ждать наступления "успеха"?

Например, если мы бросаем игральную кость и ждём выпадения "шестёрки", то p=1/6, и возникает вопрос, как долго этого события придётся ждать? Понятно, что оно может наступить и после первого бросания, а может не наступать довольно долго, если нужное нам значение "упрямо" не хочет выпадать.

Подсчёт здесь простой, и ответ оказывается очень "естественным": он равен 1/p. То есть, "шестёрки" надо "в среднем" именно 6 шагов и ждать.

Рассуждение таково: снова обозначим через S то "среднее" значение, которое нам надо узнать. Случаев будет всего два. В первом из них "успех" произошёл уже на первом шаге. Вероятность равна p, а бросаний потребовалось всего одно. Второй случай: произошёл "неуспех" -- с вероятностью q. Далее нам снова надо S шагов ждать "успеха", и в итоге у нас получается либо 1 шаг с вероятностью p, либо 1+S шагов с вероятностью q. Уравнение имеет вид

S = p*1 + q*(1+S),

то есть S=1+qS. Тем самым, S=1/(1-q)=1/p, как и "анонсировалось".

Теперь применим это всё к ситуации с картами. У нас их всего n, и на каждом шаге нам одна из карт достаётся с вероятностью 1/n. Поначалу наш "комплект" довольно быстро пополняется, то есть выпадают всё новые и новые карты. С какого-то момента начинаются повторения: мы приобретаем то, что у нас уже встречалось. Дольше всего нужно ждать появления самой последней карты: вообразим ситуацию, когда n-1 карта у нас уже "на руках", и мы дожидаемся, когда же появится последняя, n-я по счёту. Из сказанного выше легко понять, что "в среднем" нам именно n шагов и придётся ждать, так как "успех" нас ждёт здесь с вероятностью p=1/n.

Но это касалось самого последнего этапа, а время ожидания остальных карт будет меньше. Первая новая карта нам выпадет вообще сразу, то есть за один шаг. Сколько времени надо ждать второй? "Успеху" здесь соответствует выпадение любой карты, кроме той, которая у нас выпала на первом шаге. То есть "успех" ждёт нас с вероятностью p=(n-1)/n, и для его достижения "в среднем" потребуется 1/p=(n-1)/n шагов. Далее ждём третьей новой карты, и нас устраивает любая, кроме двух выпавших. Здесь p=(n-2)/n, а среднее время ожидания равно n/(n-2). Далее будут получаться величины n/(n-3), n/(n-4), и так далее вплоть до n/2 (ожидание "предпоследней" новой карты), и n/1 для самой последней, как было сказано выше. Суммарное время составит

n/n + n/(n-1) + n/(n-2) + ... + n/2 + n/1 = n*(1+1/2+1/3+...+1/n).

Это и есть ответ для пункта 3. Для n=6 можно увидеть, что значение в точности равно 14,7.

Величина в скобках, на которую мы домножаем n, хотя и растёт неограниченно (это n-я частичная сумма т.н. гармонического ряда), но при этом рост происходит медленно. Приближённое значение этой суммы составляет ln n -- логарифм числа n по основанию "е". На самом деле, нужно сюда добавить ещё константу C, называемую "константой Эйлера", которая приближённо равна 0,577. То есть при "больших" значениях n можно использовать приближённую формулу вида

n*(ln n + 0.577),

что легко делается на калькуляторе. При n=36 расчёт приводит к значению около 150. А для того, чтобы собрать "супер-колоду" из n=100 карт, требуется примерно 517 или 518 покупок. То есть не так уж и много, если вдуматься. Но это, конечно, лишь при "честной" игре.

Если кого-то мои объяснения не устраивают, или есть желание что-то уточнить -- пишите в комментах.
Subscribe
  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

  • 27 comments