И где сашун такие сайты находит некрасивые, диву даюсь )

Тут говорилось уже, что генератор генерирует "правильно", но мэйби "неправильно" извлекается из "кармана".
Я хоть и программер, но с реляционными таблицами опыта у меня мало. Возможно я глупость скажу, но я встречался с таким эффектом, что когда сам не указываешь способ сортировки строк в таблице/запросе, данные могут быть представлены совсем не тем образом, какой подразумевался. Сортируются, подчиняясь какой-то своей внутренней оптимизационной логике. Возможно это могло бы пояснить почему бывают вечера со знаком "мизер или 9п", а бывают вечера со знаком "шестерик за ровно". Тоись, грубо говоря, всему залу сначала выдаются равномерные расклады а потом неравномерные.

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

Это сообщение отредактировал tucan - 12/11/2009, 10:10

Евгений! У меня такое ощущение, что ты подошел уже достаточно близко. Но вот сформулировать алгоритм просто и без всяких замудреностей у тебя еще не получается. А ведь насчет степеней двойки ты правильно подметил. И насчет того, что только бесконечная последовательность одинаковых результатов приведет к незавершенной цепочке. Но если монета бесконечное число раз выпадает "орлом", то она не просто "кривая" - у нее, скорее всего, два "орла".

Поэтому, не буду мучать дальше, а приведу его сам:

1. Единичный бросок заменяется последовательностью бросков. пронумерованных i=0,1,2 ...
2. Эта последовательность разбивается на подпоследовательности длиной 2^m (m>0), начинающихся с номеров бросков m*k (k=0,1,2, ...). Т.е. пары начинаются с номеров 0,2,4,6 ... Четверки с номеров 0,4,8,12 ... Восьмерки с 0,8,16,24 ... и т.д.
3. Подпоследовательность длиной 2^m, составленная из РАЗЛИЧНЫХ подпоследовательностей длиной 2^(m-1) завершает цепочку бросков и в качестве результата испытания берется результат последнего броска.

Удобнее все последовательности длины 2^m, состоящие из одинаковых значений, заменять на это единичное значение и при рассмотрении последовательности длиной 2^(m+1) сравнивать эти единичные значения.

В качестве примера рассмотрим последовательность бросков PPPPPPPPOOOOOOOO...

Разобъем последовательность на пары: (РР)(РР)(РР)(РР)(ОО)(ОО)(ОО)(ОО)... Все пары различны, поэтому заменяем их на единичные значения:

(РР)(РР)(РР)(РР)(ОО)(ОО)(ОО)(ОО) -> РРРРОООО
(РР)(РР)(ОО)(ОО) -> РРОО
(РР)(ОО) -> РО

И вот теперь пришли к паре различных результатов. Исход равен орлу.

На практике можно ограничить последовательность, допустим, максимум, 32-мя бросками. И если вышли за лимит, то взять противоположное значение. Погрешность будет все равно очень небольшая. Разумеется, если монетка не с двумя орлами.

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

Кстати, представляется, что это усовершенствование дает выигрыш по сравнению с тем способом, когда сравниваются только пары, всего в два раза (и то в пределе), а не на порядок, как ты хвалил.

Это сообщение отредактировал tucan - 12/11/2009, 10:16

Что "метод тукана" подразумевает - ето понятно. Непонятен АЛГОРИТМ самого испытания! Понятно НАЧАЛО испытания - два броска ОДНОЙ монетки. Понятна ЗАПИСЬ результатов в ходе испытания.

Непонятно:
- когда, чем, после какого действия ОКАНЧИВАЕТСЯ испытание?
- доказательство, что у испытания РОВНО ДВА возможных исхода - верно ли я понимаю, что испытание оканчивается тогда, когда в очередной паре бросков монетка выпадет разными сторонами?;
- почему ОБА возможных исхода испытания имеют ОДИНАКОВУЮ вероятность.

Примечание.
Мне понятно, что вероятность "бесконечного" выпадания монетки одной стороной равна нулю. Поэтому за такой случай в объяснении можно не писать ).

Так будет тут понятное решение задачки про кривую монетку?


--------------------

С уважением, А.Малышев

Судя по всему, Вы уже сформулировали свой тезис и уверены в нем. Тогда, в этом случае, доказать что-либо иное Вам УЖЕ невозможно.

Отнюдь.
Я лишь привел ЧУЖОЙ тезис (Г.Штейнгауза) о том, что ответом на вопрос "Можно ли с помощью несимметричной монеты получить последовательность испытаний с равновероятными исходами?" является предложенный Г.Штейнгаузом алгоритм построения УКАЗАННОЙ ПОСЛЕДОВАТЕЛЬНОСТИ (с доказательством, основанном, в частности, на коммутативности умножения).

Однако, в этой теме был задан ДРУГОЙ ВОПРОС: "Можно ли с помощью несимметричной монеты получить последовательность испытаний с двумя исходами, каждый из которых имеет вероятность 1/2 ?"

Так я, читая эту тему вот уже пара дней не могу понять:
- ответы на етот вопрос: ни разу не было приведено ПОЛНОЕ ОПИСАНИЕ алгоритма испытания;
- доказательство, что описанные последовательности имеют РОВНО ДВА возможных исхода;
- доказательство РАВНОвероятности этих двух исходов.

Вот у меня и возникла просьба пояснить 3 вещи:
- когда, чем, после какого действия ОКАНЧИВАЕТСЯ испытание?
- доказательство, что у испытания РОВНО ДВА возможных исхода - верно ли я понимаю, что испытание оканчивается тогда, когда в очередной паре бросков монетка выпадет разными сторонами?;
- почему ОБА возможных исхода испытания имеют ОДИНАКОВУЮ вероятность.

---------------------

Дополнительно поясняю алгоритм Штейнгауза.
Проводим ПАРНЫЕ броски кривой монетки и отбираем ИСХОДЫ только тех пар бросков, в которых монетка выпала РАЗНЫМИ сторонами.
Все эти отобранные исходы имеют РАВНУЮ вероятность. Например, в случае монетки с вероятностями выпадения аверса и реверса 0,4 и 0,6, все эти исходы будут иметь вероятность 0,24.




Это сообщение отредактировал Сашун - 12/11/2009, 12:13

--------------------

С уважением, А.Малышев

А какой критерий эффективности брать?

Если брать вероятность того, что очередной бросок в среднем завершит цепочку, то тут различия будут действительно на порядки. Ведь он может привести не только к разнозначной паре, но и к разнозначной четверке, восьмерке и т.д.

Например, какова вероятность, что цепочка будет завершена в течение 16-ти бросков?

Легче, правда, посчитать, что она НЕ будет завершена ...

По упрощенной схеме она не будет завершена, если каждая пара будет состоять из одинаковых значений. Вероятность выпадения пары с одинаковыми значениями (1-2*p+2*p*p), а вероятность выпадения таких 8-ми пар подряд равна (1-2*p+2*p*p)^8.

По модифицированному алгоритму цепочка будет незавершенной только в том случае, если все результаты бросков будут одинаковыми. Вероятность этого равна p^16+(1-p)^16.

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

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

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

Верно ли я понимаю, что в "методе тукана" испытание оканчивается тогда, когда в очередной паре бросков монетка выпадет разными сторонами?


--------------------

С уважением, А.Малышев

Так же, как и в методе Штейнгауза.

Кстати, была где-то у меня его занимательная книжечка. Много там весьма поучительных вещей было описано. В том число и нахождение фальшивой монеты из 12-ти тремя взвешиваниями.

К сожалению, лет 20 ее не видел. Потерял, скорее всего.