Равномерные распределения с помощью монеты разными способами

[arseniiv]

Есть у нас честная монетка (счётное множество независимых величин, равномерно распределённых на $\{0,1\}$). Известно, как с помощью неё получить случайные величины, равномерно распределённые на любом $1..n$ — кидаем монету $c = \lceil\log_2 n\rceil$ раз и, если выпал код числа не из $0..n-1$, а из $n..2^c-1$, перекидываем по $c$ раз до победы. Матожидание числа бросков для такого способа $2^cc/n$.

Но может существовать разложение $n$ на 2 и больше множителей $n_1\cdots n_k$, и тогда, выкидывая по одному множителю, можно получить такую же хорошую случайную величину, при этом матожидание числа бросков может быть другим, т. к. это уже $\sum_{i=1}^k 2^{c_i}c_i/n_i$. Для каждого числа можно получить множество матожиданий бросков при разных способах издевательства над монеткой, и это множество $E_n$ — как раз вопрос этой темы. Что можно о нём сказать (и об элементах, и о мощности)?

Очевидные факты:
• Для простых и степеней двойки множество имеет один элемент.
• У степеней двойки $2^n$ единственное матожидание строго меньше всех ожиданий для бо́льших чисел, и чисел из $2^{n-1}..2^n-1$, и равны они, конечно, $n$.
• $\lvert E_n\rvert$ меньше числа разложений на множители, если присутствует квадрат или более высокая степень двойки — все разложения, отличающиеся только перегруппировкой двоек, имеют один образ. А есть ли другие случаи?
• Мазня: супремумы и инфимумы множеств (синие и красные соотв.), их разности, все элементы множеств.
• Пример $n = 24$ для ленивых:

$$\begin{array}{lc} \text{Разложения} & \text{Соответствующее }\mathsf E \\ \hline 3\cdot8 = 3\cdot2\cdot4 = 3\cdot2^3 & 17/3 \\ 4\cdot6 = 2^2\cdot6 & 6 \\ 2\cdot12 & 19/3 \\ 24 & 20/3 \end{array}$$

Можно сэкономить один бросок, выкидывая не 24 из 32, а 3 из 4 и потом ещё 8.

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

И так далее.

Можно обобщить определения и на случай трёхгранной ( ) и т. д. монеты.

-- Ср авг 27, 2014 02:11:27 --

Наверно, числовые теоретики тут уже покопались?

[arseniiv]

Кстати, стоит ли из этого раздуть парочку последовательностей для OEIS? (Парами числителей и знаменателей, или умножением на $n$ целочисленных.)

[fractalon]

Интересно, интересно...
По поводу поиска минимума множества - кажется, всегда в минимуме все степени двойки будут лежать в одном множителе разложения, причём отдельно от всех остальных простых. То есть просто одним множителем будет максимальная степень двойки.

-- 11.10.2014, 09:39 --

Ещё одна очевидность: нижняя и верхняя граница множества отличаются не более, чем в два раза, а именно нижняя граница не меньше $c$ (чисто информационно).

[arseniiv]

fractalon в сообщении #917557 писал(а):

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

Это как раз не обязательно — степень двойки раскладывается только на степени двойки, и со всеми ними всё хорошо. Вот отдельность от простых уже влияет.

[Null]

Я вроде доказал что оптимальный алгоритм будет таким(это жадный алгоритм):
Будем строить дерево вариантов постепенно дорисовывая к нему уровни.
Обозначим $S$ - количество не законченных ветвей.
В начале у нас только корень -1 вариант 0 бросков.$S=1$.
При дорисовывании уровня у нас появляется $2S$ листьев.
Если $2S\ge n$ тогда $n$ листьев считаем конечными точками и ставим в соответствие каждому из них одно из возможных значений случайной величины. Считаем соответствующие ветви законченными. Осталось $S-n$ незаконченных ветвей.
Если $2S< n$ то остается $2S$ незаконченных ветвей.

Формула матожидания такова: $\frac{1}{n}=0,\alpha_1 \alpha_2 \dots$ -в двоичной системе исчисления. Тогда $E=n\sum\limits_{i=1}^{\infty}\frac{i\alpha_i}{2^i}$

[arseniiv]

(Мне напомнили эту задачу, посмотрел тему и нашёл опечатку в предыдущей формуле для матожидания. Забыли умножить слагаемые на $\alpha_i$.)