Rompecabezas de probabilidad con bucle infinito

Question

He encontrado este problema y me he atascado en cómo resolverlo.

Un minero está atrapado en una mina que contiene 3 puertas. La primera puerta conduce a un túnel que lo llevará a un lugar seguro después de 3 horas de viaje. La segunda puerta conduce a un túnel que le devolverá a la mina después de 5 horas de viaje. La tercera puerta conduce a un túnel que le devolverá a la mina después de 7 horas. Si suponemos que el minero tiene en todo momento la misma probabilidad de elegir cualquiera de las puertas, ¿cuál es el tiempo esperado hasta que llegue a un lugar seguro?

El hecho de que el minero pueda estar atascado en un bucle infinito me ha confundido. Cualquier ayuda es muy apreciada.

Answer 1

Dejemos que $T$ sea el tiempo de permanencia en la mina. Condicionando la primera puerta que elige el minero, obtenemos $$ \mathbb{E}[T]=\frac{1}{3}\cdot3+\frac{1}{3}(5+\mathbb{E}[T])+\frac{1}{3}(7+\mathbb{E}[T])$$ así que $$ \mathbb{E}[T]=5+\frac{2}{3}\mathbb{E}[T].$$ Si $\mathbb{E}[T]$ es finito, entonces podemos concluir que $\mathbb{E}[T]=15$ .

Para ver que $\mathbb{E}[T]$ es finito, dejemos que $X$ sea el número de veces que el minero elige una puerta. Entonces $ \mathbb{P}(X\geq n)=(\frac{2}{3})^{n-1}$ para $n=1,2,3,\dots$ Por lo tanto $$ \mathbb{E}[X]=\sum_{n=1}^{\infty}\mathbb{P}(X\geq n)=\sum_{n=1}^{\infty}\Big(\frac{2}{3}\Big)^{n-1}<\infty$$ Y como $T\leq 7(X-1)+3$ vemos que $\mathbb{E}[T]<\infty$ también.

Answer 2

Dejemos que $t$ sea el momento esperado para salir. Si toma la segunda o tercera puerta, vuelve a la misma posición de la salida, por lo que el tiempo esperado después de volver es $t$ . Por lo tanto, tenemos $$t=\frac 13(3) + \frac 13(t+5)+\frac 13(t+7)\\\frac 13t=5 \\t=15$$

Answer 3

Con probabilidad $1$ acabará por tomar la puerta correcta así, $$3*\frac11$$

Las puertas equivocadas pueden combinarse, $$ +6*\frac23 $$

y se repite $$ +6*(\frac23)^2 $$

y se repite $$ +6*(\frac23)^3 $$

...

Esto se puede escribir como una serie geométrica

$$3 +\sum (6 * (\frac23)^n)$$

Lo que se sabe que simplifica a $$ 3+ 4/ (1-\frac23)$$

$$= 3+4*3 $$

$$ = 15$$

---

Este resultado parece generalizarse. Para $K$ puertas con longitudes de senderos $A,B,C,...N$ si sólo $A$ conduce a la salida y todas las demás puertas conducen de nuevo a la elección que se obtiene $$A + \sum(B*(\frac{1}{K})^n) + \sum(C*(\frac{1}{K})^n) + ...\sum(N*(\frac{1}{K})^n)$$

Que se convierte en $$A+(\frac{\frac BK}{1-\frac1K})+(\frac{\frac CK}{1-\frac1K})+...(\frac{\frac NK}{1-\frac1K}))$$

$$=A +\frac BK * K + \frac CK * K + ...\frac NK * K$$

$$=A+B+C+...N$$

Ir al azar equivale a tomar cada puerta una vez. Qué raro.

Answer 4

Se trata de un enfoque diferente, que utiliza el tiempo previsto para que el minero pase por $n$ puertas.

