3
$\begingroup$

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:
           Crossing Wires
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$...?

$\endgroup$
2
  • $\begingroup$ The only property I can recall (which may be irrelevant) is guaranteed length of monotonic subsequence of a permutation which is like 1 + sqrt(n-1). Also, I note a group theoretic rendering of Joseph's problem: given a green involution g on n letters, how many solutions psi are there to g^psi = gc, where c can be any of the cycles of n letters. Perhaps someone who is familiar with conjugacy classes in S_n can give Joseph what he wants. Gerhard "Not A Professional Group Theorist" Paseman, 2012.10.09 $\endgroup$ Oct 9, 2012 at 15:53
  • $\begingroup$ Maybe I mean c instead of gc. Gerhard "Someone Check My Work Please" Paseman, 2012.10.09 $\endgroup$ Oct 9, 2012 at 15:55

2 Answers 2

3
$\begingroup$

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

$\endgroup$
6
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ Interesting, Will! For $n=10$, that's 41%, but the expression of course goes to zero with large $n$. Thanks! $\endgroup$ Oct 6, 2012 at 15:16
  • 2
    $\begingroup$ Well $2^n (n/2)!^2 / (n \cdot n!)$ goes to zero as $n \rightarrow \infty$, but only as $n^{-1/2}$, not $o(2^{-n})$. It's still almost 4% for $n=1000$. In general it's the inverse of $n 2^{-n} {n \choose n/2}$, and we know that $2^{-n} {n \choose n/2}$ (which is the probability of an exact tie after $n$ fair coin tosses) is asymptotically proportional to $n^{-1/2}$. $\endgroup$ Oct 7, 2012 at 3:31
  • $\begingroup$ Naturally, I didn't remember the estimate correctly. That makes it seems like the probability that there are at most two cycles is quite large, since you shouldn't expect too large of a drop-off of probability from a cycle of length $n$ to two cycles, one of length $n-k$ and one of length $k$. $\endgroup$
    – Will Sawin
    Oct 7, 2012 at 5:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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