¿Lo que ' s el nombre de esta distribución discreta (ecuación recursiva de diferencia) deriva?

Question

Me encontré con esta distribución en un juego de ordenador y quería aprender más acerca de su comportamiento. Se trata de la decisión de si un determinado evento debe ocurrir después de un número determinado de las acciones del jugador. Los detalles más allá de esto no son relevantes. Parece aplicable a otras situaciones, y me pareció interesante porque es fácil de calcular y se crea una cola larga.

Cada paso $n$, el juego genera un número aleatorio uniforme $0 \leq X < 1$. Si $X < p(n)$, entonces se activa el evento. Después del evento, una vez que se produce, el juego se reinicia $n = 0 $ y se ejecuta a través de la secuencia de nuevo. Sólo estoy interesado en uno de ocurrencia del evento, para este problema, ya que representa la distribución en la que el juego está utilizando. (También, cualquier pregunta con respecto a los casos múltiples se pueden contestar con una sola aparición modelo).

El principal de la "anormalidad" de aquí es que la probabilidad de parámetros en esta distribución se incrementa con el tiempo, o dicho de otro modo, el umbral se eleva a lo largo del tiempo. En el ejemplo de cambios de forma lineal, pero supongo que otras normas aplicables. Después de $n$ pasos o acciones por parte del usuario,

$$ p(n) = kn $$

para algunas constantes $0 < k < 1$. En un cierto punto de $n_{\max} $, obtenemos $p(n_{\max}) \geq 1 $. El evento es simplemente garantizado a ocurrir en ese paso.

Yo era capaz de determinar que

$$ f(n) = p(n)\left[1 - F(n - 1)\right] $$ y $$ F(n) = p(n) + F(n-1)\left[1 - p(n)\right] $$ para PMF $f(n)$ y el CDF $F(n)$. En breve, la probabilidad de que el evento será en el $n$th paso es igual a la probabilidad de $p(n)$, menor la probabilidad de que esto ya ha sucedido en cualquier paso anterior.

Aquí está una parcela de nuestro amigo de Monte Carlo, para la diversión, con $k \approx 0.003$. La mediana de las obras a 21 y tiene un promedio de 22.

Esto es aproximadamente equivalente a un primer orden de la diferencia de la ecuación de procesamiento de señal digital, que es mi fondo, y por lo que he encontrado que bastante de la novela. También estoy intrigado por la idea de que $p(n)$ podrían variar de acuerdo a cualquier fórmula.

Mis preguntas:

1. ¿Cuál es el nombre de esta distribución, si tiene una?
2. Es allí cualquier manera de obtener una expresión para $f(n)$ sin referencia a $F(n)$?
3. Hay otros ejemplos de discretos recursiva distribuciones como este?

Ediciones Aclaró proceso de generación de números aleatorios.

Answer 1

En un sentido, lo que hemos hecho es caracterizar todosno negativos valor entero de las distribuciones.

Vamos a dejar de lado la descripción de los procesos aleatorios por un momento y centrarse en las recursiones en la pregunta.

Si $f_n = p_n (1 - F_{n-1})$, entonces, ciertamente, $F_n = p_n + (1-p_n) F_{n-1}$. Si queremos volver a escribir este segundo recursividad en términos de la la supervivencia de la función $S_n = 1 - F_n = \mathbb P(T > n)$ (donde $T$ ha distribución $F$), tenemos algo muy sugerente y fácil de manejar. Claramente, $$ S_n = 1 - F_n = (1-p_n) S_{n-1} \>, $$ y así $$ S_n = \prod_{k=0}^n (1-p_k) \> . $$ Así, mientras nuestra secuencia $(p_n)$ toma valores en $[0,1]$ y hace no converge muy rápidamente a cero, entonces vamos a obtener un válido supervivencia función (es decir, monótonamente decreciente a cero, como se $n \to \infty$).

Más específicamente,

Proposición: Una secuencia $(p_n)$ tomando valores en $[0,1]$ determina la distribución de los números enteros no negativos si y sólo si $$ -\sum_{n=0}^\infty \log(1-p_n) = \infty \>, $$ y todas las distribuciones tienen una secuencia correspondiente (aunque puede no ser la única).

Por lo tanto, la recursividad escrito en la pregunta es completamente general: Cualquier entero no negativo valorado de distribución tiene una secuencia correspondiente a $(p_n)$ tomando valores es $[0,1]$.

Sin embargo, el recíproco no es cierto; es decir, hay secuencias de $(p_n)$ con valores en $[0,1]$ que no corresponden a una distribución válido. (En particular, considere la posibilidad de $0 < p_n < 1$ for all $n \leq N$ and $p_n = 0$ for $n > N$.)

