Random Tournaments

873 Views Asked by At

A tournament is a directed graph in which every pair of vertices has exactly one directed edge between them—for example, here are two tournaments on the vertices {1,2,3}:

Hamiltonian Cycle Image

(1,2,3) is a Hamiltonian path, since it visits all the vertices exactly once, without repeating any edges, but (1,2,3,1) is not a valid Hamiltonian cycle, because the tournament contains the directed edge 1 → 3 and not 3 → 1. In the second tournament, (1,2,3,1) is a Hamiltonian cycle, as are (2,3,1,2) and (3,1,2,3); for this problem we’ll say that these are all different Hamiltonian cycles, since their start/end points are different.

Consider the following way of choosing a random tournament T on n vertices: independently for each (unordered) pair of vertices {i, j} ⊂ {1,...,n}, flip a coin and include the edge i → j in the graph if the outcome is heads, and the edge j → i if tails. What is the expected number of Hamiltonian paths in T? What is the expected number of Hamiltonian cycles?

1

There are 1 best solutions below

0
On

To find the expected number of Hamiltonian paths, you need to find two things:

  1. $N$, the total number of paths that could be Hamiltonian paths in the tournament. (So, the number of ways to put all $n$ vertices in order.)

  2. $p$, the probability that a particular path does end up a Hamiltonian path. (The probability that all the arcs between the vertices have the correct direction.)

Then the expected number of Hamiltonian paths is just the product $Np$.

I'm not going to compute $N$ and $p$ for you, you will have to do that yourself.


To see why this happens, we can use linearity of expectation. The formal argument is this. We can write $X$, the number of Hamiltonian paths, as $X_1 + X_2 + \dots + X_N$, where $X_i$ is the indicator variable for the $i^{\text{th}}$ Hamiltonian path: it is $1$ if the $i^{\text{th}}$ sequence of vertices forms a Hamiltonian path, and $0$ if it doesn't. Then $$\mathbb E[X] = \mathbb E[X_1 + X_2 + \dots + X_N] = \mathbb E[X_1] + \mathbb E[X_2] + \dots + \mathbb E[X_N].$$ Meanwhile, the expected value of $\mathbb E[X_i]$ is $p$ for any $i$: with probability $p$, $X_i=1$, and otherwise $X_i=0$. Therefore $$\mathbb E[X] = \underbrace{p + p + \dots + p}_{N \text{ times}} = Np.$$


For Hamiltonian cycles, you will have the same value of $N$, since in either case, you have to put all $n$ vertices in order. However, the probability $p$ will be different, since you're asking for more of the tournament's edges to have the right orientation.