La convergencia de azar incremento de dos bandejas

Question

Si los recipientes a y B se inicializa a 1 y, a continuación, por la que continuamente se incremento a uno de ellos por 1 con una probabilidad proporcional a sus valores, sería A/B nunca convergen?

Para demostrar

A=1 B=1 , select A or B with 50-50 -> A chosen
A=2 B=1 , select A or B with 66-33 -> A chosen
A=3 B=1 , etc

Para A=1 y B=1 parece que difieren de la mayoría de las veces. Pero si me pongo de los grandes números A=100 B=100, no parece que pueda converger a 50-50 después de muchas iteraciones. Y Si comienzo a partir de A=100 B=200 convergían para 33-66 etc. Por lo que el valor inicial es importante.

¿Qué es la matemática de la explicación para este comportamiento? Tal vez el valor inicial es una función del incremento (1 en este caso) en la manera de ser capaz de garantizar la convergencia.

Answer 1

El problema puede ser formulado como un especial paseo aleatorio.

Vamos $X_n$ ($n\ge 1)$ ser un conjunto de variables de Bernoulli, tomando valores en $\{1,-1\}$, y deje $Y_n=\sum_{i=1}^n X_n$ ser nuestro paseo aleatorio. Lo que el caso de $X_n=1$ corresponden a incrementar $A_n$, tenemos:

$$ (A_n-A_0)-(B_n-B_0) = Y_n$$ $$ (A_n-A_0)+(B_n-B_0) = n$$

Por lo tanto $A_n = A_0 + (Y_n+n)/2$ $A_n + B_n = n+A_0+B_0$

Entonces

$$p_n= P(X_n=1) = \frac{A_{n-1}}{A_{n-1}+B_{n-1}} = \frac{1}{2}\frac{Y_{n-1}+n-1+2A_0}{n-1+A_0+B_0}$$

Dejando $\mu_n=E(X_n)$, acondicionado en el pasado, y la aplicación de la torre expectativa, obtenemos (me ahorraré los detalles) :

$$ \mu_n= \frac{\alpha +\sum_{i=1}^{n-1}\mu_i}{\beta +n} $$

donde$\alpha=A_0-B_0$$\beta = A_0+B_0-1$. Esto tiene la constante solución: $\mu_n = \frac{\alpha}{\beta+1}=\frac{A_0-B_0}{A_0+B_0}$. Por lo tanto

$$E(Y_n)=n \frac{A_0-B_0}{A_0+B_0}$$

y, por tanto, $A_n$ crece (en promedio) como $A_0 + n (\frac{A_0-B_0}{A_0+B_0}+\frac{1}{2})$

Lo que queda es para calcular la varianza de $Y_n$, que se requiere para calcular las correlaciones $E(X_n X_m)$. Como punto de partida, tenga en cuenta que $\sigma_X^2=4 A_0 B_0 /(A_0+B_0)^2$. Si $X_n$ fueron indepdent, $\sigma_Y^2= n \sigma_X^2$ . Porque tienen correlación positiva, sería de esperar que la varianza sea mayor, pero no mayor que $n^2 \sigma_X^2$.

Actualización: Un sencillo pero tedioso cálculo [*] me da: $$r=E(X_n X_m) = \frac{s+d^2}{ s(s+1)} \hskip{1cm} n\ne m, \;s=A_0+B_0, \; d=A_0-B_0$$

A continuación,$E(Y_n^2)=n+n(n-1) r$ ; y, por $E(Y_n)=n d/s$

$$ {\rm{Var}}(Y_n)=n\frac{s^2-d^2}{s(s+1)}\left(\frac{n}{s} +1\right) \approx n^2 \frac{s^2-d^2}{s^2(s+1)}$$

Volviendo a $A_n$, vemos que su media crece como

$$\overline{A_n} \approx n \left(\frac{1}{2}+\frac{d}{s}\right)$$

y la varianza como

$$ {\rm Var}(A_n) \approx n^2 \frac{s^2-d^2}{4 s^2(s+1)}$$

En particular, $A_0=B_0=1$ ($d=0$, $s=2$) tenemos

$$\overline{A_n} =1+\frac{n}{2} \hskip{1cm} {\rm Var}(A_n) \approx n^2 \frac{1}{12}$$

Si en lugar de $A_0=B_0=100$

$$\overline{A_n} =100+\frac{n}{2} \hskip{1cm} {\rm Var}(A_n) \approx n^2 \frac{1}{804}$$

Esto es, la conducta es básicamente el mismo en la media, pero la varianza es menor.

[*] Lo he comprobado en mis resultados en contra de las simulaciones, que parecen estar de acuerdo. Por CIERTO, confieso que me sorprendió encontrar que tanto la media y la correlación de la $X_n$ son constantes, tal vez me falta algunos conocimientos básicos y algunos la solución más sencilla.

Answer 2

Lo que usted está viendo se llama la Ley de los grandes números.

El mayor número de elecciones aleatorias hace más de cerca los números van a converger a sus probabilidades.

Como esta es una distribución Binomial y por lo tanto tiene un número finito primer momento (media) entonces satisface los criterios de una fuerte convergencia.

Así que para una probabilidad de selección de $A$ $p_a$ y un valor inicial de $A_0$$B_0$, después de $n$ ensayos será casi seguramente convergen a:

$$A_n=np_a+A_0$$ $$B_n=n(1-p_a)+B_0$$

Y, porque sabemos que la estructura de la distribución Binomial muy bien, podemos ir más lejos y afirman que van a tener una media de $np_a+A_0$ $n(1-p_a)+B_0$ respectivamente, con una variación de $np_a(1-p_a)$.

Ahora, lo suficientemente grande para $n$, $A_0$ y $B_0$ son insignificantes. Así que los valores iniciales son irrelevantes. Cómo irrelevante puede cuantificar a partir de la varianza.