Re[3]: Орлы - Этюды для программистов

Здравствуйте, _DAle_, Вы писали:

_DA>Здравствуйте, adontz, Вы писали:

A>>Здравствуйте, Slime, Вы писали:

S>>>Каждая из этих пар с равной вероятностью принимает значение и множества {00,01,10,11}. Это значит, что в среднем, из четырех подряд идущих пар, одна будет равна 11.

A>>Так, идём и читаем про цепи Маркова, потом возвращаемся и сами себе ставим минус

_DA>Зачем, достаточно про вычисление мат ожидания дискретной случайной величины.

Совершив N+1 подбасывание мы получим N пар: пусть результатом подбрасываний является последовательность abcdef парами будут — ab,bc,cd,de,ef. Каждая из этих пар с равной вероятностью принимает значение и множества {00,01,10,11}. Это значит, что в среднем, из четырех подряд идущих пар, одна будет равна 11. То есть N=4, отсюда следует, что матожидание числа подбрасываний равно 5.

Sorry рассуждал верно, но в ответе перемудрил: матожидание числа подбрасываний равно 4. То что число бросков на 1 больше чем пар — значения не имеет.

Но замечания от _DAle_ и adontz меня нескольно удивили... Из них следует, что какая из пар {00,01,10,11} будет встречаться чаще других (при большом N).

Здравствуйте, Аноним, Вы писали:

А>Но замечания от _DAle_ и adontz меня нескольно удивили... Из них следует, что какая из пар {00,01,10,11} будет встречаться чаще других (при большом N).

Нет, погляди на мой рисунок. Рассматриваю я или нет подбрасывание N + 1 зависит от результата подбрасывания N. Твои пары не независимые, величины. Если было кинуто решка-решка-решка, то выроятность, что следующая пара будет орёл-орёл не 1/4 а 0.

Здравствуйте, Аноним, Вы писали:

Предыдущий пост мой (минусы можно класть сюда).

Здравствуйте, adontz, Вы писали:

A>Здравствуйте, Аноним, Вы писали:

А>>Но замечания от _DAle_ и adontz меня нескольно удивили... Из них следует, что какая из пар {00,01,10,11} будет встречаться чаще других (при большом N).

A>Нет, погляди на мой рисунок. Рассматриваю я или нет подбрасывание N + 1 зависит от результата подбрасывания N. Твои пары не независимые, величины. Если было кинуто решка-решка-решка, то выроятность, что следующая пара будет орёл-орёл не 1/4 а 0.

Переход из одного сотсояния в любое другое составляет не более двух подбрасываний. Причем в каком бы состоянии мы не находились, два подбрасывания переводят нас в любое из четырех состояний с равной вероятностью.
Вас смущает зависимость последовательно идущих пар: нет проблем.

Пусть было совершено N подбрасываний монеты: события abcdefgh...

Подсчитаем вероятности появлений для каждой из четырех пар, беря только нечетные выпавшие пары: ab cd ef gh...
Они независимы. Вероятности появления среди них пар {00,01,10,11} очевидно равны по 1/4.

Теперь подсчитаем вероятности появлений пар, беря только нечетные выпавшие пары: bc de fg...
Эти пары тоже независимы. И о чудо! Вероятности появления среди них пар {00,01,10,11} также равны по 1/4.

Объединим эти две статистики и получим, что среди пар ab bc cd de ef fg gh... пара 11 встречается с вероятностью 1/4.

Здравствуйте, Slime, Вы писали:

S>Объединим эти две статистики и получим, что среди пар ab bc cd de ef fg gh... пара 11 встречается с вероятностью 1/4.

То есть теперь имеем ответ 8?

На самом деле нельзя объединять эти две статистики. Вопрос ведь не в том с какой вероятностью будет ли два орла подряд в последовательности из 8 подбрасываний, а в том сколько раз в среднем надо кинуть, пока не выпадет подряд два орла.

Здравствуйте, adontz, Вы писали:

A>Здравствуйте, Slime, Вы писали:

