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

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



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

Сейчас этот форум просматривают: YandexBot [bot]


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

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