Pero, espere, aún hay más!

Hemos insinuado una conexión para el análisis de supervivencia y vale la pena explorando un poco más profundamente. En el clásico análisis de supervivencia con un absolutamente continuas de distribución de $F$, y la correspondiente densidad de $f$, el función de riesgo se define como $$ h(t) = \frac{f(t)}{S(t)} \>. $$

El acumulado de peligro es entonces $\Lambda(t) = \int_0^t h(s) \,\mathrm d$ s y un simple análisis de derivados de la muestra que $$ S(t) = \exp(-\Lambda(t)) = \exp\Big(-\int_0^t h(s) \,\mathrm d s\Big)\>. $$ A partir de esto, podemos dar de inmediato una caracterización de la admisibilidad de una función de riesgo: es cualquier función medible $h$ tal que $h(t) \geq 0$ todos los $t$ y $\int_0^t h(s) \,\mathrm d s \uparrow \infty$ $t \to \infty$.

Tenemos una similar recursividad para la supervivencia de la función de la anterior, haciendo notar que, para $t > t_0$ $$ S(t) = e^{-\int_{t_0}^t h(s) \,\mathrm d s} S(t_0) \>. $$

Observe en particular que podríamos eligió $h(t)$ a ser definidas a trozos constante con cada pieza que se va de la anchura de 1 y tal que la integral converge hacia el infinito. Esto daría lugar a una función de sobrevivencia $S(t)$ que coincide con cualquier discretos entero no negativo con valores de uno en cada entero positivo.

Conectando con el caso discreto

Para que coincida con un discretas deseados $S(n)$ a cada número entero, debemos elegir un función de riesgo que es seccionalmente constante tal que $$ h(t) = h_n = -\log(1-p_n)\>, $$ en $(n-1,n]$. Esto proporciona una segunda prueba de las condiciones necesarias para que la secuencia de $(p_n)$ a definir una distribución válido.

Tenga en cuenta que, para los pequeños $p_n$, $-\log(1-p_n) \approx p_n = f_n / S_{n-1}$ que proporciona una heurística de la conexión entre la función de riesgo de un distribución continua y la distribución discreta con la coincidencia de la la supervivencia de la función en los números enteros.

Postscript: Como nota final, el ejemplo $p_n = k n$ en la pregunta ¿ no satisfacen las condiciones necesarias sin una modificación adecuada a $f_n$ en $n = \lceil k^{-1} \rceil$ y ajuste de $f_n = 0$ todos los $n > \lceil k^{-1} \rceil$.

Answer 2

En el caso de $p(n) = p < 1$, tenemos algunas propiedades conocidas. Podemos resolver la relación de recurrencia

$$ F(n) = p + F(n-1)(1-p); \; F(0) = p $$

tiene la solución

$$ F(n) = P(N \le n) = 1- (1-p)^{n+1} $$ que es la distribución geométrica. Está bien estudiado.

El caso más general de $p(n)$ probablemente puede no ser calculada en forma cerrada, y por lo tanto probablemente no tiene una distribución conocida.

Otros casos:

1. $p(n) = \frac{p}{n}; \; p<1; \;F(0) = p$ tiene solución $$ F(n) = 1 - \frac{(1-p)\Gamma( n + 1 -p)}{\Gamma( 1-p)\Gamma(n+1)} $$ que no es comúnmente conocido distribución.
2. Definir $S(n) = 1-F(n)$ (conocida como la función de sobrevivencia en las estadísticas), la recurrencia de la relación anterior se reduce a la forma más simple: $$S(n) =\left(1 - p(n) \right) S(n-1)$$
3. A partir de su ejemplo, aparece una función $p(n)$ que aumenta en $n$. Su elección $p(n) = kn$ no es muy grande analíticamente debido a la rotura en $p>1$. Los matemáticos y estadísticos prefieren suavizar las cosas. Así que me propongo $$p(n) = 1 - \frac{(1-p)}{n+1} \; p<1$$ que $p(0) = p$ y converge a 1. La solución de la recurrencia de la relación con ese $p(n)$, tiene la buena analítico forma: $$ F(n) = 1 - \frac{ (1-p)^{n+1} }{ n! } $$ Considere la posibilidad de $S(n) = 1 - F(n) = \frac{ (1-p)^{n+1} }{ n! }$. Un conocido stat hecho es que $$\sum_{i=0}^{\infty} S(i) = E[N]$$ que, si te acuerdas de algunos cálculos, se parece mucho a la exponencial de la serie de Taylor, por lo tanto, $$E[N] = (1-p)e^{(1-p) }$$