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

[Spook]

Допустим, есть набор из $N$чисел и есть случайная величина $X$, принимающая 1 либо 0 с равной вероятностью. Требуется за конечное число шагов равновероятно выбирать число, используя только $X$.

Если $N$ - степень двойки, то понятно как выбирать: если 0 - берем левую половину (упорядочив исходные числа), если единичка - правую, и т.д., уменьшая кол-во претендентов каждый раз в два раза, пока не останется одно число. А вот можно ли организовать такой выбор для произвольного натурального $N$?

[gris]

Занумеруем числа от $0$ до $N-1$. возьмём $k$ такое, что $2^k>N-1$ и вперёд. за $k$ бросаний будем определять двоичный номер числа. номера, большие $N-1$ будем отбрасывать. остальные равновероятны. Немножко неэкономно при некоторых $N$

[ИСН]

Угу.
Дальше обычно спрашивают, нельзя ли уложиться в гарантированно (worst-case) конечное количество бросков.
Нет, нельзя.

[Spook]

gris в сообщении #260871 писал(а):

Занумеруем числа от $0$ до $N-1$. возьмём $k$ такое, что $2^k>N-1$ и вперёд. за $k$ бросаний будем определять двоичный номер числа. номера, большие $N-1$ будем отбрасывать. остальные равновероятны. Немножко неэкономно при некоторых $N$

В таком случае мы можем очень долго выбирать число.

ИСН в сообщении #260877 писал(а):

Угу.
Дальше обычно спрашивают, нельзя ли уложиться в гарантированно (worst-case) конечное количество бросков.
Нет, нельзя.

Я тоже так думаю. Но доказать не могу.

[gris]

Почему долго? В худшем варианте, когда $N=2^k+1$ , будет приниматься в среднем половина номеров.

[Spook]

gris, в том-то и дело, что в среднем. То есть может быть и так, что процесс может затянуться неограниченно долго.

[gris]

Можно оценить вероятность холостой серии из $m$ попыток. Она будет со страшной скорость стремиться к нулю приросте $m$.
Но Вас это не успокоит...

[ИСН]

Конечное количество бросков порождает нам вероятности, которые выражаются конечной дробью в двоичной системе. Про 1/N этого не скажешь.

[Spook]

gris писал(а):

Можно оценить вероятность холостой серии из $m$ попыток. Она будет со страшной скорость стремиться к нулю приросте $m$.
Но Вас это не успокоит...

Я согласен с Вами. Скорее всего на практике именно так и делают. Просто мне чисто теоретически интересно стало.

-- Ср ноя 11, 2009 21:02:19 --

ИСН писал(а):

Конечное количество бросков порождает нам вероятности, которые выражаются конечной дробью в двоичной системе.

Вероятности того, что останется выбранное число?

[PAV]

Имеется в виду следующее. Если бросить монетку $k$ раз, то полное описание этого эксперимента состоит из $2^k$ равновероятных исходов. Единственное, что можно с этим делать - стоить сложные события, вероятности которых могут принимать только значения вида $\frac{m}{2^k}$. Ничего другого с этим сделать нельзя, если Вы хотите, чтобы каждая серия из $k$ бросаний гарантированно давала бы реализацию искомого события.

[Spook]

Спасибо, теперь понятно.

[Профессор Снэйп]

gris в сообщении #260871 писал(а):

Занумеруем числа от $0$ до $N-1$. возьмём $k$ такое, что $2^k>N-1$ и вперёд. за $k$ бросаний будем определять двоичный номер числа. номера, большие $N-1$ будем отбрасывать. остальные равновероятны. Немножко неэкономно при некоторых $N$

Не, ну можно, конечно, слегка оптимизировать.

Допустим $N=5$. Получается, что 3 раза бросаем монетку, в $3$ из $8$ случаев результат отбрасывается и процедура начинается снова.

С другой стороны, если монетку подбросить $4$ раза, то получается $16$ исходов, всего на $1$ больше чем $15 = 5 \cdot 3$. Выбираем заранее в $16$-ти двоичных последовательностях длины $4$ $15$ штук, делим их на $5$ групп по три, значения случайной величины, равномерно распределённой на пятиэлементном множестве, определяем как результат попадания в одну из этих групп. Получается, что при четырёх бросаниях отбраковывается лишь $1$ из $16$ исходов. Выгода налицо!

Так что, лучше, наверное, такой алгоритм. Бросаем монетку непрерывно, после каждых $k$ бросаний выделяем группы из $N \cdot m < 2^k$ двоичных последовательностей длины $k$ и смотрим попадание туда; как только попадаем --- процесс прекращается.

[venco]

Профессор Снэйп в сообщении #261099 писал(а):

Так что, лучше, наверное, такой алгоритм. Бросаем монетку непрерывно, после каждых $k$ бросаний выделяем группы из $N \cdot m < 2^k$ двоичных последовательностей длины $k$ и смотрим попадание туда; как только попадаем --- процесс прекращается.

Так нельзя. После первого же выделения на следующем шаге $k$ вероятности $2^k$ исходов не равны. Правильнее будет держать остаток $r$ с предыдущих шагов, и выделять из $2r$ на следующем шаге. Например, при $N=5$, после 3-х шагов у нас 8 вариантов, 5 выделяем, если не попало, то остаток - 3, и на следующем шаге выбираем из $2\cdot 3=6$ вариантов.

[Профессор Снэйп]

venco в сообщении #261123 писал(а):

Так нельзя.

Ну да, согласен.