Probability of at least x Hamiltonian paths in a random tournament

Question

Let $X$ be a random variable denoting the number of Hamiltonian paths in a random tournament with $n$ vertices. I'm trying to compute the probability that there are at least $x$ such paths in the random tournament. My thinking is that there are $n!$ permutations of the vertices and therefore $n!$ total Hamiltonian paths in the random tournament. The probability that a given permutation contains a Hamiltonian path is $(\frac{1}{2})^{n - 1}.$ Then $$Pr[X >= x] = 1 - \Pr[X < x] = 1 - \sum_{k = 0}^{x - 1} C(n!, k) \cdot (1/2)^{n - 1}.$$ Am I on the right track? If so, how can this expression be simplified?

Answer 1

Even if the Hamiltonian paths were independent, the probability of seeing exactly $k$ Hamiltonian paths would not be $\binom{n!}{k} \frac1{2^{n-1}}$ as it is in your answer: it would be $$\binom{n!}{k} \left(\frac1{2^{n-1}}\right)^k \left(1 - \frac1{2^{n-1}}\right)^{n!-k}.$$ So this is what a term in your summation should look like.

However, the summation will still not give the correct answer, because Hamiltonian paths are not independent. If one particular path is present, then paths that share many edges with it are more likely to appear, and paths that contain any edges going the other way are guaranteed not to appear. This is pretty much impossible to take into account systematically. In particular, we have $\Pr[X=0] = 0$, since any tournament contains a Hamiltonian path.

We can compute the expected value $\mathbb E[X]$ more easily: it is $\frac{n!}{2^{n-1}}$ by linearity of expectation, since there are $n!$ possible Hamiltonian paths and each of them appears with probability $\frac1{2^{n-1}}$.

This can give us some upper and lower bounds on $\Pr[X \ge x]$. For example:

• We have $\Pr[X \ge x] \le \frac{\mathbb E[X]}{x} = \frac{n!}{x \cdot 2^{n-1}}$, by Markov's inequality.
• We have $\Pr[X \ge x] \ge \frac{\mathbb E[X]-x}{n!-x}$ by making use of the fact that $X$ can never be larger than $n!$.

These are not very good bounds; more can be learned from understanding, for example, higher moments of $X$ such as $\mathbb E[X^2]$.