2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Равномерные распределения с помощью монеты разными способами
Сообщение26.08.2014, 23:08 
Заслуженный участник


27/04/09
28128
Есть у нас честная монетка (счётное множество независимых величин, равномерно распределённых на $\{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.

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

И так далее.

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

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

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

 Профиль  
                  
 
 Re: Равномерные распределения с помощью монеты разными способами
Сообщение02.09.2014, 23:10 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Равномерные распределения с помощью монеты разными способами
Сообщение11.10.2014, 09:57 


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

-- 11.10.2014, 09:39 --

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

 Профиль  
                  
 
 Re: Равномерные распределения с помощью монеты разными способами
Сообщение11.10.2014, 15:25 
Заслуженный участник


27/04/09
28128
fractalon в сообщении #917557 писал(а):
кажется, всегда в минимуме все степени двойки будут лежать в одном множителе разложения
Это как раз не обязательно — степень двойки раскладывается только на степени двойки, и со всеми ними всё хорошо. Вот отдельность от простых уже влияет. :-)

 Профиль  
                  
 
 Re: Равномерные распределения с помощью монеты разными способами
Сообщение16.12.2014, 10:23 
Заслуженный участник


12/08/10
1368
Я вроде доказал что оптимальный алгоритм будет таким(это жадный алгоритм):
Будем строить дерево вариантов постепенно дорисовывая к нему уровни.
Обозначим $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}$

 Профиль  
                  
 
 Re: Равномерные распределения с помощью монеты разными способами
Сообщение26.12.2015, 13:53 
Заслуженный участник


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 6 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


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

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group