# Interview Question on Probability: A and B toss a dice with 1 to n faces in an alternative way

A and B toss a dice with 1 to n faces in an alternative way, the game is over when a face shows up with point less than the previous toss and that person loses. What is the probability of the ﬁrst person losing the game and the expected number of tosses?

I can solve this question for 6 face dice: If the first die is 1, there are 5 greater numbers on the second: 1/6 * 5/6 = 5/36. If the first die is 2, there are 4: 1/6 * 4/6 = 4/36 and so on. T/hus prob of first person losing the game is:

5/36 + 4/ 36 + 3/36 + 2/36 + 1/36 = 15/36 = 5/12

don't know how to generalize it to n faces.

• I take it the faces are numbered $1$ to $n$? – saulspatz Aug 14 '18 at 17:40
• @saulspatz yes, they are numbered from 1 to n – user584227 Aug 14 '18 at 17:44
• Welcome to MSE. You should put clarifications in the body of the question, not the comments. People browsing question will often not read the comments. What are your thoughts on this question? How far have you gotten with it? Where are you stuck? This question is likely to be closed unless you add some more context to it. – saulspatz Aug 14 '18 at 17:48
• @RossMillikan: I think "in an alternative way" is meant to say "alternatingly". – joriki Aug 14 '18 at 20:25
• Adding my standard rant: you cannot throw "a dice". "Dice" is the plural of "die". You can throw a singe "die" or two or more "dice". – user247327 Aug 14 '18 at 22:54

There are $\binom{n+k-1}k$ different non-decreasing sequences of length $k$ with elements in $\{1,\ldots,n\}$. The first player loses exactly if for any even $k$ the first $k$ rolls form such a sequence and the first $k+1$ rolls don't. Thus the probability for the first player to lose is

$$\sum_{k=0}^\infty(-1)^k\binom{n+k-1}k\frac1{n^k}=\left(1+\frac1n\right)^{-n}\;.$$

This goes to $\mathrm e^{-1}$ as $n\to\infty$. In the limit $n\to\infty$, the probability for equal rolls goes to zero, so we can rank the rolls. If we rank the first $k$ rolls, the ranks are a random permutation of the first $k$ integers. Thus, the limit can also be obtained if we know how many permutations have their first descent (or, equivalently, ascent) in an even position. This was recently asked and answered at Permutations of length $n$ in which the first ascent occurs in an even position. The result is that the number of these permutations is the number of derangements, and the proportion of permutations of length $k$ that are derangements goes to $\mathrm e^{-1}$ as $k\to\infty$, in agreement with the above result.

The expected number of rolls can be obtained by summing the probabilities that no descent has occurred after $k$ rolls:

$$\sum_{k=0}^\infty\binom{n+k-1}k\frac1{n^k}=\left(1-\frac1n\right)^{-n}\;.$$

This goes to $\mathrm e$ as $n\to\infty$. In the limit $n\to\infty$, we can again ignore the possibility of equal rolls. The probability that no descent has occurred after $k$ rolls is then $\frac1{k!}$, and the expected number of rolls is

$$\sum_{k=0}^\infty\frac1{k!}=\mathrm e\;,$$

in agreement with the above result.

• Delightful. I'm not sure I fully follow the parts where you say we can evaluate the limits by ignoring the possibility of equal rolls, though. I understand them as heuristics, but you seem to be saying that these are rigorous arguments. In both cases, you are taking the limit as $n\to\infty$ under the summation sign, aren't you? Is it just that all the terms are positive, and one can appeal to the dominated convergence theorem, say? – saulspatz Aug 15 '18 at 15:32
• @saulspatz: Well, I didn't make any effort to turn those parts into rigorous arguments since the limit agreed with the limit from the exact calculation -- but if I had to turn them into rigorous arguments, I think I'd argue that these results are exact conditional on not rolling any equal numbers before the game ends; the probability of rolling equal numbers before the game ends goes to zero as $n\to\infty$; and the expectations conditional on rolling equal numbers before the game ends are finite -- I think that should be enough? – joriki Aug 15 '18 at 18:40
• That makes sense, thanks. I guess I understood it in the sense you originally intended, but I thought I was missing something. – saulspatz Aug 15 '18 at 18:55
• Turns out that you and I interpreted the rules differently. See my edited answer. – saulspatz Aug 16 '18 at 10:29
• @saulspatz: Yes, that is a bit weird that neither of us had noticed before. I did check whether my result agreed with yours, but I guess I must have suffered from confirmation bias :-) – joriki Aug 16 '18 at 14:55

