Problema de "back to square one"

Question

Hay un problema que me he quedado estancado en preparación para entrar en concurso de programación de la que voy a participar. Es como sigue:

El "back to square one" el problema es jugado en un tablero que ha $n$ cuadrados en una fila y $n-1$ de probabilidades. Los jugadores se turnan para jugar. En su primer turno, un jugador avanza a la plaza de la $1$.Después de la primera vuelta, si un jugador está en la plaza de $i$ , el jugador avanza a la plaza de la $i + 1$ con una probabilidad de $p(i)$ , y vuelve a la plaza de la 1 con una probabilidad de $1-p(i)$ .El jugador termina al llegar a la plaza de $n$. Calcular el número esperado de vueltas para completar el juego.

$\textbf{My Attempt:}$ A partir de la definición de expectativa sabemos que

$$E[X] = \sum_{i=1}^{n-1}i\cdot P(i)= \sum_{i=1}^{n-1}i\cdot(1-p(i))\cdot p(i)$$

No estoy muy seguro de qué hacer con esta expresión. Tal vez sigue una distribución binomial negativa. Pero, la CDF para esto es realmente feo y creo que estaría más allá del alcance de este concurso.

Answer 1

Sea $f(i)$ el número esperado de vueltas cuando estás en Plaza $i$. Entonces tienes la recurrencia $i=1, 2,3,\dots n-1$: $$f(i) =1+ f(i+1)p(i)+f(1)(1-p(i)), \; f(n)=0$ $ y buscar $f(0)=1+f(1)$. Esto le da un sistema lineal a resolver.

Answer 2

Intuitivamente, usted necesita ganar $n-1$ en una fila. Trata de la oportunidad de hacer esto es $\prod_i p(i)$, por lo que toma $\frac 1{\prod_i p(i)}$. Necesita calcular la longitud media de un intento fallido. Es $1\ \ 1-p(1)$de la época, $2\ \ p(1)(1-p(2))$ % del tiempo y así sucesivamente. Añadirlos de arriba, recordando que debes dejar de $n-2$ para este cálculo. Si la duración promedio de una falla es $x$, tiene $\frac x{\prod_i p(i)}+n-1$ para el tiempo esperado para el éxito

Answer 3

Este es un problema de saber después de cuántas iteraciones de un transitorio de markov de estado se absorbe en el estado de absorción.

Wikipedia ayuda!

Básicamente, llenar una matriz de $A$ con las probabilidades de la cadena de markov, quitar la última columna y la última fila que corresponde a la absorción de estado, ha $Q$.

A continuación,$N = (I - Q)^{-1}$, y la respuesta es la suma de la primera fila de $N$.