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:

    “Crushed to earth and rising again is an author’s gymnastic. Once he fails to struggle to his feet and grab his pen, he will contemplate a fact he should never permit himself to face: that in all probability books have been written, are being written, will be written, better than anything he has done, is doing, or will do.”
    —Fannie Hurst (1889–1968)

    “It is a secret from nobody that the famous random event is most likely to arise from those parts of the world where the old adage “There is no alternative to victory” retains a high degree of plausibility.”
    —Hannah Arendt (1906–1975)

    “The beauty myth moves for men as a mirage; its power lies in its ever-receding nature. When the gap is closed, the lover embraces only his own disillusion.”
    —Naomi Wolf (b. 1962)

    “Oh, life is a glorious cycle of song,
    A medley of extemporanea;
    And love is a thing that can never go wrong;
    And I am Marie of Roumania.”
    —Dorothy Parker (1893–1967)