Expected number of cycles in a random tournament

136 Views Asked by At

What is the expected number of cycles (of each length, if you like) in a tournament of order $n$ where the direction of each edge is decided uniformly at random?

The case $n = 3$ is trivial to calculate exactly, and I computed estimates for $n \leq 10$, but I'm sure there's a nice way to determine this with a counting argument or recurrence relation.

1

There are 1 best solutions below

2
On BEST ANSWER

Let $X_G$ be the number of directed cycles in a random tournament $G$ of order $n$ where the direction of each edge is decided uniformly at random. Now, for each undirected cycle $C$ in $G$, define the random variable

$$X_C=\begin{cases} 1&\text{ if $C$ is a directed cycle in $G$}\\ 0&\text{ if $C$ is not a directed cycle in $G$}\\ \end{cases}$$

and note that $X_G=\sum_{C\in\mathcal U} X_C$ where $\mathcal{U}$ is the set of undirected cycles $C$ in $G$. By the linearity of expectation, we may write

$$\mathbb{E}[X_G]=\sum_{C\in\mathcal{U}}\mathbb{E}[X_C]=\sum_{C\in\mathcal{U}}\mathbb{P}(C\text{ is a directed cycle in } G)$$

Now all that remains is to note that for $k\geq 3$, the probability that an undirected $k$-cycle $C$ in $G$ is a directed cycle in $G$ is given by $\frac1{2^{k-1}}$, and the number of undirected $k$-cycles $C$ in $G$ is given by $\binom{n}{k}\frac{(k-1)!}2$. Therefore, the expected number of directed cycles in a random tournament $G$ of order $n$ is

$$\mathbb{E}[X_G]=\sum_{k=3}^n\binom{n}{k}\frac{(k-1)!}{2^k}$$