Throwing n-sided fair dice until sum of two throws equals n

Question

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?

Answer 1

Here somewhat detailed instructions for constructing the transition probabilities for Markov chain.

To proceed to the final state ($\dagger$) we should collect a pair $(i,n-i)$. So let characterize a state by the number $k$ of the collected unpaired numbers disregarding '$0$', so that $0\le k\le\left\lfloor\dfrac n2\right\rfloor$. There is however a serious difference between the cases with odd and even $n$. In the latter case there is single number $\frac n2$ which is self-paired. This almost doubles the number of Markov states: from $\frac{n+3}2$ to $n+1$. We shall designate the states which include the number $\frac n2$ by $k^*$. Observe that the numbers of starred and unstarred states are equal: the former do not include the state $0$, and the latter do not include the state $\frac n2$.

The non-zero transition probabilities are shown in the following tables (with the transition probability of the absorbing state $\dagger\to\dagger$ equal to $1$):

1. Even $n$: $$ \begin{array}{|c|c|c|c|} \hline k\to k& k\to (k+1)& k\to (k+1)^*&k\to\dagger\\ \frac{k+1}n& \frac{n-2k-2}n&\frac1n&\frac kn\\ \hline k^*\to k^*& k^*\to (k+1)^*&&k^*\to\dagger\\ \frac{k}n& \frac{n-2k}n&&\frac kn\\ \hline \end{array}$$

2. Odd $n$:

$$ \begin{array}{|c|c|c|c|} \hline k\to k& k\to (k+1)&k\to\dagger\\ \frac{k+1}n& \frac{n-2k-1}n&\frac kn\\ \hline \end{array}$$

---

A simpler method to compute the probability is the following. Let us compute the probability that the game does not end after $k$ throws: $$ P_k(n)=\frac1{n^k}\sum_{i=0}^N\binom Ni 2^i i!\left({k+1 \brace i+1} +\left[k {k \brace i+1}\right]_{n\in 2\mathbb Z}\right),\tag1 $$ with $$ N=\left\lfloor\frac{n-1}2\right\rfloor $$ being the number of the complementary pairs.

Then the probability in question can be computed as $$ p_k(n)=P_{k-1}(n)-P_k(n). $$

Explanation.

We need to count all sequences of the length $k$ which do not contain any two of the complementary numbers. To avoid the double counting we split the sequences in the disjoint classes labeled by the representatives of the pairs showing up at least once in the sequence. The factor $\binom Ni$ counts the number of classes with $i$ representatives. The factor $2^i$ takes into account the fact that there are two possible representatives for a pair. The factor $i!{k+1 \brace i+1}$ counts the number of ways to distribute $k$ dices (labeled by their position in the sequence) into $(i+1)$ distinguishable "boxes" (an additional box is for the dice showing up $0$ and is the only one which is allowed to be empty). Finally in the case of even $n$ we can have in the sequence one special die $\frac n2$ which results in the additional term $k{k \brace i+1}$ (the factor $k$ counts the number of ways to choose the position of the special die in the sequence).

Answer 2

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.