Dejemos que $n$ sea el número de puertas que abre el minero y que $P(T=t)$ sea la probabilidad de que el minero tome $t$ horas para salir. Para $n=3$ la secuencia de puertas que abre el minero es una de $(2,2,1),(2,3,1),(3,2,1),(3,3,1)$ . Estas secuencias corresponden a $P(5+5+3)=\frac{1}{3^3}$ , $P(5+7+3)=\frac{2}{3^3}$ y $P(7+7+3)=\frac{1}{3^3}$ . El numerador de la segunda probabilidad es $2$ porque hay $2$ formas de tener $t=15$ . La figura siguiente es un gráfico del PMF de P(t).

Si el minero pasa por $n$ puertas, de las cuales $k$ son de puerta $2$ Entonces él pasará $n-1-k$ veces a través de la puerta- $3$ . El $-1$ término da cuenta de su paso por la puerta- $1$ . Entonces, en general, $P(5k+7(n-1-k)+3)=\frac{1}{3^n}\binom{n-1}{k}$ . Esto se debe a que existe una $\frac{1}{3^n}$ probabilidad de elegir cada secuencia de puertas, pero $\binom{n-1}{k}$ formas de elegir esa secuencia. El minero puede pasar por la puerta $2$ entre $0$ y $n-1$ veces, así que $0\leq k\leq n-1$ .

$\mathbb{E}[T]=\sum tP(t)$

En $n$ el valor esperado, $\mathbb{E}[T]$ es:

$$ \begin{aligned} \mathbb{E}[T]&=\sum _k tP(t) \\ &=\sum_{0\leq k\leq n-1}\frac{5k+7(n-1-k)+3}{3^n}\binom{n-1}{k} \\ &=\frac{1}{3^n}\left[(7n-4)\sum\binom{n-1}{k}-2\sum k\binom{n-1}{k}\right] \\ &=\frac{1}{3^n}\left[2^{n-1}(7n-4)-2^{n-1}(n-1)\right] \\ &=\frac{2^{n-1}(6n+3)}{3^n} \end{aligned} $$

Entonces, el valor esperado sobre todos los $n$ es:

$$ \begin{aligned} \mathbb{E}[T]&=\sum_{n\in\mathbb{Z^+}} \frac{2^{n-1}(6n+3)}{3^n} \\ &=15 \end{aligned} $$

Answer 5

Consideremos un ejemplo más sencillo: tienes una moneda justa. Tiras la moneda una y otra vez. ¿Cuál es el número esperado de veces que lanzará la moneda antes de obtener una cara? Por supuesto, es posible que lanzará la moneda infinitas veces y nunca obtendrá cara. Por otro lado, también es posible que salga cara en el primer lanzamiento. Afortunadamente, tu intuición es que es muy poco probable que tengas que lanzar la moneda más de un par de veces antes de que salga cara. Podemos resumir todo el proceso con un diagrama de árbol:

La probabilidad en cada hoja es el producto de todas las probabilidades que conducen a ella (esto es un resultado de la independencia; tenga en cuenta que este tipo de diagramas a menudo puede ser útil para entender el condicionamiento). En la fila superior, seguimos lanzando colas una y otra vez. Los resultados finales terminan todos en cara. Entonces \begin {align} \mathbb {E}[ \text {número de lanzamientos}] &= 1 \cdot \mathrm {P}( \mathrm {H}) + 2 \cdot \mathrm {P}( \mathrm {TH}) + 3 \cdot \mathrm {P}( \mathrm {TTH}) + 4 \cdot \mathrm {P}( \mathrm {TTTH}) + \dotsb \\ &= \frac {1}{2} + \frac {2}{4} + \frac {3}{8} + \frac {4}{16} + \dotsb \\ &= \sum_ {n=1}^{ \infty } \frac {n}{2^n} \\ &= 2. \end {align} Por lo tanto, en promedio, podemos esperar lanzar la moneda dos veces.

Obsérvese que podemos simplificar enormemente esta imagen observando que si primero lanzamos cruz, entonces volvemos al principio. Eso nos da esta imagen:

