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)

    “There is a potential 4-6 percentage point net gain for the President [George Bush] by replacing Dan Quayle on the ticket with someone of neutral stature.”
    —Mary Matalin, U.S. Republican political advisor, author, and James Carville b. 1946, U.S. Democratic political advisor, author. All’s Fair: Love, War, and Running for President, p. 205, Random House (1994)

    “Man seeks to escape himself in myth, and does so by any means at his disposal. Drugs, alcohol, or lies. Unable to withdraw into himself, he disguises himself. Lies and inaccuracy give him a few moments of comfort.”
    —Jean Cocteau (1889–1963)

    “The Buddha, the Godhead, resides quite as comfortably in the circuits of a digital computer or the gears of a cycle transmission as he does at the top of a mountain or in the petals of a flower.”
    —Robert M. Pirsig (b. 1928)