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)

    “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)

    “That the discovery of this great truth, which lies so near and obvious to the mind, should be attained to by the reason of so very few, is a sad instance of the stupidity and inattention of men, who, though they are surrounded with such clear manifestations of the Deity, are yet so little affected by them, that they seem as it were blinded with excess of light.”
    —George Berkeley (1685–1753)

    “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)