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:

    “The source of Pyrrhonism comes from failing to distinguish between a demonstration, a proof and a probability. A demonstration supposes that the contradictory idea is impossible; a proof of fact is where all the reasons lead to belief, without there being any pretext for doubt; a probability is where the reasons for belief are stronger than those for doubting.”
    —Andrew Michael Ramsay (1686–1743)

    “poor Felix Randal;
    How far from then forethought of, all thy more boisterous years,
    When thou at the random grim forge, powerful amidst peers,
    Didst fettle for the great gray drayhorse his bright and battering
    sandal!”
    —Gerard Manley Hopkins (1844–1889)

    “The great end of all human industry is the attainment of happiness. For this were arts invented, sciences cultivated, laws ordained, and societies modelled, by the most profound wisdom of patriots and legislators. Even the lonely savage, who lies exposed to the inclemency of the elements and the fury of wild beasts, forgets not, for a moment, this grand object of his being.”
    —David Hume (1711–1776)

    “The lifelong process of caregiving, is the ultimate link between caregivers of all ages. You and I are not just in a phase we will outgrow. This is life—birth, death, and everything in between.... The care continuum is the cycle of life turning full circle in each of our lives. And what we learn when we spoon-feed our babies will echo in our ears as we feed our parents. The point is not to be done. The point is to be ready to do again.”
    —Paula C. Lowe (20th century)