S>>Объединим эти две статистики и получим, что среди пар ab bc cd de ef fg gh... пара 11 встречается с вероятностью 1/4.

A>То есть теперь имеем ответ 8?

Почему 8? Одну последовательность из N пар я разбил на две последовательности из N/2 пар. Подсчитал вероятности для каждой из них и объединил. На распределение вероятностей это никак не повлияло.

A>На самом деле нельзя объединять эти две статистики. Вопрос ведь не в том с какой вероятностью будет ли два орла подряд в последовательности из 8 подбрасываний, а в том сколько раз в среднем надо кинуть, пока не выпадет подряд два орла.

Так ведь это, по определению, одно и тоже! Ну возмите одиночное вападение орла: может потребоваться 1 бросок, а может и 1000 не хватит, но реально требуется 2 броска. Аналогично для игральной кости требуется в среднем 6 бросков для выпадения любой из сторон. Я показал что пары выпадений можно рассматривать как независимые события из чего и получил искомое число подбрасываний. Хотя если рассматривать не последовательность из N подбрасываний, а рассматривать N подбрасывателей, подбрасывающих каждый собственную монету до выпадения двух орлов, то матожидание числа бросков будет равно 5 из-за непродуктивного начального броска. Это узкое место требующее уточнения, но по сути оно мало что меняет в рассуждениях.

Здравствуйте, Slime, Вы писали:

S>Так ведь это, по определению, одно и тоже!

Где ты берёшь такие определения?

S>Ну возмите одиночное вападение орла: может потребоваться 1 бросок, а может и 1000 не хватит, но реально требуется 2 броска.

А вот и нет. В среднем требуется 1 бросок.

S>Аналогично для игральной кости требуется в среднем 6 бросков для выпадения любой из сторон.

А вот и нет. В среднем требуется 3 броска.

S>Я показал что пары выпадений можно рассматривать как независимые события из чего и получил искомое число подбрасываний.

Во-первых, ты ничего не показал. во-вторых, сделал вывод их неверное предпосылки.

S>Хотя если рассматривать не последовательность из N подбрасываний, а рассматривать N подбрасывателей,

Что совсем не одно и то же

S>>Ну возмите одиночное вападение орла: может потребоваться 1 бросок, а может и 1000 не хватит, но реально требуется 2 броска.

A>А вот и нет. В среднем требуется 1 бросок.

  1     1     1 
1*- + 2*- + 3*-...
  2     4     8

Сумма этого ряда равна 2.

Здравствуйте, _DAle_, Вы писали:

_DA>Сумма этого ряда равна 2.

Да был не прав

Здравствуйте, Slime, Вы писали:

S>Матожидание двух подряд выпавших орлов(00) равно матожиданию двух решек(11), а также равно матожиданию орел-решка(01) и матожиданию решка-орел(10).

S>Совершив N+1 подбасывание мы получим N пар: пусть результатом подбрасываний является последовательность abcdef парами будут — ab,bc,cd,de,ef. Каждая из этих пар с равной вероятностью принимает значение и множества {00,01,10,11}. Это значит, что в среднем, из четырех подряд идущих пар, одна будет равна 11. То есть N=4, отсюда следует, что матожидание числа подбрасываний равно 5.

Случайные величины ab,bc зависимы поэтому ваши рассуждения не проходят.
Дальнейшие рассуждения про матожидание тоже неубедительны...

Правильный ответ здесь
или здесь

Здравствуйте, adontz, Вы писали:

A>Здравствуйте, Slime, Вы писали:

S>>Ну возмите одиночное вападение орла: может потребоваться 1 бросок, а может и 1000 не хватит, но реально требуется 2 броска.

A>А вот и нет. В среднем требуется 1 бросок.
здесь но вы уже ответили
S>>Аналогично для игральной кости требуется в среднем 6 бросков для выпадения любой из сторон.

A>А вот и нет. В среднем требуется 3 броска.

1*1/6 + 2*(5/6*1/6) + 3*(5/6*5/6*1/6)+...=6

S>>Я показал что пары выпадений можно рассматривать как независимые события из чего и получил искомое число подбрасываний.

