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

or

\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:

    “Only in Britain could it be thought a defect to be “too clever by half.” The probability is that too many people are too stupid by three-quarters.”
    —John Major (b. 1943)

    “Novels as dull as dishwater, with the grease of random sentiments floating on top.”
    —Italo Calvino (1923–1985)

    “Perchance the time will come when we shall not be content to go back and forth upon a raft to some huge Homeric or Shakespearean Indiaman that lies upon the reef, but build a bark out of that wreck and others that are buried in the sands of this desolate island, and such new timber as may be required, in which to sail away to whole new worlds of light and life, where our friends are.”
    —Henry David Thoreau (1817–1862)

    “The cycle of the machine is now coming to an end. Man has learned much in the hard discipline and the shrewd, unflinching grasp of practical possibilities that the machine has provided in the last three centuries: but we can no more continue to live in the world of the machine than we could live successfully on the barren surface of the moon.”
    —Lewis Mumford (1895–1990)