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)

    “Beside all the small reasons we assign, there is a great reason for the existence of every extant fact; a reason which lies grand and immovable, often unsuspected behind it in silence.”
    —Ralph Waldo Emerson (1803–1882)

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