A>Во-первых, ты ничего не показал. во-вторых, сделал вывод их неверное предпосылки.

S>>Хотя если рассматривать не последовательность из N подбрасываний, а рассматривать N подбрасывателей,

A>Что совсем не одно и то же

Согласен.

Я изучил вашу схему. И нашел ее верной.
Это привело меня к парадоксальному выводу:

Проведем мысленный эксперимент.
Пусть в некоторой комнате раз в минуту подбрасывается монета. Перед очередным подбрасыванием в комнату входит новый наблюдатель. Он следит за результатами подбрасываний и уходит сразу после выпадения двух орлов {11}. Что выпадало до или после того как он вошел в комнату ему не известно. Спрашивается сколько минут в среднем проводят наблюдатели в данной комнате. Ответ очевидно — 5. Несмотря на ваши возражения я это вполне ясно обосновал.
Но суть спора в ином. Ваша точка зрения заключается в том, что нельзя оставлять в комнате наблюдателя видевшего выпадения парного орла (после которого его коллега(и) покинул(и) комнату). Этого наблюдателя следует выгнать и его время не учитывать. И так как после следующего броска он, с вероятностью 50%, мог покинуть комнату сам, то мы получаем увеличение среднего времени нахождения наблюдателей в комнате до 6 минут.
А теперь сам парадокс. Пусть от наблюдателей требуется фиксировать не {11}, а {10}.
После того как наблюдатель покидает комнату, мы выгоняем наблюдателя видевшего {0}. Но это "бесполезный" наблюдатель:
на следующем ходу он не покинет комнату, так как у него будет либо {01}, либо {00}. А кагда пришло бы его время выходить, он покинул бы комнату вместе с группой наблюдателей и у него было бы наибольшее среди них время нахождения в комнате. Таким образом мы уменьшаем среднее время нахождения наблюдателей в комнате до, примерно, 4 минут.

Если не верите — можете проверить программно...

Здравствуйте, Константин, Вы писали:

К>Здравствуйте, Slime, Вы писали:

S>>Матожидание двух подряд выпавших орлов(00) равно матожиданию двух решек(11), а также равно матожиданию орел-решка(01) и матожиданию решка-орел(10).

S>>Совершив N+1 подбасывание мы получим N пар: пусть результатом подбрасываний является последовательность abcdef парами будут — ab,bc,cd,de,ef. Каждая из этих пар с равной вероятностью принимает значение и множества {00,01,10,11}. Это значит, что в среднем, из четырех подряд идущих пар, одна будет равна 11. То есть N=4, отсюда следует, что матожидание числа подбрасываний равно 5.

К>Случайные величины ab,bc зависимы поэтому ваши рассуждения не проходят.
К>Дальнейшие рассуждения про матожидание тоже неубедительны...

Все гораздо проще: ab,cd,ef — не зависимы и bc,de — тоже не зависимы.
В последовательности ab,cd,ef... пара {11} встречается с вероятностью 1/4 и в последовательности bc,de... пара {11} встречается с вероятностью 1/4. Надеюсь не станет откровением предположение, что и в объединенной последовательности ab,cd,ef,bc,de пара {11} будет встречается с вероятностью 1/4.

К>Правильный ответ здесь
К>или здесь
А я и не спорю. Меня смущает что, матожидание двух подряд выпавших орлов{00} равно матожиданию двух решек{11}, но не равно матожиданию орел-решка{01} и матожиданию решка-орел{10} здесь.

Здравствуйте, Slime, Вы писали:

S>Здравствуйте, Константин, Вы писали:

К>>Здравствуйте, Slime, Вы писали:

S>>>Матожидание двух подряд выпавших орлов(00) равно матожиданию двух решек(11), а также равно матожиданию орел-решка(01) и матожиданию решка-орел(10).

S>>>Совершив N+1 подбасывание мы получим N пар: пусть результатом подбрасываний является последовательность abcdef парами будут — ab,bc,cd,de,ef. Каждая из этих пар с равной вероятностью принимает значение и множества {00,01,10,11}. Это значит, что в среднем, из четырех подряд идущих пар, одна будет равна 11. То есть N=4, отсюда следует, что матожидание числа подбрасываний равно 5.

