2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1, 2
 
 Re: Нечестная монетка
Сообщение27.03.2025, 13:57 
Заслуженный участник
Аватара пользователя


16/07/14
9529
Цюрих
sirvff в сообщении #1680072 писал(а):
пример приведите плз
Пусть у нас есть какой-то алгоритм $A$.
Рассмотрим его две модификации: $A_h$: кинуть монетку, если выпал орел, то запустить $A$, иначе кинуть монетку еще $100$ раз, после чего запустить $A$. $A_t$: кинуть монетку, если выпала решка, то запустить $A$, иначе кинуть монетку еще $100$ раз, после чего запустить $A$.
Если $o < 1/2$, то первый лучше, если $o > 1/2$, то второй лучше.

Понятно что тут есть алгоритм, лучший их обоих для любой монетки, но в общем случае существование универсального оптимального алгоритма совсем не очевидно.

 Профиль  
                  
 
 Re: Нечестная монетка
Сообщение27.03.2025, 14:09 


05/01/23
24
mihaild в сообщении #1680084 писал(а):
sirvff в сообщении #1680067 писал(а):
что это за "жадный алгоритм"? он точно работает в условиях п1, когда мы НЕ ЗНАЕМ реальное значение О ?
Нет, не работает, он для варианта с известным $o$.
Делает следующее. Пусть нам надо сгенерировать орла с вероятностью $p$ (изначально $1/2$). Бросаем монетку.
Если $o < p$ и выпал орел, то сразу говорим "орел". Если $o < p$ и выпала решка, то продолжаем бросать, теперь нужно сгенерировать орла с вероятностью $\frac{p - o}{1 - o}$.
Если $o > p$ и выпала решка, то сразу говорим "решка". Если $o > p$ и выпал орел, то продолжаем бросать, теперь нужно сгенерировать орла с вероятностью $\frac{p}{o}$.


ннуууу.... а для известного о он оптимален? тут видимо можно улучшить...

-- 27.03.2025, 14:12 --

Null в сообщении #1680083 писал(а):
Рассмотрим алгоритм: кидаем группами по $2k$ Если в очередной группе количество О и Р одинаково, то останавливаемся. Таких наборов $C^k_{2k}$ четное число - на половину выдаем Р, на вторую О. Назовем его $B_{2k}$
Матожидание $\frac{2k}{C^k_{2k}o^k(1-o)^k}$.
Сравните 10 бросков пропускаем потом $B_2$ и $B_4$. Разность матожиданий $=10+\frac{2}{2o(1-o)}-\frac{4}{6o^2(1-o)^2}$ меняет знак.


1. можно пытаться привести "универсально лучший", вдруг он есть разом для всех. вообще-то наверное можно почти все посл-сти кроме много одинаковых подряд попилить на 0-1, есть смысл привести алгосы, не содержашие очевидных улучшений хотя бы для начала.
2. можно брать интеграл по всему(равномерному) распределению
ну да. хорошее наблюдение. ещё бы связи с какими-то более известными задачами если найти, то можно и покопаться.

 Профиль  
                  
 
 Re: Нечестная монетка
Сообщение27.03.2025, 18:48 
Заслуженный участник


12/08/10
1718
А если такой жадный алгоритм:
$S_0$- пустое множество строк из "О" и "Р"
$S_{i+1}$ -дописываем к каждому слову из $S_i$ "О" и "Р"(количество слов удвоилось), потом берем пары слов с одинаковым количеством "О" и "Р" и относим их к разным вариантам выходных ответов и выкидываем их из $S_{i+1}$
Осталось не более $i+2$ слов(разные количества букв "Р") и их вероятность не больше $(\max(o;1-o))^{i+2}$ и матожидание алгоритма конечно.

 Профиль  
                  
 
 Re: Нечестная монетка
Сообщение27.03.2025, 18:55 
Заслуженный участник
Аватара пользователя


16/07/14
9529
Цюрих
Null, это вроде тот же самый итеративный алгоритм.

 Профиль  
                  
 
 Re: Нечестная монетка
Сообщение27.03.2025, 19:42 


05/01/23
24
Null в сообщении #1680121 писал(а):
А если такой жадный алгоритм:
$S_0$- пустое множество строк из "О" и "Р"
$S_{i+1}$ -дописываем к каждому слову из $S_i$ "О" и "Р"(количество слов удвоилось), потом берем пары слов с одинаковым количеством "О" и "Р" и относим их к разным вариантам выходных ответов и выкидываем их из $S_{i+1}$
Осталось не более $i+2$ слов(разные количества букв "Р") и их вероятность не больше $(\max(o;1-o))^{i+2}$ и матожидание алгоритма конечно.


нуу, даа, ну вот чо-нить про оптимальность этой штуки. может быть можно сделать "среднюю длину дерева" ещё меньше как-то по одной дописывая итп, крч B_i d в ваших терминах побыстрее собирать
пока к сожалению не доходят руки норм подумать

 Профиль  
                  
 
 Re: Нечестная монетка
Сообщение27.03.2025, 21:50 


05/01/23
24
Можно по поводу пункта 2 ещё подоказывать что-то в духе "если Х - редкая, то и sqrt(X) редкая"
на сам деле любопытно, насколько сложен тут в реальности ответ и что он значит

 Профиль  
                  
 
 Re: Нечестная монетка
Сообщение27.03.2025, 22:02 
Заслуженный участник
Аватара пользователя


16/07/14
9529
Цюрих
Пусть $N(x, y)$ - количество строк с $x$ орлами и $y$ решками, на которых алгоритм говорит "орел", $M(x, y)$ - на которых говорит решка.
Для простоты пока предположим, что $N(x + 1, y) \cdot N(x, y + 1) = 0$ и $M(x + 1, y) \cdot M(x, y + 1) = 0$ (пару строк $(x + 1, y)$ и $(x, y + 1)$ можно заменить на $(x, y)$ с сохранением вероятности и уменьшением ожидаемой длины - не факт, что это получится сделать в дереве, но пока проигнорируем).
Тогда вроде бы $\forall x, y: N(x, y) = M(x, y)$. Ожидаемая длина при этом получается $\sum\limits_{x, y} N(x, y) o^x \cdot (1 - o)^y$.
Алгоритм выше соответствует варианту $N(x, y) = 1$ для случая, когда последняя единица в двоичных записях $x$ и $y$ общая, а все остальные не совпадают.
Вопрос - можно ли найти какие-то простые ограничения на $N$, при которых существует соответствующее разбиение дерева?

 Профиль  
                  
 
 Re: Нечестная монетка
Сообщение29.03.2025, 11:13 
Заслуженный участник
Аватара пользователя


11/03/08
10184
Москва
"Фабрика честного жребия"
Пусть имеется монета, выдающая "О" с вероятностью $p\ne \frac 1 2$ и "Р" с вероятностью $q=1-p$ (вероятности известны или оцениваются по выборке)
Тогда, сжав сгенерированное так слово "ОРООРОРРРООРОР..." или подобное алгоритмом арифметического сжатия, получим битовую последовательность. По мере роста сжимаемого текста степень сжатия приближается к теоретически максимальной, а сжатый текст - к последовательности равновероятных и независимых битов (а случайны они в силу случайности исходного текста).
Процент выхода готовой продукции зависит от того, насколько вероятности для исходной монеты отличны от одной второй.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 23 ]  На страницу Пред.  1, 2

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



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

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


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

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