Entonces \begin {align} \mathbb {E}[ \text {número de lanzamientos}] &= 1 \cdot \mathrm {P}( \mathrm {H}) + (1+ \mathbb {E}[ \text {número de lanzamientos}]) \cdot \mathrm {P}( \mathrm {T}) \\ &= \frac {1}{2} + \frac {1+ \mathbb {E}[ \text {número de lanzamientos}]}{2} \end {align} El $1+\mathbb{E}[\text{number of tosses}]$ viene del hecho de que si sacamos cruz en el primer lanzamiento de la moneda, entonces ya hemos lanzado la moneda una vez, pero todo lo demás es como si acabáramos de empezar el proceso desde el principio. Esto se puede expresar en términos de probabilidad condicional, pero no creo que la notación adicional ayude mucho en este caso. En cualquier caso, resolviendo el número esperado de lanzamientos, obtenemos $$ \frac{1}{2} \mathbb{E}[\text{number of tosses}] = 1 \implies \mathbb{E}[\text{number of tosses}] = 2. $$

---

Entonces, ¿qué tiene que ver esto con el problema de las cuevas? Para generalizar el argumento anterior al problema de la cueva, imagina primero que estás en la habitación descrita, y que tienes una moneda de tres caras justa (¿sería mejor si sugiriera que tienes un d3?). Cada vez que vuelves al principio, lanzas tu moneda de tres caras para decidir por qué puerta pasar. Con la probabilidad $\frac{1}{3}$ se pasa por la puerta de las 3 horas y se vuelve al inicio, con probabilidad $\frac{1}{3}$ atraviesas la puerta de las 5 horas y escapas, y con probabilidad $\frac{1}{3}$ pasas por la puerta de las 7 horas y vuelves al principio.

Así que, supongamos que primero se elige la puerta de las tres horas. ¿Cuánto tiempo espera tener que caminar en total? Vas a tener que caminar durante 3 horas, pero luego vuelves al principio. El tiempo que esperas caminar desde allí es el tiempo esperado, que es lo que estamos tratando de calcular. Por lo tanto, si primero pasa por la puerta de las tres horas, entonces vas a caminar $$ 3\text{ hours} + \mathbb{E}[\text{total time}].$$ En otras palabras, utilizando el lenguaje de la probabilidad condicional (aquí, va a hacer las cosas un poco más claras, creo), tenemos $$ \mathbb{E}[\text{total time} \mid \text{chose 3 hour door}] = 3 + \mathbb{E}[\text{total time}]. $$

Por un razonamiento similar, tenemos \begin {align} \mathbb {E}[ \text {tiempo total} \mid \text {elegir la puerta de 5 horas}] &= 5 && ( \text {no volvemos al principio}) \\ \mathbb {E}[ \text {tiempo total} \mid \text {elegir la puerta de 7 horas}] &= 7 + \mathbb {E}[ \text {tiempo total}] \end {align} Como cada uno de estos eventos es igualmente probable, sumamos para obtener \begin {align} \mathbb {E}[ \text {tiempo total}] &= \mathrm {P}( \text {puerta de 3 horas}) \cdot (3 + \mathbb {E}[ \text {tiempo total}]) + \mathrm {P}( \text {puerta de 5 horas}) \cdot 5 \\ & \qquad\qquad + \mathrm {P}( \text {puerta de 7 horas}) \cdot (7 + \mathbb {E}[ \text {tiempo total}]) \\\\ &= \frac {3 + \mathbb {E}[ \text {tiempo total}]}{3} + \frac {5}{3} + \frac {7 + \mathbb {E}[ \text {tiempo total}]}{3}. \end {align} Sólo queda resolver el tiempo total de recorrido esperado. Para simplificar la notación, dejemos que $E := \mathbb{E}[\text{total time}]$ . La ecuación anterior se reduce a \begin {align} E = \frac {3 + E}{3} + \frac {5}{3} + \frac {7 + E}{3} = \frac {15 + 2E}{3} & \implies \frac {E}{3} = 5 \\ & \implies E = 15. \end {align} En otras palabras, deberíamos esperar viajar 15 horas en total (que es lo que dan las otras respuestas).

---

La moraleja de esta historia es que viajar durante un tiempo infinito es, en principio, posible. Sin embargo, es muy poco probable que se pueda viajar para siempre (de hecho, se viajará durante una cantidad infinita de tiempo con una probabilidad nula; a efectos prácticos, nunca ocurrirá).