6
$\begingroup$

A few days ago someone asked a question about dice in an interview. Naturally, one can consider the following more general problem. Suppose there are $n$ dice, with numbers from $1$ to $n$, on them. Person A throws $(n-1)$ dice in total, and person B throws a single die. Player B wins if his number is larger than the maximum of all the numbers of person A. What is the probability that B wins in this game?

The simplest approach is to consider a sequence $(a_1,a_2,...,a_{n-1},b)$. We wish to count all such sequences so that $b$ is larger than $a_i$. We can choose $n$ choices for $b$ and then $(n-1)$ choices for the $a_i$. Therefore, the probability that person B beats person A is equal to, $\frac{(n-1)^{n-1}n}{n^n} = \left( 1 - \tfrac{1}{n} \right)^{n-1}\approx \frac{1}{e}$.

Mysteriously the answer here involves $e$. Is there some deeper explanation for where this quantity comes from? This answer reminds me of the classical "hat problem" to which the answer is also (approximately) $\frac{1}{e}$. In both problems it is unclear to me what exactly is causing these constants to appear.

To clarify, when we say "deeper reason", we mean in reference to some deep result in probability theory. For instance, there are some problems which are approximated with an answer involving $\pi$, however, those problems are clear since they are variants of the Central Limit Theorem in some form or another, so it is not a surprise where this constant came from.

What exactly is the limiting distribution here that makes $e$ appear? I remember I once read about "order statistics", but I never learned anything about them, perhaps, by taking the maximum it is the asymptotic of the top order statistic? (It would be helpful is someone can also explain where $e$ likewise comes from in the hat problem as well.)

$\endgroup$
12
  • $\begingroup$ $\lim_{n \to \infty} (1 - \tfrac{1}{n})^n = \tfrac{1}{e}$ Check en.wikipedia.org/wiki/E_(mathematical_constant) $\endgroup$
    – Tim
    Commented Dec 31, 2022 at 8:18
  • $\begingroup$ That is not the question, furthermore, you meant to write $e$ not $1/e$, in either case, the question is asking for a limiting probability distribution, not calculus. $\endgroup$ Commented Dec 31, 2022 at 8:48
  • 1
    $\begingroup$ If you know that's the limit, what is your question? $\endgroup$
    – Tim
    Commented Dec 31, 2022 at 9:04
  • 2
    $\begingroup$ The description of the game doesn't match your calculations. If B needs to exceed the maximum of A's numbers, then in order to select a sequence in which B wins, we have $n$ choices for the number $b$, but only $b-1$ choices for each of the remaining $a_i$, not $n-1$. These calculations would describe a game where B wins if his number is different from all of A's numbers (not necessarily greater). Is that perhaps what you had in mind? $\endgroup$ Commented Dec 31, 2022 at 17:05
  • 1
    $\begingroup$ For a probabilist, maybe the most "fundamental" property of $e$ is that $1/e$ gives the probability for a Poisson process of rate 1 to have no arrivals in 1 unit of time. That could even be considered as the definition of the number $e$. And as $n$ goes to infinity, the number of A's rolls that match B's roll does indeed converge to a Poisson distribution. $\endgroup$ Commented Dec 31, 2022 at 23:43

1 Answer 1

10
$\begingroup$

The reason $e =\lim\limits_{n \to \infty}\left(1+\frac1n\right)^{n}=\frac1{\lim\limits_{n \to \infty}\left(1-\frac1n\right)^{n}}$ appears is precisely because you are taking a particular limit, though I am not sure you took exactly the correct one.

The answer should head towards $0$ as $n$ increases, since player B has one die and player A has an increasing number of dice. Ignoring the possibilities of ties for the largest values, you might think the probability of player B having the largest of $n$ values might be $\frac1n$. But the possibility of ties changes this.

You have used $n$ to mean two different things: the numbers of/on the dice and the number thrown by $B$. If instead you had used $b$ as the number thrown by player B then the answer to "the probability that Player B's number is strictly larger than the maximum of all the numbers of person A" is $$\sum\limits_{b=1}^n \frac{(b-1)^{n-1}}{n^n}$$ which for large $n$ is approximately $\frac{1}{n(e-1)}$, about $\frac{0.58}n$.

Meanwhile "the probability that Player B's number is at least as large as the maximum of all the numbers of person A" would be $\sum\limits_{b=1}^n \frac{b^{n-1}}{n^n}$ which for large $n$ is approximately $\frac{e}{n(e-1)}$ about $\frac{1.58}n$.

From the difference, you can tell that the probability of player B's number being exactly equal to the largest of player A's numbers is $\sum\limits_{b=1}^n \frac{b^{n-1}-(b-1)^{n-1}}{n^n}=\frac1n$. An alternative approach would be to say that the largest of player A's numbers is some value from $1$ to $n$ and player B has a probability of $\frac1n$ of getting that exact value.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.