I have an $n$-sided fair die and each side has a different number from the set $\{0, 1, 2, … , n – 1\}$. On each throw I write down number what was thrown. I do this until the sum of two numbers from the list that I wrote down equals $n$. So the question is, what is the probability that this game ends in $k$ throws? It is clear that when $k = 1$ the probability is $0$. I thought of using a Markov chain to solve this problem, but I don't know how to represent states and what is the probability of going from one state to another. Can anybody help me with this?
Throwing n-sided fair dice until sum of two throws equals n
dicemarkov chainsprobability
Related Solutions
Consider the expected number of points you will obtain after rolling a particular number.
e.g. Suppose we have just rolled a 6. We need to roll another 6 to keep playing, otherwise we stop. Using conditional expectation, we can compute the number of future points we expect to obtain, $E_6$: $$E_6 = \frac{1}{6}(E_6 + 6) + \frac{5}{6}\times 3.$$
The first term corresponds to rolling a 6, and we are back in the same position as before, just with 6 extra points. The second term gives expected number of points obtained, given that we roll a lower number and stop playing. We solve this to obtain $$E_6 = \frac{21}{5}.$$
Now suppose that, in a new game, we have just rolled a 5. What is the expected number of points from this point, $E_5$? Using the same conditional expectation rules as before: $$E_5 = \frac{1}{6}(E_5+5) + \frac{1}{6}(E_6+6) + \frac{4}{6} \times \frac{5}{2}.$$ Since we know $E_6$ from above, we can now solve for $E_5$.
Repeat this for $E_4, \dots, E_1$, and we know the expected number of future points given the most recent roll number.
Finally, the expected number of points, $E$, will be the conditional sum of these values, i.e.
\begin{equation} E = \sum_{n=1}^6 \frac{1}{6}(E_n + n). \tag{1} \end{equation}
Edit: following an observation by Taner, I thought I'd add a few more lines.
After some generalizing and rearranging, we obtain $$E_n = \frac{1}{5}\left(\sum_{m=n+1}^6 E_m + 21\right),$$ and we can set up a recurrence relation for $E_n$ so we don't have to do this sum every time to compute it. We have
\begin{align} E_{n+1} &= \frac{1}{5}\left(\sum_{m=n+2}^6 E_m + 21\right) \\ &= \frac{1}{5}\left(\sum_{m=n+1}^6 E_m + 21 - E_{n+1}\right) \\ &= E_n - \frac{1}{5}E_{n+1}, \end{align}
which we rearrange to obtain $$E_{n+1} = \frac{5}{6}E_n,$$ which has solution $$E_n = C \left(\frac{5}{6}\right)^n,$$ where $C$ is some constant, for which we can solve by setting $n=6$ and using our value of $E_6$. We obtain (allowing for possible arithmetic errors made by me) $$E_n = \frac{21}{5}\left(\frac{5}{6}\right)^{n-6}.$$
We can substitute this into Equation (1) and use geometric and arithmetic sum formulae to obtain the final answer.
Edit 2: as Alex Zorn pointed out, we don't even need to do this geometric and arithmetic sum stuff in Equation (1). Note that the game is the same before and after rolling a 1, so this tells us straight away that $$E = E_1 = \frac{21}{5}\left(\frac{5}{6}\right)^{-5} = \frac{163296}{15625} \approx 10.45.$$
Best Answer
HINTS
Let $[n-1] = \{k\}_{k=0}^{n-1}$ and one approach is to let $W$ denote the set of all $A \subseteq W$ such that no two elements of $A$ add up to $n$. Then, $S = W \cup \{*\}$ is the state space of the Markov chain, with $*$ denoting the absorbing state of finally generating a set of throws where two members add up to $n$.
Now you can define transition probabilities and solve.
A different approach is to note that if you have thrown $1$, then either you win in the next throw or you cannot throw $n-1$ at any time. So you really have $1,n-1$ and $2,n-2$ etc., and when you throw one number from the pair, you will never throw another one unless you complete the task. So the probability to finish in exactly $k$ steps is the probability of picking $k-1$ of those pairs in the first $k-1$ tries, and then picking one of them again in the last attempt.
You could use a geometric random variable or a Markov chain, or argue from first principles.