Имитация честного кубика с предвзятым штампом

18

Учитывая смещенную N стороннюю матрицу, как можно случайное число в диапазоне [1,N]равномерно генерировать N ] ? Распределение вероятностей граней матрицы неизвестно, все, что известно, это то, что каждая грань имеет ненулевую вероятность и что распределение вероятности одинаково для всех бросков (в частности, броски независимы). Это очевидное обобщениесправедливых результатов с несправедливой смертью.

Если выразить это в терминах информатики, у нас есть оракул, представляющий броски кубика: D:N[1,N] такой, что pi=P(D(k)=i) равен нулю и не зависит от k . Мы ищем детерминированный алгоритм A который параметризован D (т. Е. A может вызывать D ) так, чтобы P(A()=i)=1/N . Алгоритм должен завершаться с вероятностью 1, то есть вероятность того, что A делает больше, чем n вызовов D должна сходиться к 0 при n .

Для N=2 (имитировать честную монету из подбрасывания монеты пристрастной монетой) существует хорошо известный алгоритм:

  • Повторяйте «дважды», пока два броска не приведут к определенным результатам ((головы, хвосты) или (хвосты, головы)). Другими словами, цикл для k=0.. до тех пор, пока D(2k+1)D(2k)
  • Вернуть 0, если последняя пара бросков была (головы, хвосты) и 1, если это было (хвосты, головы). Другими словами, вернуть D(2k) гдеk - индекс, при котором цикл был завершен.

Упрощенный способ сделать беспристрастный кристалл из предвзятого состоит в том, чтобы использовать метод смещения монеты с переворотом, чтобы построить честную монету и построить честный кристалл с выборкой отклонения, как в Unbiasing of sequence . Но является ли это оптимальным (для общих значений распределения вероятностей)?

В частности, мой вопрос: что такое алгоритм, который требует наименьшее ожидаемое количество обращений к оракулу ? Если набор достижимых ожидаемых значений открыт, какова нижняя граница и что представляет собой класс алгоритмов, сходящихся к этой нижней границе?

В случае, если разные семейства алгоритмов оптимальны для разных распределений вероятности, давайте сосредоточимся на почти честных кубиках: я ищу алгоритм или семейство алгоритмов, оптимальных для распределений, таких что i,|pi1/N|<ϵ для некоторых ϵ>0 .

Жиль "ТАК - перестань быть злым"
источник
Обратите внимание, что важно тщательно определить оптимальный, так как, например, вам может быть предоставлен совершенно справедливый кубик или кубик с , p i = ϵ / ( N - 1 ) для i > 1 или любым другим вид умереть. Оптимальная схема для честного кубика требует только одного броска, тогда как для несправедливого примера оптимальная схема требует многих. Кроме того, супремум оптимальных по всем возможным смещенным штампам, вероятно, не ограничен. Поэтому вы можете ввести параметр и предположить, что max i p iϵp1=1ϵpi=ϵ/(N1)i>1maxipi1ϵ например.
Усул
@usul Я не понимаю твой комментарий. Существуют более эффективные алгоритмы для некоторых значений (например, если i , p i = 1 / N ), но я прошу только алгоритмы, которые не зависят от ( p i ) . Какой смысл ϵ ? pii,pi=1/N(pi)ϵ
Жиль "ТАК - перестать быть злым"
Как вы измеряете эффективность алгоритма, который не зависит от ? Вероятно, для любого такого алгоритма не существует верхней границы ожидаемого количества требуемых вызовов, если взять мой пример смещенного штампа с ϵ 0 . Это то, что я имею в виду под «супремумом оптимального ... вероятно, не ограничен». Итак, если все алгоритмы могут требовать сколь угодно много бросков в ожидании, как мы решим, какой из них лучше? (pi)ϵ0
Усул
@usul Конечно, нет верхней границы количества бросков, но я спрашиваю об ожидаемом значении (то есть среднем количестве бросков). Для данного распределения ожидаемое значение для алгоритма, который создает справедливую монету и использует ее для выборки отклонения, конечно, не так ли? Это правда, что ожидание зависит от распределения, поэтому разные (семейства) алгоритмы могут быть оптимальными для разных распределений. Если это так, скажем, мне интересны почти честные кости. (pi)
Жиль "ТАК - перестать быть злым"
Не совсем точно вопрос, но вы бы хотели искать только результат, близкий к равномерному (в / общее расстояние изменения)? Если это так, в зависимости от гарантии, которую вы запрашиваете в исходном дистрибутиве, это изучается в недавней статье (в представлении) под названием «средство для улучшения выборки для единообразия», в которой, в частности, показано, что вы можете получить число розыгрышей независимо от N чтобы улучшить от 1 расстояние е , чтобы расстояние х ' . 1N1εε
Клемент С.

