Здравствуйте, 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''' в разряд допустимых чисел.

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

Здравствуйте, 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 до бесконечности)

M=sum[P(k)*(m+k)]=sum[P(k)*m]+sum[P(k)*k]=m+sum[k/2^k]=m+2

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

...

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

Как всегда, соврал. Но, надеюсь, без злой интенции.

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


К>Еще раз прорекламирую мою стратегию.
К>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

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

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

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

Два графика для первых 100 и первых 1000 значений ничем, кроме верхней цифры на оси Y не отличаются !

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

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

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

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

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

Класс! А что если по ошибке файл заслал? Как удалить? Или у вас дискового пространства немеряно?

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

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

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

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