The cycle structure of twisted wires, connected - MathOverflow

The cycle structure of twisted wires, connected

2012-10-06T13:56:13Z

Suppose you have $n$ (blue) wires linearly arrayed at junction box $A$, connected to a remote junction box $B$, where the wires are now arrayed along a line in a randomly permuted order, i.e., each of the $n!$ permutations is equally likely at $B$. Now you tie together every other wire at $A$ and at $B$ with a (green) connector, like this:

What is the probability that you have formed a single cycle (as illustrated)? More generally, what are the combinatorics of the cycle structures achievable in this manner? (It may be best to separate out the $n$-even case from $n$ odd.)

I came upon this thinking of the wires as an arrangement of lines, where each line crosses every other before reaching junction box $B$, in which case, for $n$ even, one necessarily arrives at $n/2$ cycles, each containing two (blue) wires. All $n$ wires in a single cycle is in some sense the obverse situation.

Update. Will Swain's argument shows, as Noam points out, that the probability of a single cycle is asymptotically $\frac{1}{\sqrt{n}}$. I would be interested to learn if there is a way to see this intuitively without Will's explicit calculation. Perhaps an assessment of the probability of repeatedly avoiding premature closing of a loop as one criss-crosses from $A$ to $B$...?

Answer by Will Sawin for The cycle structure of twisted wires, connected

2012-10-06T14:21:08Z

Untangle the permutation as a big cycle green-blue-green-blue, and choose an orientation. We're going to count the posible shapes for this cycle, with the vertices labeled by their original position. We first have an alternating cyclic permutation of all the green wires. There are $(n/2)!\cdot (n/2)!/(n/2)$ ways to do this. Then we can choose an orientation of each of the green wires. There are $2^n$ ways to do this. Finally we note that two big cycles with reversed orientation correspond to the same permutation, so we divide by $2$. The total number of ways to get one big cycle is:

$\frac{2^n \left(\frac{n}{2}\right)!\left(\frac{n}{2}\right)!}{n}$

and the probability is:

$\frac{2^n \left(\frac{n}{2}\right)!\left(\frac{n}{2}\right)!}{n\cdot n!}$

which as Noam Elkies points out is asymptotically proportional to $n^{-1/2}$.

Answer by Kevin P. Costello for The cycle structure of twisted wires, connected

2012-10-09T20:27:50Z

Here's an alternative way of thinking about the problem and Will's answer in the case where $n$ is even.

If we identify the identically labelled vertices on each side, we're left with a graph on $n$ vertices formed by the union of two matchings: The fixed matching ($(1,2), (3,4), \dots, (n-1,n)$) and a random matching. Now imagine exposing the random matching one edge at a time.

At the start (before the new matching is exposed), we have a set of $n/2$ isolated edges. There's a $\frac{1}{n-1}$ chance that the first exposed edge in the second matching is already in the first matching, leaving us with a closed loop together with $n-1$ isolated edges. Otherwise, we have a single path of length $2$ together with $n-2$ isolated edges.

When the next edge is exposed, its endpoints are chosen uniformly at random from the degree $1$ vertices. It closes a cycle if the two endpoints are from the same path. The key thing here is that there's always $\frac{n}{2}-1$ open paths that can be closed, regardless of what happened in the previous edge. This is true in general: Whether an edge closes an existing path off or connects two paths, it always reduces the number of open paths by exactly $1$. So as the $k^{th}$ edge in the new matching is exposed, there's $\frac{n}{2}+1-k$ open paths and a $\frac{1}{n-2k+1}$ chance of closing one of them.

It follows that the number of cycles can be thought of as $x_1+\dots+x_{n/2}$, where the $x_i$ are independently $1$ with probability $\frac{1}{2i-1}$ and $0$ otherwise. This means that

-The probability that there's exactly one cycle (that $x_2=x_3=\dots=0$) is $$\frac{2}{3} \frac{4}{5} \dots \frac{n-2}{n-1} = \frac{2^n \left(\frac{n}{2}!\right)^2}{n\cdot n!}$$

-The expected number of cycles is $\frac{1}{1}+\frac{1}{3}+\dots+\frac{1}{n-1} \approx \frac{1}{2} \log n$

-The number of cycles is reasonably concentrated around its mean (e.g. by Chernoff's bound we have $$P(|X-E(X)| \geq \frac{1}{2} E(X) ) \leq 2 e^{-E(X)/16} = 2n^{-1/32})$$