Ответы:

3

Следующая статья отвечает на близкий вариант этого вопроса: Эффективное построение несмещенной случайной последовательности, Элиас, 1972 .

Похоже, возникает следующий вопрос: получив доступ к этому смещенному независимому источнику, выведите последовательность случайных чисел в (обратите внимание на отличие от вашего вопроса, в котором запрашивается только один выходной символ). По мере того, как длина желаемого результата уходит в бесконечность, «эффективность» схемы в статье (которая выглядит как естественное обобщение фон Неймана) становится равной 1 , что означает, я полагаю, что вход с энтропией h преобразуется в выход энтропии приближается к ч[1,N]1hh .

Вопрос выглядит гораздо лучше, когда он формулируется таким образом, а не запрашивает одну выходную цифру, потому что, например, если мы рисуем выборок и в результате получаем вывод с большим количеством информации (например, все N входных символов различны) затем мы можем использовать всю эту информацию для получения множества выходных символов, тогда как при заданном здесь вопросе любая информация, помимо той, которая использовалась для получения одного выходного символа, теряется.NN

Я полагаю, что схема многократно берет отрисовок, просматривает последовательность и отображает в ней некоторые выходные данные или пустую строку. Возможно, есть способ улучшить схему вашего вопроса, посмотрев на префиксы и остановившись, если у нас «достаточно» информации для вывода символа? Я не знаю.N

усул
источник
Я не искал последующую работу или работу со ссылкой на газету, поэтому я не знаю, но, возможно, кто-то улучшил схему, предложил другую, ответил на ваш вопрос и т. Д.
usul
2

Метод, который вы описываете для обобщает. Мы используем, что все перестановки [ 1 .. N ] одинаково вероятны даже с смещенным кристаллом (так как броски независимы). Следовательно, мы можем продолжать вращаться, пока не увидим такую ​​перестановку, как последние N бросков, и вывести последний бросок.N=2[1..N]N

Общий анализ сложен; однако ясно, что ожидаемое число бросков быстро возрастает в так как вероятность увидеть перестановку на любом данном шаге мала (и не зависит от шагов до и после, а значит, хитрая). Это является большим , чем 0 при фиксированном N , однако, поэтому процедура завершается почти наверняка (то есть с вероятностью 1 ).N0N1

Для фиксированного мы можем построить цепь Маркова на множестве векторов Париха, сумма которых равна N , суммируя результаты последних N бросков, и определить ожидаемое количество шагов, пока мы не достигнем ( 1 , , 1 ) для первый раз . Этого достаточно, поскольку все перестановки, имеющие общий вектор Париха, одинаково вероятны; таким образом цепочки и вычисления проще.NNN(1,,1)

Предположу , что мы в состоянии с Й п я = 1 V яN . Тогда вероятность получения элемента i (т. Е. Следующий бросок равен i ) всегда определяется какv=(v1,,vN)i=1nviNii

.Pr[gain i]=pi

С другой стороны, вероятность удаления элемента из истории определяется выражениемi

Prv[drop i]=viN

всякий раз , когда 0 в противном случае) именно потому , что все перестановки с Парих вектора V с равной вероятностью. Эти вероятности независимы (так как броски независимы), поэтому мы можем вычислить вероятности перехода следующим образом:i=1nvi=N0v

