Здравствуйте, mrhru, Вы писали:
M>1) А как справедливо "прожеребить" трёх дуэлянтов с помощью обычной (двухсторонней) монетки?
Очевидно, полностью равных шансов здесь нет: будет турнир вида (A*B)*C.
Для поочередной стрельбы есть 6 вариантов, для одновременной (в паре) — 3.
M>2) Сколько раз им придётся бросать монетку?
Если 6 вариантов — то первым броском делим их на 2.
Чтобы выбрать 1 вариант из 3, нужно бросить монетку не менее 2 раз (получив 4 варианта).
С вероятностью Pz=1/4 выпадает "зеро". Тогда совершаем еще 2 броска...
Вероятность того, что придется бросить монетку не менее 2(m+1) раз (из-за того, что m раз выпало зеро), равна
PP(m) = Pz^m.
Вероятность того, что придется бросить монетку ровно 2(m+1) раз, равна
P(m) = Pz^m*(1-Pz)
Отсюда можно посчитать среднее количество бросков: 2(M[m]+1),
M[m] = sum{m=0..oo} P(m) = (1-Z) * sum{m=0..oo} Pz^m = (1-Pz)* 1/(1-Pz) = 1.
итого — в среднем 4 броска (m — это число повторных попыток).
(плюс 1 бросок, если выстрелы поочередные).
M>3) Какова вероятность, что дуэль не состоится(!) ?
Pz^m (m->oo) -> 0
На самом деле, вскоре (после M[m]+3s[m]=3 повторных попыток, или 8 бросков) дуэлянты должны понять, что небо против. Действительно, вероятность такого явления PP(3) = 1/4^3 = 1/256, что менее 1%
M>4) Каково общее решение для N дуэлянтов и обычной монетки?
Интересно, что формула M[m] = 1 не зависит от числа интересующих нас исходов.
Однако, если мы кинули монетку T = ]log2 K[ раз, а интересуют нас только K исходов из 2^T,
то мы можем использовать множество "зеров" в последующих бросках:
Первая попытка
0. K исходов, T0=]log2 K[ бросков, V0=2^T0 исходов, Z0 = V0-K случаев зеро
Если выпал один из зеро, подкинем монетку еще T1 раз: получим V1=Z0*2^T1 вариантов.
если T1 = ]log2 (K/Z0)[, то полученной информации с избытком достаточно, чтобы выбрать K из V1.
1. T1 = ]log2(K/Z0)[, V1=Z0*2^T1, Z1=V1-K
i. Ti = ]log2(K/Z{i-1}[, Vi=Z{i-1}*2^Ti, Zi=Vi-K
Если K=(2^a)*(2^b — 1), то получим стационарные значения:
T0 = a+b
V0 = 2^a * 2^b
Z0 = 2^a
Ti = b
Vi = 2^a * 2^b
Zi = 2^a
Что и наблюдали с 3 участниками.
Мы так и не выяснили, что же это за число "K".
Для дуэли с поочередными выстрелами важен порядок.
Турнир "плей-офф" по системе 1/x-финалов (как и любое двоичное дерево наперед заданной структуры) проецируется на массив из "листьев" этого дерева.
Число перестановок в массиве составит Ko (ordered) = N! (N — число участников).
Если же в паре стреляют одновременно, то взаимное расположение участников в паре не имеет значения.
Фактически, сбалансированный турнир из N=2^a участников имеет N-1 осей симметрии.
(Спроецируем дерево турнира на числовую ось):
1 -+- 2 -+- 3 -+- 4 -+- ...
\_ _/ \_ _/
V V
\____ ____/
V
. . .
Видно, что каждому узлу дерева строго соответствует интервал между соседними целыми числами.
Для N=2^a + 2^b + ... + 2^c (где a>b>c), т.е. двоичное представление N,
число осей симметрии равняется (2^a-1) + (2^b-1) + ... + (2^c-1) = N — (1 + 1 + ... + 1)
поскольку турнир разбивается на множество под-турниров, которые друг с другом не симметричны.
(Представьте себе наиболее-сбалансированное двоичное дерево для такого турнира)
0 1 2 3 4 5 6 7 8 9 10
\_/ \_/ \_/ \_/ \_/
\_/ \_/ \_/
\_____/
\_________/
для 11 участников (11 = 1011b) имеются насыщенные деревья (0..7), (8..9) и (10) (вырожденное)
в которых есть соответственно 7, 1 и 0 осей симметрии.
Итого 8 осей = 11 - 3.
Итак, число осей симметрии S = N — setbits(N)
Число вариантов турнира
Ks (simultaneous) = Ko / 2^S
Здравствуйте, mrhru, Вы писали:
M>И ещё одно соображение.
M>Возможно, что алгоритм с повторным использованием zero для последующих бросков можно еще немного улучшить. M>Смотрите, когда в случае N = 5, в 3 случаях из 8 нам надо бросать дополнительно одну монету — получаем 6 вариантов, из которых 1 не используем. А здря! Конечно, само значение этого варианта совершенно неслучайно, но вероятность его выпадения можно рассматривать как часть бросания монеты (сильно гнутой). Набрав несколько таких "виртуальных бросаний гнутых монеток" — можно заменить одно реальное.
Если у нас получаются несколько независимых взаимоисключающих вариантов зеро, то выпадение одного из них несет информацию.
Когда зеро один, то сделать выбор "между ним" невозможно. В единице содержится 0 бит информации.
Если тебе пришлось сделать k+1 серию бросков, из-за того, что в k выпадал зеро, то k+1'й зеро не является независимым (а точнее — это прямое следствие выпадения k-го).
Еще раз прорекламирую мою стратегию.
1. Бросаем монетку (1 раз). Достаточно информации для выбора?
— нет, повторяем пункт 1
— да, смотрим
2. полученное двоичное число (*) ( в диапазоне [0..(2^k)-1] ). Это зеро? (**)
— нет, останавливаемся
— да, переходим к пункту 1.
(*) Число получается путем сдвига влево предыдущих бросков и дописывания нового младшего разряда.
В результате можно воспользоваться примечанием (***)
(**) Зеро в диапазоне [0,V) для K вариантов — это любое число большее Z = V — (V % K).
Для всех остальных чисел (D) — вариант находится по формуле (D % K).
(***) Если выпал зеро, то мы бросаем монетку еще раз. При этом значения D (текущее число) и V (диапазон вариантов) умножатся на 2. Имеем:
Z' = 2V — 2V % K = 2V — 2(V%K) = 2Z
D' = 2D
D >= Z
D' >= Z'
так будет продолжаться t раз, пока (2^t) % K == 2^t, т.е. 2^t < K. Затем граница зеро резко подскочит, переведя D''' в разряд допустимых чисел.
Тем самым показано, что эта стратегия является оптимальной (минимизирующей число бросков), и варьировать в ней можно только вычисления выпавшего варианта.
Здравствуйте, Кодт, Вы писали:
К>Все равно я остаюсь при ИМХО, что адаптивная стратегия будет чуть лучше железной (хотя выигрыш и незначительный). В 5/16 случаев мы кидаем 3 монетки, еще в 10/16 — четыре, и в 1/16 — начинаем по новой.
) что матожидание числа серий всегда равно 1, независимо от вероятности зеро. Или я там жестоко ошибся?
Похоже, здесь уже ошибся ты
К>M[m] = sum{m=0..oo} P(m) = (1-Z) * sum{m=0..oo} Pz^m = (1-Pz)* 1/(1-Pz) = 1.
Ты посчитал не мат ожидание, а суммарную вероятность. Конечно она равна 1.
А для мат. ожидания ещё множитель n надо было в член суммы ввести.
Если вероятность удачи в одном броске равна p, то среднее количество бросков, конечно 1/p. Это очевидно, но вот тебе формальное доказательство. (все суммы — по n — от нуля до бесконечности)
Для серий то же самое. Если вероятность в одной серии получить победителя 3/4 (для трёх участников), то ожидаемое количество серий 4/3, а брошенных монет 2*4/3=8/3=2.66
Здравствуйте, Pushkin, Вы писали:
M>>То что число бросаний для N = 2^m + 1 стремится к m + 1, когда m >> inf — вполне понятно. Ведь почти в половине случаев выпадает zero и мы вынуждены бросать еще одну монетку. Образно говоря, дополнительные бросания расходуются на борьбу с "лишними" вариантами — чем их больше, тем больше бросков.
P>А вот здесь я не понимаю. P>Ясно, что m монет не хватит, ясно что нужно по крайней мере m+1. P>Но откуда уверенность, что m+1 хватит?
Нужно не более m+1 монет!
P>Ведь вероятность получить победителя в первой серии практически 1/2. P>Значит число необходимых монет (m+1)*2. P>Но это по тупой стратегии. При N=5 нас выручила замечательная хитрость. P>Есть ли рецепт такой хитрости для больших N ?
Для всех N — используется одна и та же хитрость — повторное использование zero.
P>Или хотя бы уверенность, что такая хитрость обязательно существует? P>Мне почему-то кажется, что чем больше N, тем дохлее такая уверенность.
Пусть N — очень велико и равно 2^m + 1. Значит, с вероятностью близкой к 1/2 нам понадобится еще одна монета, потом с 1/4 — еще одна и так далее. Сумма summ(n = 1 to inf) (1/2)^n — стремится к 1 снизу. Если же на каком-то шаге нам нужна не одна монета, а больше — то этот шаг наступит с вероятностью меньшей чем 1/2. В граничном случае (этот случай вырождается в "тупой") N = 2^(m+1) — 1 нам всегда понадобятся m монет, но с вероятностью (1/N)^n.
Евгений, с приветом (но без остроумной подписи, к сожалению )
Здравствуйте, mrhru, Вы писали:
M>1) А как справедливо "прожеребить" трёх дуэлянтов с помощью обычной (двухсторонней) монетки?
бросают три раза (для начала), т.е. первый — второй, второй — третий, третий — первый
у всех равное количество? повторяют операцию...
M>2) Сколько раз им придётся бросать монетку?
три раза (минимум), или 3*n (где n — количество после которого поймут, что у
монетки две "решки")
M>3) Какова вероятность, что дуэль не состоится(!) ?
0.25 после первых трех бросаний монетки, 0.25^n если они будут повторять бросать...
M>4) Каково общее решение для N дуэлянтов и обычной монетки?
хмм...
Здравствуйте, mrhru, Вы писали:
M>4) Каково общее решение для N дуэлянтов и обычной монетки?
Пусть монета бросится М раз. Надо спроэцировать множество вариантов жеребьевки (N!) на множество вариантов серии бросаний (2^M).
Должно выпоняться неравенство: N! <= 2^M.
Соотв. M = log(2,N!)
Понятно, что некоторые варианты серии бросаний не будут иметь отображения (если N!<>2^M); в таком случае можно повторить серию (или отменить дуель). Вероятность такого дела будет: (2^M-N!)/N!.
Можно конечно предложить другой способ пережеребьевки в последнем случае, минимизирующий дополн. колл. бросаний (но должна сохраняться равноверятность вариантов жеребьевки), но это уже другая задача.
Здравствуйте, Кодт, Вы писали:
К>Здравствуйте, mrhru, Вы писали:
M>>1) А как справедливо "прожеребить" трёх дуэлянтов с помощью обычной (двухсторонней) монетки?
К>Очевидно, полностью равных шансов здесь нет: будет турнир вида (A*B)*C. К>Для поочередной стрельбы есть 6 вариантов, для одновременной (в паре) — 3.
Почему же нет полностью равных шансов? Очень даже.
1) И для поочередной стрельбы, и для одновременной — жеребьёвку можно разбить на два этапа:
А) Определяем очередность стрельбы для каждого
Б) (в случае, если при своём ходе, дуэлянт не сам выбирает себе цель) определяем для него цель.
А) Очевидно, что полностью равные шансы для N дулянтов — это оказаться на i-м месте с вероятностью 1/N.
Используем итерационно следующее: пусть какое-то количество участников мы уже прожеребили, теперь из оставшихся М надо сделать выбор "1 из М". Как совершенно верно было сказано, бросаем монетку m раз, где m = ]log2 M[. Если выпадает zero, бросаем еще m раз и т.д.
Вероятность для произвольного участника оказаться на первом месте, очевидно равна 1/N.
Соответсвенно, вероятность оказаться на втором месте равна вероятности оказаться на "первом" при выборе "1 из (N-1):
((1-N)/N) * (1/(1-N)) = 1/N,
на третьем — это выбор "1 из (N-2)
((1-(N-1))/N) * (1/(1-(N-1))) = 1/N ....
Для определения цели (Б) используем аналогичный алгоритм.
---------------------
Количество бросаний монеты для распределения участников по местам, равно:
По поводу использования выпавших zero в последующих бросках — идея интересная, но
— либо я чего-то не понял,
— либо это не обеспечит равновероятного распределения — значия самих zero — гораздо более неслучайны. Например, для трёх участников, приняв за zero комбинацию (0, 0) — как мы можем её использовать при следующих бросаниях?
Евгений, с приветом (но без остроумной подписи, к сожалению )
Здравствуйте, mrhru, Вы писали:
К>>Очевидно, полностью равных шансов здесь нет: будет турнир вида (A*B)*C. К>>Для поочередной стрельбы есть 6 вариантов, для одновременной (в паре) — 3.
M>Почему же нет полностью равных шансов? Очень даже.
< дальше идут размышления про равные возможности оказаться на i-м месте и прицелиться в j-го игрока >
Не, я имел в виду, что после жеребьевки шансы становятся неравны.
Про отдельную жеребьевку "кто в кого целится". Она просто не нужна.
Представим себе дерево турнира на N персон (неважно, сбалансированное или нет).
Пронумеруем все листья.
Теперь достаточно раздать номера участникам в случайном порядке. Т.е. N! вариантов.
Или N!-2^(N-setbits(N)) — если дуэль "от платка".
M>---------------------
Для этого есть тег [ hr ]:
M>По поводу использования выпавших zero в последующих бросках — идея интересная, но M> — либо я чего-то не понял, M> — либо это не обеспечит равновероятного распределения — значия самих zero — гораздо более неслучайны. Например, для трёх участников, приняв за zero комбинацию (0, 0) — как мы можем её использовать при следующих бросаниях?
Зеро — это естественное явление: подкинув монету 2 раза, ты получишь 4 равновероятных варианта. А для жеребьевки нужны 3. Следовательно, четвертый — лишний.
Пусть тебе нужно разыграть K=5 вариантов. Тогда ближайшая степень 2 — это T0=3, V0=8.
Следовательно, варианты 101,110,111 окажутся холостыми. Z0=3.
Они равновероятны, поэтому, если выпал любой из них, мы это запомним... Кинем монетку еще T1=1 раз. Получаются 3*2 равновероятных случаев: 1010,1011,1100,1101,1110,1111.
Первые 5 из них — "значащие": если выпадет один из первых 5, то жеребьевка окончена.
Если же последний (Z1=1) — продолжим кидать монетку.
На самом деле, что получается: мы бросаем монетку 4 раза. 2^4 = 16 = 15+1.
В 15 случаях мы считаем исход удачным, полученное число делим на 3
И есть 1 зеро (1111).
В принципе, можно делать проще:
— если выпал любой зеро, то забывать и начинать жеребьевку по новому.
— всегда кидать столько монеток, чему равен период дроби 1/N в двоичной записи (т.е. 2^T=c*N+1), и делить полученное число на c.
Но это не экономично.
[согласен, скипнуто ]
К>На самом деле, что получается: мы бросаем монетку 4 раза. 2^4 = 16 = 15+1. К>В 15 случаях мы считаем исход удачным, полученное число делим на 3 К>И есть 1 зеро (1111).
К>В принципе, можно делать проще: К>- если выпал любой зеро, то забывать и начинать жеребьевку по новому. К>- всегда кидать столько монеток, чему равен период дроби 1/N в двоичной записи (т.е. 2^T=c*N+1), и делить полученное число на c. К>Но это не экономично.
4 броска — тоже неэкономично
для N = 5 число бросков равно
3 + SUM{i=1 to inf} (3/8)^i = 3.6
что больше log2(5) = 0,53647, но меньше log2(15) = 0,677
Если интересно, то можно предложить следующую задачку:
Найти способ равновероятно выбрать 1 из 5 (в общем случае N) с помощью монетки так, чтобы среднее число бросаний было как можно ближе к log2(5) (log2(N)).
(Чем-то напоминает любимое развлечение математиков — поиск наиболее плотной упаковки N-мерных сфер в N-мерном пространстве )
Евгений, с приветом (но без остроумной подписи, к сожалению )
Оба способа абсолютно точны в том смысле, что дают ровно 1/3 каждому.
1) Симметричный.
Кидаем каждый по монетке. Если у всех выпало одно и то же — не считается, перекидываем.
Если нет, то выиграл тот, кто в меньшинстве.
Вероятность получить победителя на первом круге 3/4, на втором 3/16 и так далее.
Вероятность получить победителя за конечное число шагов 1.
Мат. ожидание кинутых монет 3*4/3=4.
2) Более быстрый. (О нём уже написал Кодт, но я скажу своими словами)
Если бы у нас было 4 человека, мы бы легко нашли победителя 2-мя монетами.
Поставим рядом с тремя одного "призрака", если выпадет на него — переиграем.
Вероятность получить победителя с первого раза тоже 3/4.
Но монет на круг нужно всего 2 а не 3.
Отсюда мат. ожидание 2*4/3=8/3 монеты — меньше трёх!
Здесь кстати у меня другое мат. ожидание получилось для числа монет ( у Кодта — 4 ).
Либо он просто ошибся либо у него другой способ. (Или ошибся я, но вероятность этого мала )
Короче вот это самое число — мат. ожидание числа потребовавшихся монет — и есть наиболее важный критерий качества алгоритма. Думаю, 8/3 это нижний предел. Если кто сделает меньше, максимальный балл обещаю
Для N монет рецепт ясен — вводить больше призраков, до ближайшего числа 2^N. Но здесь, как уже указывалось, остаётся открытым вопрос о том, является ли этот способ самым экономичным. Для N=5, например, сомнительно.
В первом способе тоже можно обобщить на любое N — остаются играть дальше те, кто в меньшинстве. (Если осталось чётное число людей, одной монетой делим их пополам, чтобы потом не было равенства).
PS
Задача действительно хорошая и я раньше её не встречал. Автору почёт и уваженье.
Забавно, что среднее количество бросаний для случаев
— "повторного" использования zero в последующих бросках:
(получив zero (3 комбинации из 8), бросаем монету (6 комбинаций).
Из них 5 полезных, а одно zero — которое использовать нельзя,
поэтому снова бросаем 3 монеты... и т.д....)
P>Для N монет рецепт ясен — вводить больше призраков, до ближайшего числа 2^N. Но здесь, как уже указывалось, остаётся открытым вопрос о том, является ли этот способ самым экономичным. Для N=5, например, сомнительно.
Для N=5 дополнение до 8 оказывается неэффективным
Мы имеем вероятность удачи с первого круга 5/8
Ожидаемое число монет 3*8/5 = 24/5 = 4.8
Если дополнять до следующей степени двойки — до 16, 1 вариант запретный, оставшиеся 15 вариантов прекрасно делятся на пятерых по 3 штуки каждому.
Вероятность успеха за круг 15/16
Ожидаемое число монет 4*16/15 = 64/15 = 4.26 — гораздо выгоднее!
Для N=6 делим на 3 кучи, а потом одной монетой пополам
Ожидаемое число монет 8/3+1 = 11/3 = 3.66
Для N=7 тоже разумно дополнять до 8 — один вариант останется запретным.
Вероятность успеха за круг 7/8
Ожидаемое число монет 3*8/7 = 24/7 = 3.43
N=8 потребность в монетах сваливается в 3.
Итак имеем последовательность числа монет в зависимости от числа участников
N = 2, 3, 4, 5, 6, 7, 8
M = 1, 2.66, 2, 4.26, 3.66, 3.43, 3
Очевидная пилообразная зависимость! В степенях двойки минимумы, сразу после них резкий взлёт, а потом плавный спад — "недостепени" удобней чем "перестепени"
Здравствуйте, mrhru, Вы писали:
К>>На самом деле, что получается: мы бросаем монетку 4 раза. 2^4 = 16 = 15+1. К>>В 15 случаях мы считаем исход удачным, полученное число делим на 3 К>>И есть 1 зеро (1111).
К>>В принципе, можно делать проще: К>>- если выпал любой зеро, то забывать и начинать жеребьевку по новому. К>>- всегда кидать столько монеток, чему равен период дроби 1/N в двоичной записи (т.е. 2^T=c*N+1), и делить полученное число на c. К>>Но это не экономично.
M>4 броска — тоже неэкономично
M>для N = 5 число бросков равно
M>3 + SUM{i=1 to inf} (3/8)^i = 3.6
Как технически реализовать "3.6" броска монетки?
M>что больше log2(5) = 0,53647, но меньше log2(15) = 0,677
Что-то я не понял: log2(5) = 2,xxx; log2(15) = 3,xxx. Может быть, имелось в виду 1/log2...?
M>Если интересно, то можно предложить следующую задачку:
M>Найти способ равновероятно выбрать 1 из 5 (в общем случае N) с помощью монетки так, чтобы среднее число бросаний было как можно ближе к log2(5) (log2(N)).
Отвечаю: бросать монетку по моей технологии, описанной выше. T0,V0,Z0. T1,V1,Z1. И так далее.
Доказательство умозрительное:
1) меньшее число бросков в конкретной серии — все равно не получится, т.к. не хватит информации для выбора
2) большее число бросков в конкретной серии (по альтернативной технологии) — излишне, т.к., используя мою технологию, выбор можно было сделать раньше.
M>(Чем-то напоминает любимое развлечение математиков — поиск наиболее плотной упаковки N-мерных сфер в N-мерном пространстве )
На сферы не похоже. Тем более, что и задача, и решение легко формализуются.
Здравствуйте, Pushkin, Вы писали:
P>Для N=5 дополнение до 8 оказывается неэффективным P>Мы имеем вероятность удачи с первого круга 5/8 P>Ожидаемое число монет 3*8/5 = 24/5 = 4.8
P>Если дополнять до следующей степени двойки — до 16, 1 вариант запретный, оставшиеся 15 вариантов прекрасно делятся на пятерых по 3 штуки каждому. P>Вероятность успеха за круг 15/16 P>Ожидаемое число монет 4*16/15 = 64/15 = 4.26 — гораздо выгоднее!
Дополнение до 8 — это частный случай дополнения до 16!!!
Я не понимаю, как это может быть "гораздо выгоднее". Ты кидаешь 3 монетки, а если выпал зеро (один из 3), то кидаешь четвертую.
P>Итак имеем последовательность числа монет в зависимости от числа участников P>
P>Очевидная пилообразная зависимость! В степенях двойки минимумы, сразу после них резкий взлёт, а потом плавный спад — "недостепени" удобней чем "перестепени"
Связано с длиной периода двоичной дроби 1/N.
Посмотри на поведение M(N) в окресности числа, например, Nx=3*2^10.
При ровно N=Nx — сделаем 10 первичных бросков, далее свели задачу к N=3.
При N=Nx+/-1 — будет какая-то длинная дробь.
(Кстати, я подозреваю, что длина периода 1/N как-то выводится из двоичной записи N. Ы?)
Здравствуйте, Кодт, Вы писали:
К>Дополнение до 8 — это частный случай дополнения до 16!!! К>Я не понимаю, как это может быть "гораздо выгоднее". Ты кидаешь 3 монетки, а если выпал зеро (один из 3), то кидаешь четвертую.
Это ты брось! Если выпал запрещённый вариант, мы не четвёртую должны кидать, а всю серию заново начинать, согласившись, что мы попали в тот неприятный случай 3/8, когда эксперимент завершился неудачно.
Другое дело, что имея один из 3 равновероятных запрещённых вариантов, мы можем ещё раз кинуть монетку и сделать 6 равновероятных вариантов. И тогда можно раздать 5 из них спорщикам, а один таки объявить запрещённым, признать неудачу и начать заново кидать всю серию.
С этой поправленной стратегией вариант дополнения до 8 действительно становится равным и по ответу и по сути варианту дополнения до 16.
P>>Итак имеем последовательность числа монет в зависимости от числа участников P>>
P>>Очевидная пилообразная зависимость! В степенях двойки минимумы, сразу после них резкий взлёт, а потом плавный спад — "недостепени" удобней чем "перестепени"
К>Связано с длиной периода двоичной дроби 1/N.
Здесь я чего-то торможу. Может оно и так, но я не чувствую, почему.
К>Посмотри на поведение M(N) в окресности числа, например, Nx=3*2^10. К>При ровно N=Nx — сделаем 10 первичных бросков, далее свели задачу к N=3.
Сводить задачу к меньшим N последовательным делением это хорошо? Вот простой пример, что это не так — N=63
Если сначала разделить участников на 3 группы, потом ещё на 3, а потом бросить жребий из 7, то монет понадобится
8/3+8/3+24/7=8.76
А если сразу распределить из 63 из 64 вариантов и один объявить запрещённым, будем иметь чуть больше 6 монет
К>При N=Nx+/-1 — будет какая-то длинная дробь.
Мне кажется +1 и -1 кардинально различаются.
При -1 я просто добавлю к спорщикам одного призрака и буду делить первый случай. А если вдруг выпадет на призрака — пожму плечами и начну сначала (но не выпадет же, это невероятно).
А вот при +1 полная задница, надо всё менять, и добром это явно не кончится.
...
P>Для N=5 дополнение до 8 оказывается неэффективным P>Мы имеем вероятность удачи с первого круга 5/8 P>Ожидаемое число монет 3*8/5 = 24/5 = 4.8
P>Если дополнять до следующей степени двойки — до 16, 1 вариант запретный, оставшиеся 15 вариантов прекрасно делятся на пятерых по 3 штуки каждому. P>Вероятность успеха за круг 15/16 P>Ожидаемое число монет 4*16/15 = 64/15 = 4.26 — гораздо выгоднее!
Ещё выгоднее описанное ранее Кодтом
в 3/8 случаях бросаем ещё одну монету и получаем выбор 1 из 6, из которых полезны 5.
В этом шестом случае бросаем снова 3 и т.д....
Число бросаний монеты равно 3 + 3/8(1 + 1/6(3 + 3/8(1 + 1/6(3 + 3/8... = 3.6
и тогда распределение выглядит так:
N = 2, 3, 4, 5, 6, 7, 8
M = 1, 2.66, 2, 3.6, 3.66, 3.43, 3
P>Очевидная пилообразная зависимость! В степенях двойки минимумы, сразу после них резкий взлёт, а потом плавный спад — "недостепени" удобней чем "перестепени"
Распределение чисел от 2 до 32 приблизительно такое
(лень было все вычислять самому, составил програмку, которая сама монеты бросает ,
поэтому результаты неточные )
Дополнительная проверка чисел до 1024 выявила интересный факт — ни один результат не превысил
]log2(N)[
т.е. при N = [512, 1023] — число бросков монеты не превысило 10, хотя и подбиралось близко.
Следуя принципам физиков-экспериментаторов, (полагающих что все числа меньше 100 — так как экперименты с первой сотней чисел эту гипотезу подтверждают ("Физики продолжают шутить")), можно предположить — что это закономерно (когда нибудь это будет доказано? )
И ещё одно соображение.
Возможно, что алгоритм с повторным использованием zero для последующих бросков можно еще немного улучшить.
Смотрите, когда в случае N = 5, в 3 случаях из 8 нам надо бросать дополнительно одну монету — получаем 6 вариантов, из которых 1 не используем. А здря! Конечно, само значение этого варианта совершенно неслучайно, но вероятность его выпадения можно рассматривать как часть бросания монеты (сильно гнутой). Набрав несколько таких "виртуальных бросаний гнутых монеток" — можно заменить одно реальное.
Евгений, с приветом (но без остроумной подписи, к сожалению )
Здравствуйте, mrhru, Вы писали:
M>Ещё выгоднее описанное ранее Кодтом M> в 3/8 случаях бросаем ещё одну монету и получаем выбор 1 из 6, из которых полезны 5. M> В этом шестом случае бросаем снова 3 и т.д.... M> Число бросаний монеты равно 3 + 3/8(1 + 1/6(3 + 3/8(1 + 1/6(3 + 3/8... = 3.6
Да, блин... Мне почему-то казалось, что это ровно то же самое, что у меня. А написать и посчитать ряд поленился. Круто, короче Вот только странно, что 5 теперь лучше 6-и выходит, какая-то другая пила получается. Может и для 6 можно придумать что-то более хитрое? Или можно доказать, что нельзя?
Экперименты говорят, что чем больше основание — ]log2(N)[ — тем более равномерной выглядит эта пила.
Для чисел N = 2^m + 1, при m >= 5, количество бросаний наибольшее, чем для остальных
N = [2^m + 2, 2^(m + 1) — 1].
Так что результаты при N = 5, 9 и 17 — это некая "случайность".
То что число бросаний для N = 2^m + 1 стремится к m + 1, когда m >> inf — вполне понятно. Ведь почти в половине случаев выпадает zero и мы вынуждены бросать еще одну монетку. Образно говоря, дополнительные бросания расходуются на борьбу с "лишними" вариантами — чем их больше, тем больше бросков.
Евгений, с приветом (но без остроумной подписи, к сожалению )
Здравствуйте, Pushkin, Вы писали:
К>>Дополнение до 8 — это частный случай дополнения до 16!!! К>>Я не понимаю, как это может быть "гораздо выгоднее". Ты кидаешь 3 монетки, а если выпал зеро (один из 3), то кидаешь четвертую.
P>Это ты брось! Если выпал запрещённый вариант, мы не четвёртую должны кидать, а всю серию заново начинать, согласившись, что мы попали в тот неприятный случай 3/8, когда эксперимент завершился неудачно.
Ну, если мы решили прибить гвоздями число монеток, то да.
P>Другое дело, что имея один из 3 равновероятных запрещённых вариантов, мы можем ещё раз кинуть монетку и сделать 6 равновероятных вариантов. И тогда можно раздать 5 из них спорщикам, а один таки объявить запрещённым, признать неудачу и начать заново кидать всю серию.
P>С этой поправленной стратегией вариант дополнения до 8 действительно становится равным и по ответу и по сути варианту дополнения до 16.
Все равно я остаюсь при ИМХО, что адаптивная стратегия будет чуть лучше железной (хотя выигрыш и незначительный). В 5/16 случаев мы кидаем 3 монетки, еще в 10/16 — четыре, и в 1/16 — начинаем по новой.
P>>>Очевидная пилообразная зависимость! В степенях двойки минимумы, сразу после них резкий взлёт, а потом плавный спад — "недостепени" удобней чем "перестепени"
Кстати, самые гадские варианты — это K=(2^n)+1. При этом нужно кинуть не менее T=(n+1) монетки, получив Z=(2^n)-1.
К>>Посмотри на поведение M(N) в окресности числа, например, Nx=3*2^10. К>>При ровно N=Nx — сделаем 10 первичных бросков, далее свели задачу к N=3.
P>Сводить задачу к меньшим N последовательным делением это хорошо? Вот простой пример, что это не так — N=63 P>Если сначала разделить участников на 3 группы, потом ещё на 3, а потом бросить жребий из 7, то монет понадобится P>8/3+8/3+24/7=8.76 P>А если сразу распределить из 63 из 64 вариантов и один объявить запрещённым, будем иметь чуть больше 6 монет
Сводить задачу делением на 2 — это хорошо. Возьмем те же 3*2^10.
M(3*2^10) = ...
10 + M(3) = ...
) что матожидание числа серий всегда равно 1, независимо от вероятности зеро. Или я там жестоко ошибся?
А соответственно, число бросков = число серий * длина серии.
К>>При N=Nx+/-1 — будет какая-то длинная дробь.
P>Мне кажется +1 и -1 кардинально различаются. P>При -1 я просто добавлю к спорщикам одного призрака и буду делить первый случай. А если вдруг выпадет на призрака — пожму плечами и начну сначала (но не выпадет же, это невероятно). P>А вот при +1 полная задница, надо всё менять, и добром это явно не кончится.
И именно поэтому и будет наблюдаться пила: с каждым новым участником остается все меньше и меньше зеро (тех самых призраков), пока не произойдет скачок через степень 2.
Здравствуйте, mrhru, Вы писали:
M>То что число бросаний для N = 2^m + 1 стремится к m + 1, когда m >> inf — вполне понятно. Ведь почти в половине случаев выпадает zero и мы вынуждены бросать еще одну монетку. Образно говоря, дополнительные бросания расходуются на борьбу с "лишними" вариантами — чем их больше, тем больше бросков.
А вот здесь я не понимаю.
Ясно, что m монет не хватит, ясно что нужно по крайней мере m+1.
Но откуда уверенность, что m+1 хватит?
Ведь вероятность получить победителя в первой серии практически 1/2.
Значит число необходимых монет (m+1)*2.
Но это по тупой стратегии. При N=5 нас выручила замечательная хитрость.
Есть ли рецепт такой хитрости для больших N ?
Или хотя бы уверенность, что такая хитрость обязательно существует?
Мне почему-то кажется, что чем больше N, тем дохлее такая уверенность.
Здравствуйте, Pushkin, Вы писали:
P>Похоже, здесь уже ошибся ты
К>>M[m] = sum{m=0..oo} P(m) = (1-Z) * sum{m=0..oo} Pz^m = (1-Pz)* 1/(1-Pz) = 1.
P>Ты посчитал не мат ожидание, а суммарную вероятность. Конечно она равна 1. P>А для мат. ожидания ещё множитель n надо было в член суммы ввести.
Семён семёныч! Ёоо.
P>Если вероятность удачи в одном броске равна p, то среднее количество бросков, конечно 1/p. Это очевидно, но вот тебе формальное доказательство. (все суммы — по n — от нуля до бесконечности)
P>M=sum[(n+1)*p*(1-p)^n] = sum[p*(n+1)*q^n]=d/dq sum[p*q^n] = d/dq [p/(1-q)] = p/(1-q)^2 = p/p^2 = 1/p
P>Для серий то же самое. Если вероятность в одной серии получить победителя 3/4 (для трёх участников), то ожидаемое количество серий 4/3, а брошенных монет 2*4/3=8/3=2.66
Здравствуйте, mrhru, Вы писали:
M>Нужно не более m+1 монет! M>Пусть N — очень велико и равно 2^m + 1. Значит, с вероятностью близкой к 1/2 нам понадобится еще одна монета, потом с 1/4 — еще одна и так далее. Сумма summ(n = 1 to inf) (1/2)^n — стремится к 1 снизу. Если же на каком-то шаге нам нужна не одна монета, а больше — то этот шаг наступит с вероятностью меньшей чем 1/2. В граничном случае (этот случай вырождается в "тупой") N = 2^(m+1) — 1 нам всегда понадобятся m монет, но с вероятностью (1/N)^n.
Хорошо, не надо умножать на 2, я понял. Но!
Первоначальный бросок — m+1 монета
+ 1 которая набирается в результате суммы
Итого m+2 — на единицу ты таки соврал
Я правда поаккуратнее бы переписал...
Вероятность того, что потребуется ровно m+k монет P(k>0)=1/2^k
(по крайней мере для малых k, а только малые k и вносят вклад в суммы)
Значит мат. ожидание для числа монет равно (все суммы по k от 1 до бесконечности)
...
P>Хорошо, не надо умножать на 2, я понял. Но! P>Первоначальный бросок — m+1 монета P>+ 1 которая набирается в результате суммы P>Итого m+2 — на единицу ты таки соврал
Как всегда, соврал. Но, надеюсь, без злой интенции.
Евгений, с приветом (но без остроумной подписи, к сожалению )
К>Еще раз прорекламирую мою стратегию. К>1. Бросаем монетку (1 раз). Достаточно информации для выбора? К>- нет, повторяем пункт 1 К>- да, смотрим К>2. полученное двоичное число (*) ( в диапазоне [0..(2^k)-1] ). Это зеро? (**) К>- нет, останавливаемся К>- да, переходим к пункту 1.
Не смог удержаться и написал прогу по столь гениально ясному алгоритму
Здравствуйте, Pushkin, Вы писали:
P>Вот вывод для первых 70 n.
Блин! Как жаль, что я не умею присылать картинки. Но если вы постоите (хоть в экселе) графики зависимости числа нужных монет от числа участников жеребьёвки, то вам понравится!
Два графика для первых 100 и первых 1000 значений ничем, кроме верхней цифры на оси Y не отличаются !
Перекуём баги на фичи!