К>>Случайные величины ab,bc зависимы поэтому ваши рассуждения не проходят.
К>>Дальнейшие рассуждения про матожидание тоже неубедительны...

S>Все гораздо проще: ab,cd,ef — не зависимы и bc,de — тоже не зависимы.
S>В последовательности ab,cd,ef... пара {11} встречается с вероятностью 1/4 и в последовательности bc,de... пара {11} встречается с вероятностью 1/4. Надеюсь не станет откровением предположение, что и в объединенной последовательности ab,cd,ef,bc,de пара {11} будет встречается с вероятностью 1/4.

К>>Правильный ответ здесь
К>>или здесь
S>А я и не спорю. Меня смущает что, матожидание двух подряд выпавших орлов{00} равно матожиданию двух решек{11}, но не равно матожиданию орел-решка{01} и матожиданию решка-орел{10} здесь.

А все-таки наверное равно

Чем если не секрет отличается одна комбинация от другой?

Здравствуйте, tinytjan, Вы писали:

T>Здравствуйте, Slime, Вы писали:

...

К>>>Правильный ответ здесь
К>>>или здесь
S>>А я и не спорю. Меня смущает что, матожидание двух подряд выпавших орлов{00} равно матожиданию двух решек{11}, но не равно матожиданию орел-решка{01} и матожиданию решка-орел{10} здесь.

T>А все-таки наверное равно

T>Чем если не секрет отличается одна комбинация от другой?

Они, как ни странно, отличаются. Пары {11} и {00} переходят сами в себя при получении {1} и {0} соответственно.
А вот пары {10} и {01} переходят в себя только при получении {10} и {01} соответственно.
То есть в потоке результатов бросков, пары {11} и {00} часто спрессованы, а пары {10} и {01} всегда
раздельны. Например: последовательность {1111} дает 3 спрессованные пары {11}. А вот последовательность {101010}
дает 3 раздельные пары {10}. Именно свойство спрессованности и губит пары {11} и {00} при проведении эксперимента.
При получении {1111} учесть мы можем только две пары, а одну пару {11} теряем. А при поиске {10} мы не отбрасываем ни одной пары {10}, а наоборот избавляемся от ненужных пар {01} или {00}.

Здравствуйте, Slime, Вы писали:

S>Здравствуйте, Константин, Вы писали:

S>Все гораздо проще: ab,cd,ef — не зависимы и bc,de — тоже не зависимы.
S>В последовательности ab,cd,ef... пара {11} встречается с вероятностью 1/4 и в последовательности bc,de... пара {11} встречается с вероятностью 1/4. Надеюсь не станет откровением предположение, что и в объединенной последовательности ab,cd,ef,bc,de пара {11} будет встречается с вероятностью 1/4.

Проблема в другом.
Неверно следующее утверждение
Неверное утверждение
f_1,f_2,...,f_n --- одинаково распределённые случайные величины p(f_i=={x})=p.
Тогда матожидание(минимальное i: f_i=={x})=1/p
Контрпример1: f_1=f_2=...=f_n=...=f, где f --- случ. величина p(f=={x})=p.
M = p*1+(1-p)*\infty=\infty
Контрпример2:
f=1, c p=1/2; f=0, c p=1/2
f_1=f, f_2=1-f, f_3=f, f_4=1-f.......
M=1/2*1+1/2*2=3/2 != 2

Верное утверждение
f_1,f_2,...,f_n --- одинаково независимые распределённые случайные величины p(f_i=={x})=p.
Тогда матожидание(минимальное i: f_i=={x})=1/p
Доказателсьтво:
на первом шаге: P=p
на втором шаге: P=p*(1-p)
на третьем шаге: P=p*(1-p)*(1-p)
...
M=p*1+p*(1-p)*2+...=1/p