Let me get you started. For $k=1,2,\dots,n$ let $p_k$ be the probability that the roller loses if he rolls $k,$ and that does not immediately win the game. Therefore, the probability that the first player loses is $${1\over n}\sum_{k=1}^np_k$$

It seems to me that the easiest way to compute $p_k$ will be in decreasing order, starting with $k=n$ and progressing down to $k=1$. When $k= n$ we have

$$p_n= {n-1\over n} + {1\over n}\left(1-p_n\right)\implies p_n={n\over n+1}$$ because, if the roller rolls $n$, he will lose if his opponent rolls anything but $n$, and in the case where the opponent does rolls $n$, he loses if the opponent doesn't lose.

Similarly, \begin{align} p_{n-1}&={n-2\over n} + {1\over n}\left(1-p_{n-1}\right) + {1\over n}\left(1-p_n\right)\\ p_{n-1}&=1-{1\over n}p_{n-1}-{1\over n}p_n\\ {n+1\over n}p_{n-1}&=1-{1\over n+1}\\ p_{n-1}&={n^2\over(n+1)^2} \end{align}

Can you continue?

EDIT

Now that a complete solution has been given, I will work out the details. I claim that with $p_k$ defined as above, we have $$p_{n-j}=\left({n\over n+1}\right)^{n-j},\ j=0,1,\dots,n-1$$

The $j=0$ case has been done above. Assuming the theorem is true for $0,1,\dots,j-1,$, we have \begin{align} p_{n-j}&={n-j-1\over n}+{1\over n}\sum_{k=n-j}^n(1-p_k)\\ \left(1+\frac1n\right)p_{n-j}&=1-\frac1n\sum_{k=0}^{j-1}p_{n-k}\\ \left({n+1\over n}\right)p_{n-j}&=1-\frac1n\sum_{k=0}^{j-1}\left({n\over n+1}\right)^{k+1}\\ \left({n+1\over n}\right)p_{n-j}&=1-\frac1n\frac{\left({n\over n+1}\right)^{j+1}-{n\over n+1}}{{n\over n+1}-1}\\ \left({n+1\over n}\right)p_{n-j}&=1-\frac1n{n\over n+1}\frac{\left({n\over n+1}\right)^{j}-1}{{-1\over n+1}}=1-\left(1-\left(n\over n+1\right)^j\right)\\ p_{n-j}&=\left({n\over n+1}\right)^{j+1} \end{align}

Therefore, the probability that the first player loses is $$\frac1n\sum_{j=0}^{n-1}\left({n\over n+1}\right)^{j+1}= \frac1n\frac{\left({n\over n+1}\right)^{n+1}-{n\over n+1}}{{n\over n+1}-1}=\frac1n{n\over n+1}\frac{\left({n\over n+1}\right)^n-1}{{-1\over n+1}}=1-\left({n\over n+1}\right)^n$$

Note that this is precisely the complement of the probability that joriki computed in his solution. The problem lies in the description of the game in the question: "the game is over when a face shows up with point less than the previous toss and that person loses." It isn't at all clear who "that person" is, as the phrase has no antecedent. I interpreted it to mean that the first player who rolls a smaller number wins, and joriki interpreted it oppositely. Note that joiki says that the first player loses if the first non-monotonically increasing sequence has odd length, so that if the first $3$ rolls are $3,4,2$ the first player loses. In my interpretation, since it is the first player who rolled the $2,$ the first player wins. It's a bit surprising that nobody (including joriki and me) noticed that we were using different rules.

A similar approach will give the expected number of rolls, and this time, reassuringly, I get the same answer as joriki. If we let $e_k$ be the expected number number of rolls remaining, if the current point is $k$ then the expected number of rolls in the game is $$E=1+\frac1n\sum_{k=1}^ne_k$$ and in a manner exactly analogous to the calculations above, we find that $$e_{n-j}=\left(n\over n-1\right)^{j+1},\ j=0,1,\dots,n-1$$ and that $$E=\left({n\over n-1}\right)^n=\left(1-\frac1n\right)^{-n}$$

• The result can actually be obtained in closed form (see my answer). – joriki Aug 15 '18 at 5:58
• As I said, I was just trying to get the OP started. I hadn't worked out the answer in detail. Frankly, I just assumed, since it was an interview question, that it would work out if one continued along these lines. Now that I've seen your answer, I'll have to try to follow this line of thought to completion, and see where I get. – saulspatz Aug 15 '18 at 14:17