Dado un dado sesgado del lado , ¿cómo puede generarse un número aleatorio en el rango manera uniforme? La distribución de probabilidad de las caras del dado no se conoce, todo lo que se sabe es que cada cara tiene una probabilidad distinta de cero y que la distribución de probabilidad es la misma en todos los lanzamientos (en particular, los lanzamientos son independientes). Esta es la generalización obvia de los resultados justos con un dado injusto .
Poniendo esto en términos informáticos, tenemos un oráculo que representa las tiradas del dado: modo que es distinto de cero e independiente de . Estamos en busca de un algoritmo determinista que está parametrizada por (es decir, pueden hacer llamadas a ) de tal manera que . El algoritmo debe terminar con la probabilidad 1, es decir, la probabilidad de que haga más de llamadas a debe converger a como .
Para (simule una moneda justa de monedas con una moneda sesgada), hay un algoritmo bien conocido:
- Repita "voltear dos veces" hasta que los dos lanzamientos arrojen resultados distintos ((cara, cruz) o (cola, cara)). En otras palabras, bucle para hasta
- Devuelve 0 si el último par de vueltas fue (caras, colas) y 1 si fue (colas, caras). En otras palabras, devuelva donde es el índice en el que se terminó el ciclo.
Una forma simplista de hacer un dado imparcial a partir de uno sesgado es usar el método de deshacer el cambio de moneda para construir una moneda justa, y construir un dado justo con muestreo de rechazo, como en Unbiasing de secuencias . Pero, ¿es esto óptimo (para valores genéricos de la distribución de probabilidad)?
Específicamente, mi pregunta es: ¿qué es un algoritmo que requiere el menor número esperado de llamadas al oráculo ? Si el conjunto de valores esperados alcanzables está abierto, ¿cuál es el límite inferior y cuál es una clase de algoritmos que converge hacia este límite inferior?
En caso de que diferentes familias de algoritmos sean óptimas para diferentes distribuciones de probabilidad, centrémonos en dados casi justos: estoy buscando un algoritmo o una familia de algoritmos que sea óptimo para distribuciones tales que para algunos .ϵ > 0
fuente
Respuestas:
El siguiente artículo responde a una variante cercana de esta pregunta: La construcción eficiente de una secuencia aleatoria imparcial, Elias 1972 .
La pregunta parece ser esta: dado el acceso a esta fuente independiente sesgada, genera una secuencia de números aleatorios en (observe la diferencia de su pregunta en la que solo se solicita un símbolo de salida). A medida que la longitud del resultado deseado llega al infinito, la "eficiencia" del esquema en el documento (que parece una generalización natural de von Neumann) va a[1,N] , lo que significa, creo, que una entrada con entropía h se convierte en Una salida de entropía que se aproxima a h .1 h h
La pregunta parece comportarse mucho mejor cuando se formula de esta manera, en lugar de solicitar un solo dígito de salida, porque, por ejemplo, si dibujamos muestras y terminamos con una salida con mucha información (por ejemplo, todos los N símbolos de entrada son distintos) , entonces podemos usartodaesa información para producir muchos símbolos de salida, mientras que con la pregunta como está formulada aquí, cualquier información más allá de la utilizada para producir un símbolo de salida se desperdicia.N N
Creo que el esquema toma sorteos repetidamente , mira la secuencia y le asigna algunas salidas o la cadena vacía. ¿Quizás haya una manera de mejorar el esquema de su pregunta mirando prefijos y deteniéndose si tenemos información "suficiente" para generar un símbolo? No lo sé.N
fuente
El método que describe para generaliza. Usamos que todas las permutaciones de [ 1 .. N ] son igualmente probables incluso con un dado sesgado (ya que las tiradas son independientes). Por lo tanto, podemos seguir rodando hasta que veamos una permutación como las últimas N tiradas y la salida de la última tira.N=2 [1..N] N
Un análisis general es complicado; Sin embargo, está claro que el número esperado de lanzamientos crece rápidamente en ya que la probabilidad de ver una permutación en cualquier paso dado es pequeña (y no independiente de los pasos anteriores y posteriores, por lo tanto, difícil). Sin embargo, es mayor que 0 para N fijo , por lo que el procedimiento termina casi con seguridad (es decir, con probabilidad 1 ).N 0 N 1
Para fijo podemos construir una cadena de Markov sobre el conjunto de vectores Parikh que suman ≤ N , resumiendo los resultados de los últimos N rollos, y determinar el número esperado de pasos hasta llegar a ( 1 , ... , 1N ≤N N para el primera vez(1,…,1) . Esto es suficiente ya que todas las permutaciones que comparten un vector Parikh son igualmente probables; Las cadenas y los cálculos son más simples de esta manera.
Supongamos que estamos en el estado de con Σ n i = 1 v i ≤ N . Entonces, la probabilidad de obtener un elemento i (es decir, el próximo lanzamiento es iv=(v1,…,vN) ∑ni=1vi≤N i i ) siempre viene dada por
Por otro lado, la posibilidad de soltar un elementoi de la historia está dada por
siempre que (y 0 de otro modo), precisamente porque todas las permutaciones con Parikh-vector v son igualmente probables. Estas probabilidades son independientes (ya que los rollos son independientes), por lo que podemos calcular las probabilidades de transición de la siguiente manera:∑ni=1vi=N 0 v
todas las demás probabilidades de transición son cero. El único estado de absorción es , el vector Parikh de todas las permutaciones de [ 1 .. N ] .(1,…,1) [1..N]
Para la cadena de Markov resultante esN=2
[ fuente ]
con el número esperado de pasos hasta la absorción
utilizando para simplificar que . Si ahora, como se sugiere, p 0 = 1p1=1−p0 para algunosϵ∈[0,1p0=12±ϵ , entoncesϵ∈[0,12)
Para y distribuciones uniformes (el mejor de los casos) he realizado los cálculos con álgebra de computadora²; Como el espacio de estado explota rápidamente, los valores más grandes son difíciles de evaluar. Los resultados (redondeados hacia arriba) sonN≤6
Mostrar parcelas en función de N
El crecimiento parece ser exponencial, pero los valores son demasiado pequeños para dar buenas estimaciones.
En cuanto a la estabilidad frente a las perturbaciones de la , podemos observar la situación para N = 3 :pi N=3
La trama muestra en función de p 0 y p 1 ; naturalmente, p 2 = 1 - p 0 - p 1 .
Suponiendo imágenes similares para más grande (el núcleo se bloquea al calcular resultados simbólicos incluso para N = 4 ), el número esperado de pasos parece ser bastante estable para todas las opciones excepto las más extremas (casi todas o ninguna masa en algún p i ).N N=4 pi
Para comparar, simular una moneda imparcial (por ejemplo, asignando los resultados del dado a 0 y 1 de la manera más uniforme posible), usar esto para simular una moneda justa y, finalmente, realizar un muestreo de rechazo en bits.ϵ 0 1
los dados mueren en expectativa, probablemente deberías quedarte con eso.
fuente
Solo un comentario rápido sobre el caso . Tome un número grande de m , y muestree m tiros del dado. Si tienes k cabezas, entonces puedes extraer log ( mN=2 m m k bits. Suponiendo que el dado estásesgadop, la cantidad promedio de información es
m ∑ k=0pk(1-p)m-k ( mlog(mk) p
Para obtener esta estimación, utilice el hecho de que la variable binomial se concentra alrededor dek=pmjunto con elregistro deestimación ( m
Puede usar el mismo método para general , y probablemente obtendrá el mismo H ( → p ) . Estos algoritmos solo son óptimos en el límite, y puede haber algoritmos que lleguen al límite más rápido que estos. De hecho, olvidé calcular la velocidad de convergencia; podría ser un ejercicio interesante.N H(p⃗ )
fuente
Me arriesgaría a la siguiente respuesta.
.
Extra:
Esto me hace pensar en la idea de simplemente muestrear mucho para estimar la probabilidad de cada resultado del dado. En este caso más simple de modelo de una capa sin capa oculta (un modelo conocido), podemos calcular un límite para concluir que la estimación converge rápidamente. De hecho, el límite de Chernoff nos muestra que el error disminuye exponencialmente a medida que aumenta el muestreo (linealmente).
Sin embargo, este enfoque es una respuesta a un sabor diferente de la pregunta. La pregunta pide una imparcialidad perfecta garantizada a costa de un muestreo potencialmente grande (aunque de baja probabilidad). Este enfoque solo utiliza muestreo finito con límite en el parámetro de confianza. Por lo tanto, no creo que este enfoque sea apropiado para esta pregunta aunque sea muy interesante.
fuente