What is the expected number of questions answered to complete a sequence in which wrong answers send you to the start?

Question

Given a sequence of n questions that each contain x answer choices, what is the expected number of questions answered before answering all questions correctly if answering a question incorrectly sends you to the beginning of the sequence? The questions do not change, so once a question has been answered correctly, guessing does not have to occur again. All choices are made by guessing between whichever answer choices remain. In other words, once a wrong answer has been chosen, it cannot be picked again later in the sequence, and once a right answer has been found, it will always be chosen when visiting that question.

For example, for n equals 2 and x equals 2 the expected value is $E_{2,2} = \frac{7}{2}$:

1. Get both questions right on the first try: $(\frac{1}{2})^{2}(2)$
2. Get the first question wrong once, then the second question right: $(\frac{1}{2})^{2}(3)$
3. Get the first question right, then the second question wrong, then right: $(\frac{1}{2})^{2}(4)$
4. Get the first wrong, then right, then the second wrong, then right: $(\frac{1}{2})^{2}(5)$

I've been unable to derive a closed form expression for any single value of x (other than the trivial case of x = 1), much less a closed form expression in terms of both n and x. I've tried to start with a recurrence relation such as $E_{n+1,x} = E_{n,x} + (\frac{1}{x})^{n+1}S_{n,x} + E_{1,x}$ where $S_{n,x}$ is the number of times a reset occurs in the tree diagram that represents $E_{n,x}$. However, I haven't been able to take this any further.

For the sake of clarity, $E_{3,1} = 2$:

1. Get the first question right: $\frac{1}{3}(1)$
2. Get the first question wrong then right: $(\frac{2}{3})(\frac{1}{2})(2)$
3. Get the first question wrong twice then right: $(\frac{2}{3})(\frac{1}{2})(3)$

I thought it was a fairly interesting problem that I haven't been able to find anywhere else. Could anyone provide some insight into deriving a closed form expression for this problem? Or at least how I might develop a recursive solution?

Answer 1

Observation: To answer one question with $x$ choices correctly, the expected number of guesses until getting the correct answer is $\frac{x+1}{2}$. (Note that this implies that the expected number of incorrect responses is $\frac{x-1}{2}$).

After a while, we have just answered our $k$th question correctly, and we go on to question number $(k+1)$. As above, we expect to make $\frac{x-1}{2}$ incorrect responses to question $k+1$, and each of these incorrect responses must be immediately followed by $k$ (correct) responses to questions $1$ through $k$. Hence the expected number of responses to get question $(k+1)$ correct after getting question $k$ correct is $\frac{x-1}{2}\cdot(k+1)+1$.

So the expected total number of guesses to get $n$ questions correct is $$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)$$ This can be rewritten as $$E_{n,x}=\frac{x-1}{2}\cdot\frac{n(n+1)}{2}+n$$