Algoritmo para el despliegue de una infinita cara ponderado de morir

Question

Si quería tener un morir que rodó, por ejemplo:

| Roll | Prob (in %) |
|------|-------------|
| 1    | 60          |
| 2    | 25          |
| 3    | 12          |
| 4    | 4           |
| 5    | 1           |
| 6    | 0.2         |
| 7    | 0.04        |
| ...  | ...         |

(Estos números son la parte superior de mi cabeza, y no necesariamente seguir un algoritmo simple)

¿Qué tipos de algoritmos puedo describir mediante programación así que pude rollo¹ número exponencialmente con la disminución de las probabilidades?

Estaba pensando que si me genera una tabla de probabilidades mediante una curva exponencial yo no sería capaz de garantizar mi función resuelve; Si yo empecé 1 roll y tuvo un par de fallos en una fila, yo nunca podría tener un éxito rollo; y yo no se puede iniciar en el otro extremo en el trabajo de mi camino hacia un rollo de 1 con una probabilidad de 100%, porque es infinitamente larga y no hay ningún final para que se inicie en².

Entonces, ¿cómo puedo escoger un número que a partir de esta distribución? Si es posible, la distribución exponencial o cuadráticamente de la caries, pero cualquier distribución que podría modelo algo como:

1. The number of rooms in a house
2. The number of items in a treasure chest
3. The number of eyeballs on a mutant

Un final, pero no es necesario el punto de que se puede considerar es la facilidad de que el algoritmo puede ser modificado para estirar/acortar la curva, para hacer números bajos a menos/más probable.

---

^{1: Restricción de equipo de precisión; un rollo de MAXINT o lo que sería en la práctica el máximo
2: de Nuevo, en la práctica, una computadora puede hacerlo porque hay un menor de flotación para la probabilidad, pero que sería terriblemente ineficiente. El caso promedio tomaría miles de millones de rollos de papel, mientras que un buen algoritmo probablemente podría hacer en O(1) por elegir sólo una fracción y su resolución.}

Answer 1

El enfoque estándar aquí es el uso de la CDF de su distribución, que se define en $\mathbb{R}$ (sin importar el apoyo de su distribución).

Para cualquier finito de distribución, generalmente utiliza cumsum para calcular el CDF; infinidad de distribución, se necesita de una fórmula explícita para $F:\mathbb{R}\rightarrow[0,1]$ donde $F(x)=\mathbb{P}[X\leq x]$.

Para una distribución discreta, la CDF será un derecho continuo de la función de paso de, por ejemplo, para la distribución geométrica (imagen de Wikipedia):

Una vez que usted tiene su CDF, dibujar un uniforme normal de la variable aleatoria $u$~$U[0,1]$. Necesitamos invertir $F$, la cual se realiza mediante la selección de las menos $x$ s.t. $f(x)$ (la densidad) se define y $F(x)\geq u$, es decir, elegimos la $x$ que obtiene cerca de $u$ sin pasar por debajo.

Para ver por qué, considere la posibilidad de un simple tirón de la moneda, representado por un Bernoulli(1/4) de la variable. Queremos ir de $u\in[0,1]$ a algo que muestra 0 de un cuarto de hora y 1 el de los otros tres trimestres. Tenga en cuenta que nuestra distribución acumulativa es $F(x)=\frac{1}{4}\mathbb{1}[x\geq 0] + \frac{3}{4}\mathbb{1}[x \geq 1]$ donde $\mathbb{1}[\cdot]$ es un indicador de la función toma el valor 1 si el argumento es true, 0 en caso contrario.

Por la regla que he descrito, elegiremos $0 \Leftrightarrow u<\frac{1}{4}$$1 \Leftrightarrow u \geq \frac{1}{4}$; tenga en cuenta que esto significa que vamos a recoger 0 una cuarta parte del tiempo, y 1 de tres cuartos, que es lo que queríamos.

Poner en una forma más, la probabilidad de golpear a cualquier valor dado es dado por la distancia en la $y$ eje entre los saltos en el CDF en ese valor. Distancias en la $y$ eje corresponden a las probabilidades de $U[0,1]$ varia, por lo que para que coincida con la probabilidad de un valor, se debe asignar ese valor a $u$ siempre $u$ cae en la brecha.

Answer 2

Si usted tiene un $f: \mathbb{N} \rightarrow [0,1]$ función tal que $n$ está de un lado y $f(n)$ la probabilidad de obtener ese lado, y si somos capaces de producir una función de $g: \mathbb{N} \rightarrow [0,1]$ tal que $g$ es invertible y:

$$ g(n) = \sum_{i=1}^n f(n) $$

Después podría producir un float aleatorio $ k\in [0,1]$ y regresar $g^{-1}(k)$

Edit: Como se señaló, no podemos esperar que el $g^{-1}(k)$ a existir. Sin embargo, tal vez si lo imagina por un minuto que $g$ se define en $\mathbb{R} \ge 0 $, y si tenemos suerte y $g'(x) \ge 0, \forall x \in \mathbb{R} \ge 0 $, entonces sólo podemos hacer $\left\lfloor g^{-1}(k)\right\rfloor$.

Answer 3

Estas probabilidades son descritos por una Distribución Geométrica. Para que uno, la probabilidad de resultado $n$ está dada por: $$P(X = n) = (1-p)^{n-1}p$$ donde $p$ es el "ritmo exponencial".

Para muestra de esta distribución (o de otros), puede hacer lo siguiente. Puede elegir de entre un uniforme de $[0,1]$ variable aleatoria y, a continuación, busque en el valor inverso de ese resultado a través de la CDF. La CDF para esta distribución es $$P(X \leq n) = 1 - (1-p)^n$$ Así que aquí puedes encontrar la primera $n$ s.t. que la función es mayor que el uniforme resultado que usted eligió.

Answer 4

La inversa de la transformación de los métodos mencionados por dos de las otras respuestas es uno de los más elegantes para la generación de números aleatorios sobre las distribuciones. La distribución exponencial tiene una muy simple inverse CDF que hace numérico generación fácil; se puede aplicar el techo de la función para obtener toda la-número de salidas.

Un algoritmo alternativo que se puede utilizar con el real dados sobre una mesa, es simplemente "roll de una n-colindado mueren; si el número de rodó es menor o igual a m , a continuación, se vuelve a tirar, de lo contrario, detener; el resultado es el número de rollos antes de detenerse.", que obedece a una distribución geométrica. Esto da un resultado de 1 con una probabilidad de $1 - {m\over n}$, 2 con probabilidad de ${m \over n} \left(1 - {m \over n}\right)$, 3 con probabilidad de ${m \over n}^2 \left(1 - {m \over n}\right)$, etc. Se espera una (promedio) resultado de $n \over {n - m}$, que es el mismo que el número esperado de rodillos para obtener el resultado. El procedimiento termina con una probabilidad de 1, porque para cualquier probabilidad de $p$, no importa lo pequeño que sea, hay un número finito de rollos $r$ tales que la probabilidad de no terminar después de $r$ rollos es de menos de $p$.