В вашей воследовательности выполняется, что xy --- одинаково распределены, p({xy}=={00})=p({xy}=={01})=p({xy}=={00})=p({xy}=={11})=1/4.
Но случайные величины получились зависимы. Следовательно утверждением пользоваться нельзя. Если бы было можно, получилось бы 4,
и в итоге 5 для исходной задачи, но

Здравствуйте, Slime, Вы писали:

S>А я и не спорю. Меня смущает что, матожидание двух подряд выпавших орлов{00} равно матожиданию двух решек{11}, но не равно матожиданию орел-решка{01} и матожиданию решка-орел{10} здесь.

А что собственно смущает?
Например,
f_n --- число последовательностей длины n, где нет 11
z_n --- число последовательностей длины n, где нет 11, оканчивающиеся на 1
o_n --- число последовательностей длины n, где нет 11, оканчивающиеся на 0
f_n = z_n+o_n
z_{n+1}=o_n
o_{n+1}=z_n+o_n
полезли числа Фибоначчи

ff_n --- число последовательностей длины n, где нет 01
zz_n --- число последовательностей длины n, где нет 01, оканчивающиеся на 1
oo_n --- число последовательностей длины n, где нет 01, оканчивающиеся на 0
ff_n=zz_n+oo_n
zz_{n+1}=z_n+o_n
oo_{n+1}=o_n
Тут всё растёт линейно

Я тут немного поразглогольствую...

Единственно верный постулат... Если долго и упорно бить в бубен, то он обязательно сломается, но не обязательно порветься.

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

Попробуем упростить задачу. Если любую пару подбрасываний принять за 1 событие. если система идеальная то максимально мы встретим всего 3 неверных первых событий, три наших события это 6 подбрасываний...

ОТВЕТ 6.

А вообще это все словоблудие, хорошо хоть не рукоблудие

Здравствуйте, GSL, Вы писали:

GSL>Я тут немного поразглогольствую...

GSL>...
GSL>...
GSL>...

GSL>Попробуем упростить задачу. Если любую пару подбрасываний принять за 1 событие. если система идеальная то максимально мы встретим всего 3 неверных первых событий, три наших события это 6 подбрасываний...

GSL>ОТВЕТ 6.

А почему мы берем именно максимум?
И откуда берется 6 подбрасываний из 3+1 события, ведь 6 подбрасываний дает 5 событий?

Здравствуйте, Нэчер, Вы писали:

Н>Здравствуйте, GSL, Вы писали:

GSL>>Я тут немного поразглогольствую...

GSL>>...

GSL>>Попробуем упростить задачу. Если любую пару подбрасываний принять за 1 событие. если система идеальная то максимально мы встретим всего 3 неверных первых событий, три наших события это 6 подбрасываний...

GSL>>ОТВЕТ 6.

Н>А почему мы берем именно максимум?
Н>И откуда берется 6 подбрасываний из 3+1 события, ведь 6 подбрасываний дает 5 событий?

Я же говорил шаманить будем... Вообщем так время ожидания, как мне кажеться ( !!! ) это то сколько масимально пройдет времяни до выпадения нужного события... максимально для равномерно распределенно системы событий должно произойти 3 события, т.к. в одном событии 2 броска следовательно время ожидания 6 бросков... правда только до начала события. Время же ожидания события скорее всего окажеться 7

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

З.Ы. Вообшем шаманство, но вроде работает

P.S

	От:	_DAle_
	Дата:	06.06.05 15:52
	Оценка:

	От:	Аноним
	Дата:	06.06.05 16:28
	Оценка:

От:	adontz	http://adontz.wordpress.com/
Дата:	06.06.05 16:38
Оценка:

	От:	Slime
	Дата:	06.06.05 16:40
	Оценка:

	От:	Slime
	Дата:	06.06.05 17:11
	Оценка:

	От:	Константин
	Дата:	07.06.05 06:54
	Оценка:

	От:	GSL
	Дата:	19.06.05 10:37
	Оценка:

	От:	Нэчер
	Дата:	19.06.05 17:24
	Оценка:

	От:	GSL
	Дата:	19.06.05 21:28
	Оценка: