¿Cuál es el número esperado de preguntas para completar una secuencia en que respuestas incorrectas envían al comienzo?

Question

Dada una secuencia de n preguntas que contiene cada una x las opciones de respuesta, lo que se espera que el número de preguntas respondidas antes de contestar todas las preguntas correctamente si contesta a una pregunta incorrectamente envía al principio de la secuencia? Las preguntas no cambian, así que una vez que la pregunta ha sido respondida correctamente, adivinando no tiene que ocurrir de nuevo. Todas las decisiones son hechas por adivinar entre cualquiera de las opciones de respuesta, siendo. En otras palabras, una vez que una respuesta equivocada ha sido elegido, no puede ser elegido de nuevo más tarde en la secuencia, y una vez que la respuesta ha sido encontrado, siempre será elegido al visitar esa pregunta.

Por ejemplo, para n = 2 y x = 2 el valor esperado es $E_{2,2} = \frac{7}{2}$:

1. Obtener preguntas a la derecha en el primer intento: $(\frac{1}{2})^{2}(2)$
2. Obtener la primera pregunta equivocado una vez, a la segunda pregunta derecha: $(\frac{1}{2})^{2}(3)$
3. Obtener la primera pregunta la derecha, luego a la segunda pregunta equivocada, luego a la derecha: $(\frac{1}{2})^{2}(4)$
4. Consigue el primer lugar equivocado, a la derecha, luego el segundo mal, luego a la derecha: $(\frac{1}{2})^{2}(5)$

He sido incapaz de derivar una forma cerrada de expresión para cualquier valor de x (distinta de la trivial caso de x = 1), y mucho menos cerrado, forma de expresión, tanto en términos de n y x. He probado a iniciar con una recurrencia de la relación como $E_{n+1,x} = E_{n,x} + (\frac{1}{x})^{n+1}S_{n,x} + E_{1,x}$ donde $S_{n,x}$ es el número de veces que el restablecimiento se produce en el diagrama de árbol que representa a $E_{n,x}$. Sin embargo, no he sido capaz de tomar esto más.

En aras de la claridad, $E_{3,1} = 2$:

1. Obtener la primera pregunta: $\frac{1}{3}(1)$
2. Obtener la primera pregunta equivocada, a continuación, haga: $(\frac{2}{3})(\frac{1}{2})(2)$
3. Obtener la primera pregunta mal dos veces, a continuación, haga: $(\frac{2}{3})(\frac{1}{2})(3)$

Pensé que era bastante interesante problema que no he sido capaz de encontrar en cualquier otro lugar. Alguien podría darnos una idea de la que se derive una forma cerrada de expresión para este problema? O al menos cómo podría desarrollar una solución recursiva?

Answer 1

Observación: Para responder una pregunta con $x$ opciones correctamente, se espera que el número de conjeturas, hasta obtener la respuesta correcta es $\frac{x+1}{2}$. (Tenga en cuenta que esto implica que el número esperado de respuestas incorrectas es $\frac{x-1}{2}$).

Después de un tiempo, hemos respondido a nuestras $k$th correctamente a la pregunta, y pasamos a la pregunta número $(k+1)$. Como en el anterior, esperamos hacer de $\frac{x-1}{2}$ respuestas incorrectas a la pregunta $k+1$, y cada una de estas respuestas incorrectas debe ser seguida inmediatamente por $k$ (correcta) de las respuestas a las preguntas de $1$ a través de $k$. Por lo tanto el número esperado de respuestas a la pregunta $(k+1)$ correcto después de conseguir la pregunta $k$ correcto es $\frac{x-1}{2}\cdot(k+1)+1$.

Por lo que el total estimado de la cantidad de conjeturas para obtener $n$ de preguntas correctas es $$E_{n,x}=\left(\frac{x-1}{2}+1\right)+\left(\frac{x-1}{2}\cdot 2+1\right)+\left(\frac{x-1}{2}\cdot 3+1\right)+\cdots+\left(\frac{x-1}{2}\cdot n+1\right)$$ Esto puede ser reescrita como $$E_{n,x}=\frac{x-1}{2}\cdot\frac{n(n+1)}{2}+n$$