Random Permutation Statistics - Probability That A Random Subset of Lies On The Same Cycle

Probability That A Random Subset of Lies On The Same Cycle

Select a random subset Q of containing m elements and a random permutation, and ask about the probability that all elements of Q lie on the same cycle. This is another average parameter. The function b(k) is equal to, because a cycle of length k contributes subsets of size m, where for k < m. This yields

$\frac{\partial}{\partial u} g(z, u) \Bigg|_{u=1} = \frac{1}{1-z} \sum_{k\ge m} {k \choose m} \frac{z^k}{k} = \frac{1}{1-z} \frac{1}{m} \frac{z^m}{(1-z)^m} = \frac{1}{m} \frac{z^m}{(1-z)^{m+1}}.$

Averaging out we obtain that the probability of the elements of Q being on the same cycle is

${n \choose m}^{-1} \frac{1}{m} \frac{z^m}{(1-z)^{m+1}} = {n \choose m}^{-1} \frac{1}{m} \frac{1}{(1-z)^{m+1}}$

$\frac{1}{m} {n \choose m}^{-1} {(n-m) \; + \; m \choose m} = \frac{1}{m}.$

In particular, the probability that two elements p < q are on the same cycle is 1/2.

Read more about this topic: Random Permutation Statistics

Famous quotes containing the words probability, random, lies and/or cycle:

“The probability of learning something unusual from a newspaper is far greater than that of experiencing it; in other words, it is in the realm of the abstract that the more important things happen in these times, and it is the unimportant that happens in real life.”
—Robert Musil (1880–1942)

“Assemble, first, all casual bits and scraps
That may shake down into a world perhaps;
People this world, by chance created so,
With random persons whom you do not know—”
—Robert Graves (1895–1985)

“Here lies Jonson with the rest
Of the poets; but the best.
Reader, would’st thou more have known?
Ask his story, not this stone.
That will speak what this can’t tell
Of his glory. So farewell.”
—Robert Herrick (1591–1674)

“Only mediocrities progress. An artist revolves in a cycle of masterpieces, the first of which is no less perfect than the last.”
—Oscar Wilde (1854–1900)