# What is the probability of losing in the Taiwainese IMO team's game?

Evan Chen's recount of the Taiwanese IMO team's journey recorded a game the team members played at their free time, which runs as the following:

There are $n$ team members (in the actual case $n=6$ but here we simply take $n\geq2$)Every team member points at another team member (whom must be different from him/herself) and thus we obtain a (directed) graph with $n$ vertices and $n$ edges. It has one more edge than a tree and therefore must contain a cycle. Any member who is a vertex of any cycle in this graph loses the game. (So it is possible that everyone loses but it's impossible that no one loses.)

Assume everyone chooses the person s/he points at randomly, what is the probability of a player losing the game?

Reference: Evan Chen's recount

It is: $$p_{1}+\cdots+p_{n-1}$$ where: $$p_{k}:=\frac{n-2}{n-1}\frac{n-3}{n-1}\cdots\frac{n-k}{n-1}\frac{1}{n-1}$$ is the probability of losing together with $k$ mates that are in the same (losing) cycle.

Let's start with denoting the player who starts with $P_0$ and the player he points at with $P_1$. Inductively denote the player pointed at by $P_{n-1}$ with $P_n$. Then $P_0$ will lose with exactly $k$ mates in the same cycle if $P_0,\dots,P_{k-1}$ are distinct and $P_k=P_0$.

If e.g. $P_0$ loses together with $3$ mates $P_1$ must point at $P_2\neq P_0$ (probability $\frac{n-2}{n-1}$), $P_2$ must point at $P_3\notin\{P_0,P_1\}$ (probability $\frac{n-3}{n-1}$) and finally $P_3$ must point at $P_0$ (probability $\frac1{n-1}$).

This leads to $p_3=\frac{n-2}{n-1}\frac{n-3}{n-1}\frac{1}{n-1}$.

• This looks awesome but can you please provide an outline of where the $p_k$'s come from or at least point me to a reference? – Zhipu 'Wilson' Zhao Feb 13 '15 at 11:28

Equivalently to the other answers so far, it's $\displaystyle\sum_{k=2}^n\frac{(k-1)!\binom{n-1}{k-1}}{(n-1)^k}$, or to make the sum work out nicely (adding the missing first term and shifting the index $k$ by one): $$-\frac{1}{n-1}+\displaystyle\sum_{k=0}^{n-1}\frac{k!\binom{n-1}{k}}{(n-1)^{k+1}}$$

I'd just like to note that this can be simplified via using generating functions. We start with the simple generating function $$(1+x)^{n-1}=\displaystyle\sum_{k=0}^{n-1}\binom{n-1}{k}x^k.$$ Note that for $y$ positive, $\displaystyle\int_0^{\infty}x^ke^{-x/y}dx=y^{k+1}\displaystyle\int_{0}^{\infty}z^ke^{-z}dz=k!y^{k+1}$ (using the substitution $x=yz$).

This is a convenient tool allowing us to get the desired $k!$ in our generating function. In particular, we find that

$$\displaystyle\int_0^{\infty}(1+x)^{n-1}e^{-x/y}dx=\displaystyle\sum_{k=0}^{n-1}\binom{n-1}{k}\displaystyle\int_0^{\infty}x^ke^{-x/y}dx=\displaystyle\sum_{k=0}^{n-1}k!\binom{n-1}{k}y^{k+1}.$$

Now the idea is clear, as we have that subsituting $y=\frac{1}{n-1}$, $$\displaystyle\sum_{k=0}^{n-1}\frac{k!\binom{n-1}{k}}{(n-1)^{k+1}}=\displaystyle\int_0^{\infty}(1+x)^{n-1}e^{-(n-1)x}dx=\displaystyle\int_0^{\infty}((1+x)e^{-x})^{n-1}dx,$$ so we have that the probability with $n$ people is $$P_n=-\frac{1}{n-1}+\displaystyle\int_0^{\infty}((1+x)e^{-x})^{n-1}dx.$$ This integral formulation is nice in that it allows us to evaluate this asymptotically, as the integral is $$\displaystyle\int_0^{\infty}e^{(n-1)(\ln(1+x)-x)}dx\approx\displaystyle\int_0^{\infty}e^{(n-1)(-x^2/2)}dx$$ for large $n$, which is a Gaussian integral and evaluates to $\sqrt{\frac{\pi}{2(n-1)}}$. The $\frac{1}{n-1}$ term can thus be ignored and we get an asymptotic result of $\sqrt{\frac{\pi}{2(n-1)}}$.

Let's play this game with $n$ people. I'll call a graph coming from a play of this game a round. Since each person has $n-1$ choices of whom to point to, there are $(n-1)^{n}$ possible rounds.

Let us calculate the number of rounds in which Person $1$ loses.

Of course in every round, every vertex has out-degree exactly $1$. It follows that if Person $1$ loses in a given round, then the cycle they are on is a directed cycle and, moreover, they are in exactly one directed cycle.

If Person $1$ loses because they are in a directed $k$-cycle for some $k\geq 2$, then there are ${n-1\choose k-1}$ choices of people that they can be involved in a $k$-cycle with, and $(k-1)!$ different directed cycles involving just these people. So there are $(k-1)!{n-1\choose k-1}(n-1)^{n-k}$ such rounds.

Note that we are not over-counting anywhere here since it cannot be the case that Person $1$ is in more than one cycle.

Thus the probability of Person $1$ losing is $$\frac{\sum_{k=2}^n(k-1)!{n-1\choose k-1}(n-1)^{n-k}}{(n-1)^n}$$

For $n=6$, this amounts to a probability of a little over a half ($0.50208$).