6
$\begingroup$

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

$\endgroup$
5
$\begingroup$

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.


addendum:

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}$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Zhipu 'Wilson' Zhao Feb 13 '15 at 11:28
3
$\begingroup$

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)}}$.

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

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$).

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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