Re: Жеребьёвка
От: Кодт Россия  
Дата: 26.01.03 15:29
Оценка: 31 (3)
Здравствуйте, 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 бросок, если выстрелы поочередные).

Дисперсия
D[m] = M[m]^2 — sum{m=0..oo} P(m)^2
= 1 — (1-Pz)^2 * sum{m=0..oo} Z^2m
= 1 — (1-Pz)^2/(1-Pz^2)
= 1 — (1-Pz)/(1+Pz) = 1 + (Pz-1)/(Pz+1) = 2*Pz/(Pz+1) = 1/2/(5/4) = 0.4

Среднеквадратичное отклонение s[m] = sqrt D[m] = 0.63...



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
Перекуём баги на фичи!
Re[4]: N=5,6,7
От: Кодт Россия  
Дата: 29.01.03 11:00
Оценка: 28 (2)
Здравствуйте, 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''' в разряд допустимых чисел.

Тем самым показано, что эта стратегия является оптимальной (минимизирующей число бросков), и варьировать в ней можно только вычисления выпавшего варианта.
Перекуём баги на фичи!
Re[6]: N=5,6,7
От: Pushkin Россия www.linkbit.com
Дата: 29.01.03 09:37
Оценка: 28 (1)
Здравствуйте, Кодт, Вы писали:

К>Все равно я остаюсь при ИМХО, что адаптивная стратегия будет чуть лучше железной (хотя выигрыш и незначительный). В 5/16 случаев мы кидаем 3 монетки, еще в 10/16 — четыре, и в 1/16 — начинаем по новой.


Да, ты прав, мне уже объяснили мою ошибку.

К>Кстати! Как ты получаешь дроби в матожиданиях?

К>Я ведь показал (http://www.rsdn.ru/Forum/Message.aspx?mid=182029&amp;only=1
Автор: Кодт
Дата: 26.01.03
) что матожидание числа серий всегда равно 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 — от нуля до бесконечности)

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

Для серий то же самое. Если вероятность в одной серии получить победителя 3/4 (для трёх участников), то ожидаемое количество серий 4/3, а брошенных монет 2*4/3=8/3=2.66
Жеребьёвка
От: mrhru Россия  
Дата: 25.01.03 04:01
Оценка: 21 (1)
Для тех чокнутых, которые участвуют в тройной дуэли, остается вопрос, как определить очередность стрельбы.

Для двоих это решается просто — с помощью монетки (двухсторонней). Для одного — с помощью односторонней монетки . Для шестерых — шестисторонней...

1) А как справедливо "прожеребить" трёх дуэлянтов с помощью обычной (двухсторонней) монетки?

2) Сколько раз им придётся бросать монетку?

3) Какова вероятность, что дуэль не состоится(!) ?

4) Каково общее решение для N дуэлянтов и обычной монетки?


(Я эту задачу тоже придумал сам, и тоже попытаюсь этим гордится )
Евгений, с приветом (но без остроумной подписи, к сожалению )
Re[7]: Фракталы !
От: Odi$$ey Россия http://malgarr.blogspot.com/
Дата: 03.02.03 08:11
Оценка: 18 (1)
Здравствуйте, Pushkin, Вы писали:

P>Блин! Как жаль, что я не умею присылать картинки.


а чего уметь-то — кнопка "Загрузить" на форме нового сообщения, и оформляешь ссылку как img

Re[7]: N=5,6,7
От: mrhru Россия  
Дата: 29.01.03 10:01
Оценка: 7 (1)
Здравствуйте, 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.
Евгений, с приветом (но без остроумной подписи, к сожалению )
Re: Жеребьёвка
От: plague Россия  
Дата: 25.01.03 19:57
Оценка:
Здравствуйте, mrhru, Вы писали:

M>1) А как справедливо "прожеребить" трёх дуэлянтов с помощью обычной (двухсторонней) монетки?

бросают три раза (для начала), т.е. первый — второй, второй — третий, третий — первый
у всех равное количество? повторяют операцию...

M>2) Сколько раз им придётся бросать монетку?

три раза (минимум), или 3*n (где n — количество после которого поймут, что у
монетки две "решки")

M>3) Какова вероятность, что дуэль не состоится(!) ?

0.25 после первых трех бросаний монетки, 0.25^n если они будут повторять бросать...

M>4) Каково общее решение для N дуэлянтов и обычной монетки?

хмм...
Re: Жеребьёвка
От: IO Украина  
Дата: 26.01.03 08:07
Оценка:
Здравствуйте, mrhru, Вы писали:

M>4) Каково общее решение для N дуэлянтов и обычной монетки?


Пусть монета бросится М раз. Надо спроэцировать множество вариантов жеребьевки (N!) на множество вариантов серии бросаний (2^M).
Должно выпоняться неравенство: N! <= 2^M.
Соотв. M = log(2,N!)
Понятно, что некоторые варианты серии бросаний не будут иметь отображения (если N!<>2^M); в таком случае можно повторить серию (или отменить дуель). Вероятность такого дела будет: (2^M-N!)/N!.
Можно конечно предложить другой способ пережеребьевки в последнем случае, минимизирующий дополн. колл. бросаний (но должна сохраняться равноверятность вариантов жеребьевки), но это уже другая задача.
Re[2]: Жеребьёвка
От: mrhru Россия  
Дата: 27.01.03 05:12
Оценка:
Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, 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 ....

Для определения цели (Б) используем аналогичный алгоритм.

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

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

2 + 1/4 * 2 + (1/4)^2 * 2 + (1/4)^3 * 2 + (1/4)^4 * 2... + 1 (для распределения осташихся двух) =
2 + 2/3 + 1 = 3 + 2/3.

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

По поводу использования выпавших zero в последующих бросках — идея интересная, но
— либо я чего-то не понял,
— либо это не обеспечит равновероятного распределения — значия самих zero — гораздо более неслучайны. Например, для трёх участников, приняв за zero комбинацию (0, 0) — как мы можем её использовать при следующих бросаниях?
Евгений, с приветом (но без остроумной подписи, к сожалению )
Re[3]: Жеребьёвка
От: Кодт Россия  
Дата: 27.01.03 08:32
Оценка:
Здравствуйте, 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.
Но это не экономично.
Перекуём баги на фичи!
Re[4]: Жеребьёвка
От: mrhru Россия  
Дата: 28.01.03 04:39
Оценка:
Здравствуйте, Кодт, Вы писали:

[согласен, скипнуто ]

К>На самом деле, что получается: мы бросаем монетку 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-мерном пространстве )
Евгений, с приветом (но без остроумной подписи, к сожалению )
Re: Два точных и быстрых способа
От: Pushkin Россия www.linkbit.com
Дата: 28.01.03 06:55
Оценка:
Оба способа абсолютно точны в том смысле, что дают ровно 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
Задача действительно хорошая и я раньше её не встречал. Автору почёт и уваженье.
Re[5]: Жеребьёвка
От: mrhru Россия  
Дата: 28.01.03 06:56
Оценка:
Здравствуйте, mrhru, Вы писали:

...

Забавно, что среднее количество бросаний для случаев
— "повторного" использования zero в последующих бросках:

(получив zero (3 комбинации из 8), бросаем монету (6 комбинаций).
Из них 5 полезных, а одно zero — которое использовать нельзя,
поэтому снова бросаем 3 монеты... и т.д....)


3 + 3/8(1 + 1/6 * 3(1 + 3/8(1 + 1/6 * 3( ... = 3.6

— "Кодт>>- если выпал любой зеро, то забывать и начинать жеребьевку по новому"

3 + 3/8(1 + 3/8(1 + 3/8(1 + 3/8(1 + ... = 3.6

Равны!
Евгений, с приветом (но без остроумной подписи, к сожалению )
Re[2]: N=5,6,7
От: Pushkin Россия www.linkbit.com
Дата: 28.01.03 11:27
Оценка:
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


Очевидная пилообразная зависимость! В степенях двойки минимумы, сразу после них резкий взлёт, а потом плавный спад — "недостепени" удобней чем "перестепени"
Re[5]: Жеребьёвка
От: Кодт Россия  
Дата: 28.01.03 12:28
Оценка:
Здравствуйте, 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-мерном пространстве )


На сферы не похоже. Тем более, что и задача, и решение легко формализуются.
Перекуём баги на фичи!
Re[3]: N=5,6,7
От: Кодт Россия  
Дата: 28.01.03 13:35
Оценка:
Здравствуйте, 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>N = 2,    3,   4,    5,    6,    7,   8 
P>M = 1, 2.66,   2, 4.26, 3.66, 3.43,   3
P>


P>Очевидная пилообразная зависимость! В степенях двойки минимумы, сразу после них резкий взлёт, а потом плавный спад — "недостепени" удобней чем "перестепени"


Связано с длиной периода двоичной дроби 1/N.

Посмотри на поведение M(N) в окресности числа, например, Nx=3*2^10.
При ровно N=Nx — сделаем 10 первичных бросков, далее свели задачу к N=3.
При N=Nx+/-1 — будет какая-то длинная дробь.

(Кстати, я подозреваю, что длина периода 1/N как-то выводится из двоичной записи N. Ы?)
Перекуём баги на фичи!
Re[4]: N=5,6,7
От: Pushkin Россия www.linkbit.com
Дата: 28.01.03 13:57
Оценка:
Здравствуйте, Кодт, Вы писали:

К>Дополнение до 8 — это частный случай дополнения до 16!!!

К>Я не понимаю, как это может быть "гораздо выгоднее". Ты кидаешь 3 монетки, а если выпал зеро (один из 3), то кидаешь четвертую.

Это ты брось! Если выпал запрещённый вариант, мы не четвёртую должны кидать, а всю серию заново начинать, согласившись, что мы попали в тот неприятный случай 3/8, когда эксперимент завершился неудачно.

Другое дело, что имея один из 3 равновероятных запрещённых вариантов, мы можем ещё раз кинуть монетку и сделать 6 равновероятных вариантов. И тогда можно раздать 5 из них спорщикам, а один таки объявить запрещённым, признать неудачу и начать заново кидать всю серию.

С этой поправленной стратегией вариант дополнения до 8 действительно становится равным и по ответу и по сути варианту дополнения до 16.

P>>Итак имеем последовательность числа монет в зависимости от числа участников

P>>
P>>N = 2,    3,   4,    5,    6,    7,   8 
P>>M = 1, 2.66,   2, 4.26, 3.66, 3.43,   3
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 полная задница, надо всё менять, и добром это явно не кончится.
Re[3]: N=5,6,7
От: mrhru Россия  
Дата: 29.01.03 07:28
Оценка:
Здравствуйте, 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 — гораздо выгоднее!

Ещё выгоднее описанное ранее Кодтом
в 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 приблизительно такое
(лень было все вычислять самому, составил програмку, которая сама монеты бросает ,
поэтому результаты неточные )
2 : 1
3 : 2.65808
4 : 2
5 : 3.605
6 : 3.66688
7 : 3.42246
8 : 3
9 : 4.66067
10 : 4.60306
11 : 4.84548
12 : 4.66162
13 : 4.70231
14 : 4.42669
15 : 4.26556
16 : 4
17 : 5.76219
18 : 5.66432
19 : 5.72369
20 : 5.60539
21 : 5.42731
22 : 5.85335
23 : 5.70398
24 : 5.66648
25 : 5.55085
26 : 5.69851
27 : 5.60682
28 : 5.43152
29 : 5.43542
30 : 5.2682
31 : 5.15815
32 : 5


Дополнительная проверка чисел до 1024 выявила интересный факт — ни один результат не превысил

]log2(N)[

т.е. при N = [512, 1023] — число бросков монеты не превысило 10, хотя и подбиралось близко.

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

И ещё одно соображение.

Возможно, что алгоритм с повторным использованием zero для последующих бросков можно еще немного улучшить.
Смотрите, когда в случае N = 5, в 3 случаях из 8 нам надо бросать дополнительно одну монету — получаем 6 вариантов, из которых 1 не используем. А здря! Конечно, само значение этого варианта совершенно неслучайно, но вероятность его выпадения можно рассматривать как часть бросания монеты (сильно гнутой). Набрав несколько таких "виртуальных бросаний гнутых монеток" — можно заменить одно реальное.
Евгений, с приветом (но без остроумной подписи, к сожалению )
Re[4]: N=5,6,7
От: Pushkin Россия www.linkbit.com
Дата: 29.01.03 07:55
Оценка:
Здравствуйте, 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 можно придумать что-то более хитрое? Или можно доказать, что нельзя?
Re[5]: N=5,6,7
От: mrhru Россия  
Дата: 29.01.03 09:02
Оценка:
Здравствуйте, Pushkin, Вы писали:

...

Экперименты говорят, что чем больше основание — ]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 и мы вынуждены бросать еще одну монетку. Образно говоря, дополнительные бросания расходуются на борьбу с "лишними" вариантами — чем их больше, тем больше бросков.
Евгений, с приветом (но без остроумной подписи, к сожалению )
Re[5]: N=5,6,7
От: Кодт Россия  
Дата: 29.01.03 09:09
Оценка:
Здравствуйте, 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) = ...

Кстати! Как ты получаешь дроби в матожиданиях?
Я ведь показал (http://www.rsdn.ru/Forum/Message.aspx?mid=182029&amp;only=1
Автор: Кодт
Дата: 26.01.03
) что матожидание числа серий всегда равно 1, независимо от вероятности зеро. Или я там жестоко ошибся?
А соответственно, число бросков = число серий * длина серии.

К>>При N=Nx+/-1 — будет какая-то длинная дробь.


P>Мне кажется +1 и -1 кардинально различаются.

P>При -1 я просто добавлю к спорщикам одного призрака и буду делить первый случай. А если вдруг выпадет на призрака — пожму плечами и начну сначала (но не выпадет же, это невероятно).
P>А вот при +1 полная задница, надо всё менять, и добром это явно не кончится.

И именно поэтому и будет наблюдаться пила: с каждым новым участником остается все меньше и меньше зеро (тех самых призраков), пока не произойдет скачок через степень 2.
Перекуём баги на фичи!
Re[6]: N=5,6,7
От: Pushkin Россия www.linkbit.com
Дата: 29.01.03 09:44
Оценка:
Здравствуйте, 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, тем дохлее такая уверенность.
Re[7]: N=5,6,7
От: Кодт Россия  
Дата: 29.01.03 11:10
Оценка:
Здравствуйте, 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


Спасибо!!!
Перекуём баги на фичи!
Re[8]: N=5,6,7
От: Pushkin Россия www.linkbit.com
Дата: 29.01.03 11:40
Оценка:
Здравствуйте, 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 до бесконечности)

M=sum[P(k)*(m+k)]=sum[P(k)*m]+sum[P(k)*k]=m+sum[k/2^k]=m+2
Re[9]: N=5,6,7
От: mrhru Россия  
Дата: 29.01.03 12:05
Оценка:
Здравствуйте, Pushkin, Вы писали:

...

P>Хорошо, не надо умножать на 2, я понял. Но!

P>Первоначальный бросок — m+1 монета
P>+ 1 которая набирается в результате суммы
P>Итого m+2 — на единицу ты таки соврал

Как всегда, соврал. Но, надеюсь, без злой интенции.
Евгений, с приветом (но без остроумной подписи, к сожалению )
Re[5]: Программа
От: Pushkin Россия www.linkbit.com
Дата: 29.01.03 13:41
Оценка:
Здравствуйте, Кодт, Вы писали:


К>Еще раз прорекламирую мою стратегию.

К>1. Бросаем монетку (1 раз). Достаточно информации для выбора?
К>- нет, повторяем пункт 1
К>- да, смотрим
К>2. полученное двоичное число (*) ( в диапазоне [0..(2^k)-1] ). Это зеро? (**)
К>- нет, останавливаемся
К>- да, переходим к пункту 1.

Не смог удержаться и написал прогу по столь гениально ясному алгоритму

double coins(int n)
{
    const double d=0.001;
    double p=1,m=0;
    int v=1;

    while(p*n>d)
    {
        if(v<n)
        {
            m+=p;
            v*=2;
        }
        else
        {
            p=p*(v-n)/v;
            v-=n;
        }
    }
    return m;
}


Вот вывод для первых 70 n.

02 — 1.00
03 — 2.67
04 — 2.00
05 — 3.60
06 — 3.67
07 — 3.43
08 — 3.00
09 — 4.67
10 — 4.60
11 — 4.85
12 — 4.67
13 — 4.71
14 — 4.43
15 — 4.27
16 — 4.00
17 — 5.76
18 — 5.67
19 — 5.72
20 — 5.60
21 — 5.43
22 — 5.85
23 — 5.70
24 — 5.67
25 — 5.55
26 — 5.71
27 — 5.61
28 — 5.43
29 — 5.44
30 — 5.27
31 — 5.16
32 — 5.00
33 — 6.85
34 — 6.76
35 — 6.74
36 — 6.67
37 — 6.79
38 — 6.72
39 — 6.59
40 — 6.60
41 — 6.55
42 — 6.43
43 — 6.95
44 — 6.85
45 — 6.79
46 — 6.70
47 — 6.75
48 — 6.67
49 — 6.63
50 — 6.55
51 — 6.43
52 — 6.71
53 — 6.63
54 — 6.61
55 — 6.51
56 — 6.43
57 — 6.54
58 — 6.44
59 — 6.37
60 — 6.27
61 — 6.26
62 — 6.16
63 — 6.10
64 — 6.00
65 — 7.91
66 — 7.85
67 — 7.82
68 — 7.76
69 — 7.81
70 — 7.74
Re[6]: Фракталы !
От: Pushkin Россия www.linkbit.com
Дата: 29.01.03 14:48
Оценка:
Здравствуйте, Pushkin, Вы писали:

P>Вот вывод для первых 70 n.


Блин! Как жаль, что я не умею присылать картинки. Но если вы постоите (хоть в экселе) графики зависимости числа нужных монет от числа участников жеребьёвки, то вам понравится!

Два графика для первых 100 и первых 1000 значений ничем, кроме верхней цифры на оси Y не отличаются !
Re[8]: Фракталы !
От: IO Украина  
Дата: 03.02.03 08:58
Оценка:
Здравствуйте, Odi$$ey, Вы писали:

OE>а чего уметь-то — кнопка "Загрузить" на форме нового сообщения, и оформляешь ссылку как img


Класс! А что если по ошибке файл заслал? Как удалить? Или у вас дискового пространства немеряно?
Re[8]: Фракталы !
От: Pushkin Россия www.linkbit.com
Дата: 03.02.03 09:06
Оценка:
Здравствуйте, Odi$$ey, Вы писали:

OE>а чего уметь-то — кнопка "Загрузить" на форме нового сообщения, и оформляешь ссылку как img


О! Спасибо большое. До чего же всё-таки удобный сайт.
На других надо было предварительно куда-то выложить картинку самому, а потом писать ссылку.

Вот 2 картинки, отличающиеся масштабом. Первая — до 100 участников, вторая для 1000.
Картинки замечательно похожи — типичные фракталы.

 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.