Pr[v(v1,,vj+1,,vN)]={Pr[gain j],v<N0, else,Pr[v(v1,,vi1,vj+1,,vN)]={0,v<Nvi=0vj=NPrv[drop i]Pr[gain j], else andPr[vv]={0,v<Nvi0Prv[drop i]Pr[gain i], else;

все остальные вероятности перехода равны нулю. Единственное поглощающее состояние - это , вектор Париха всех перестановок из [ 1 ... N ] .(1,,1)[1..N]

Для полученная цепь Маркова ¹ имеет видN=2

Markov chain for N=2
[ источник ]

с ожидаемым количеством шагов до поглощения

Esteps=2p0p12+i3(p0i1p1+p1i1p0)i=1p0+p02p0p02,

используя для упрощения, что . Если сейчас, как и предполагалось, р 0 = 1p1=1p0для некоторогоϵ[0,1p0=12±ϵ, тоϵ[0,12)

.Esteps=3+4ϵ214ϵ2

Для и равномерных распределений (лучший случай) я выполнил вычисления с помощью компьютерной алгебры²; поскольку пространство состояний быстро взрывается, большие значения трудно оценить. Результаты (округленные в большую сторону)N6

NormalPlot LogPlot
Сюжеты показывают как функция N ; слева регулярный, а справа логарифмический график.EstepsN

Рост кажется экспоненциальным, но значения слишком малы, чтобы давать хорошие оценки.

Что касается устойчивости к возмущениям мы можем взглянуть на ситуацию для N = 3 :piN=3

Expected number of steps for N=3 and different choices
Сюжет показывает в зависимости от p 0 и p 1 ; естественно, p 2 = 1 - p 0 - p 1 .Estepsp0p1p2=1p0p1

Предполагая, что аналогичные изображения для большего (ядро дает сбой при вычислении символических результатов даже для N = 4 ), ожидаемое количество шагов кажется достаточно стабильным для всех, кроме самых экстремальных вариантов (почти все или нет массы при некотором значении p i ).NN=4pi

Для сравнения, имитация монеты с смещением (например, путем присвоения результатов кубика 0 и 1 как можно более равномерно), использование этого для симуляции монеты и, наконец, выборка побитовых отбраковок требует максимумϵ01

2logN3+4ϵ214ϵ2

кубики в ожидании - вы должны придерживаться этого.


  1. Поскольку цепочка поглощает в края, на которые намекается серый цвет, никогда не пересекаются и не влияют на вычисления. Я включаю их только для полноты и наглядности.(11)
  2. Реализация в Mathematica 10 ( Записная книжка , Голый Источник ); извините, это то, что я знаю для такого рода проблем.
Рафаэль
источник
1

Просто быстрый комментарий по делу . Возьмите какое-нибудь большое число m и образец m бросков матрицы. Если у вас есть k голов, вы можете извлечь журнал ( мN=2mmklog(mk)p

k=0mpk(1p)mk(mk)log(mk)mh(p).
k=pmlog(mk)mh(k/m)mh(p)

NH(p). These algorithms are only optimal in the limit, and there might be algorithms reaching the limit faster than these. In fact, I neglected to compute the speed of convergence - it might be an interesting exercise.

Yuval Filmus
источник
1

I would hazard the following answer.

The specific case of 2 you mentioned above is the specific case of expanding (p+q)2 (where p is prob of head and q prob of tail) which gives you a term 2pq This means you can get pq for one case and qp for the other case. You will need to repeat sampling until you see either pq or qp (head-tail or tail-head) Using them as simulation, you will give equal probability.

When N=3 you have the expansion (p+q+r)3 which gives you the term pqr. In this case, you do the same thing, sampling until you see all 3 outcomes q, p, r in some order in 3 consecutive trials.

The same thing apply for the general case. Thinking carefully, I have to say the case of 2 is the best case where one can work things out in the expansion. When N=3 there are 6 different sequences for pqr and there are many other terms in the expansion. I would feel quite uncomfortable with other terms where there are many more outcomes.

.

Extra:

This makes me think about the idea of simply sampling a lot to estimate the probability of each outcome of the dice. In this simplest case of one layer model with no hidden layer (a known model), we can work out a bound to conclude that the estimation converges quickly. In fact Chernoff bound shows us that the error goes down exponentially as sampling increases (linearly).

Now that a good estimation of the probabilities for each side of the dice is known, there are many options. One option is that we can do the expansion above again, but this time we can potentially use many other terms in the expansion that have the same value as i=1i=npi (or any term that you use as based sequence). This will be a bit more efficient because more terms in the expansion will be used. But I admit I don't know if this will result in the smallest number of calls to the oracle to have a guarantee on whatever preconditions (such as confidence parameter), if they are given.

Nevertheless, this approach is an answer to different flavor of the question. The question asks for guaranteed perfect unbiased-ness at the cost of potentially large sampling (though low prob). This approach only uses finite sampling with bound on confidence parameter. So I don't think this approach is appropriate to this question even though it is very interesting.

InformedA
источник