Pregunta difícil sobre la probabilidad

Question

Cada mañana, un estudiante toma uno de los tres libros que posee de su estantería. La probabilidad de que elija el libro $i$ es $a_i$ , donde $0 < a_i < 1$ para $i=1,2,3$ y las elecciones en días sucesivos son independientes.

Por la noche sustituye el libro en el extremo izquierdo de la estantería. Si $P_n$ denota la probabilidad de que el día $n$ el alumno encuentra los libros en el orden $1,2,3$ de izquierda a derecha, muestran que, independientemente de la disposición inicial de los libros, $P_n$ converge como $n\to\infty$ y encontrar el límite.

Answer 1

Hay 6 órdenes diferentes. Para cada par de órdenes, se puede calcular la probabilidad de transición de uno a otro. Por ejemplo, si hoy están en el orden 123, mañana estarán en el orden 123 o 213 o 312 con probabilidad $a_1,a_2,a_3$ respectivamente. Por lo tanto, se trata de una cadena de Markov con 6 estados, y se puede escribir el $6\times6$ matriz de transición.

¿Qué sabes de las cadenas de Markov? ¿Qué sabes sobre las condiciones de la matriz de transición que garantizan la existencia de un estado al que converge la cadena independientemente de las condiciones iniciales? ¿Y puedes demostrar que la matriz que obtuvimos en el primer párrafo satisface las condiciones?

Answer 2

Lo siguiente no es una prueba de convergencia, pero da el valor de las seis probabilidades límite $p_{ikl}$ sin resolver un problema de valores propios:

Dibuja un gráfico con seis vértices $123$ , $\ldots$ , $321$ . Cada vértice recibe una probabilidad (desconocida) $p_{ikl}$ asignados. Hay aristas dirigidas con pesos asignados $a_i$ que conecta ciertos vértices. De este diagrama de flujo obtenemos seis ecuaciones de la forma $$p_{123}=a_1(p_{123}+p_{213}+p_{231})\ ,\quad \ldots\ ,\quad p_{321}=a_3(p_{321}+p_{231}+p_{213})\ ,$$ y existe la séptima ecuación $p_{123}+\ldots+p_{321}=1$ . La resolución de este sistema da en particular $$p_{123}={a_1 a_2\over a_2+a_3}\ ,$$ como se obtiene por binn.

Answer 3

Se puede resolver directamente utilizando una cadena de Markov de 6x6 con entradas en $\lbrace{ 0, a_1, a_2, a_3 \rbrace}$ como he hecho a continuación usando Wolfram alpha, pero usando la transposición de la matriz porque wolfram alpha tiene un odio a los vectores propios de la izquierda (en lugar de la derecha). Aquí estoy usando x,y,z en lugar de a1,a2,a3 porque soy perezoso.

eigendecomposición de {{x, 0, x, x, 0, 0}, {0, x, 0, 0, x, x}, {y, y, y, 0, 0, 0}, {0, 0, 0, y, y}, {z, z, 0, 0, z, 0}, {0, 0, z, 0, z}}

Quieres el vector propio correspondiente al valor propio x+y+z, pero Wolfram alpha también normaliza sus vectores propios de forma extraña, así que tienes que normalizarlo para que sus entradas sumen 1 (es decir, que sumen x+y+z). Después de hacer esto, obtuve $$ \lim_{n \to \infty} P_n = \frac{a_1 a_2}{a_2 + a_3} $$

Para demostrar que este límite existe, hay que hacer algo como demostrar que cada estado puede alcanzar cada uno de los otros estados con probabilidad positiva; esto es fácil porque se puede alcanzar el estado ijk desde cualquier estado escogiendo el libro k y luego el libro j y luego el libro i, y cada uno de estos tres eventos independientes tiene probabilidad positiva como se indica en la pregunta.

Answer 4

Se tiene una cadena de Markov irreducible y aperiódica en el conjunto de todos los órdenes posibles de libros. La teoría de las cadenas de Markov garantiza que su límite existe y es igual a $\pi(123)$ , donde $\pi$ es el único vector de probabilidad invariante vector de probabilidad para la cadena. En su notación, esto resulta ser $$\pi(123)={a_1\over a_1+a_2+a_3}\,{a_2\over a_2+a_3}\,{a_3\over a_3}.$$ Para una ordenación arbitraria de los libros, obtenemos el resultado correspondiente $$\pi(ijk)={a_i\over a_i+a_j+a_k}\,{a_j\over a_j+a_k}\,{a_k\over a_k}.$$ A continuación se presenta una prueba de esta fórmula.

---

De forma más general, vamos a denotar los libros como $A,B,C,\dots,Y,Z$ con probabilidad correspondiente de ser elegido como $a,b,c,\dots,y,z$ . Por supuesto, $a+b+c+\cdots+y+z=1$ .

Tomemos un ordenamiento particular, que etiquetaré como $\beta$ : $$\beta:=DJG\cdots CW.$$ La fórmula de la probabilidad invariable de $\beta$ es el producto $$\pi(\beta):={d\over d+j+g+\cdots+c+w}\,{j\over j+g+\cdots+c+w}\, {g\over g+\cdots+c+w} \cdots {c\over c+w}\, {w\over w}.$$

Para comprobarlo, calculemos el $\beta$ La entrada más importante en el vector vector $\pi P$ Es decir, $\sum_\alpha \pi(\alpha) P(\alpha,\beta)$ . Los únicos estados $\alpha$ desde el que se puede saltar al estado $\beta$ son los que se parecen a $\beta$ pero con libro $D$ conmovido. Eso es, $$\alpha\in\{ DJG\cdots CW, JDG\cdots CW, JGD\cdots CW, \dots, JG\cdots CWD\}.$$ Para todos estos $\alpha$ la probabilidad de transición es simplemente $P(\alpha,\beta)=d$ .

Por lo tanto, $$ \begin{eqnarray*}(\pi P)(\beta)&=&d\sum_\alpha \pi(\alpha)\\ &=&{d\over d+j+g+\cdots+c+w} \sum_\alpha \pi(\alpha)\\ &=&{d\over d+j+g+\cdots+c+w}\, {j\over j+g+\cdots+c+w}\, {g\over g+\cdots+c+w} \cdots {c\over c+w}\, {w\over w}, \end{eqnarray*} $$ donde, en el último paso, utilizamos la identidad algebraica demostrada aquí.

El hecho de que $\sum_\gamma \pi(\gamma)=1$ se puede demostrar por inducción o utilizando la siguiente interpretación: $\pi(\gamma)$ es la probabilidad de que si muestro los libros de uno en uno sin reemplazo, se ocurran en el orden $\gamma$ .