Random Permutation Statistics - Probability That A Random Element Lies On A Cycle of Size m

Probability That A Random Element Lies On A Cycle of Size m

This average parameter represents the probability that if we again select a random element of of a random permutation, the element lies on a cycle of size m. The function is equal to for and zero otherwise, because only cycles of length m contribute, namely m elements that lie on a cycle of length m. We have

\frac{\partial}{\partial u} g(z, u) \Bigg|_{u=1} = \frac{1}{1-z} \sum_{k\ge 1} b(k) \frac{z^k}{k} = \frac{1}{1-z} \; m \; \frac{z^m}{m} = \frac{z^m}{1-z}.

It follows that the probability that a random element lies on a cycle of length m is

\frac{1}{n} \frac{z^m}{1-z} = \begin{cases} \frac{1}{n}, & \mbox{if }n\ge m \\ 0, & \mbox{otherwise.} \end{cases}

Read more about this topic:  Random Permutation Statistics

Famous quotes containing the words probability, random, element, lies, cycle and/or size:

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

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

    “One can describe a landscape in many different words and sentences, but one would not normally cut up a picture of a landscape and rearrange it in different patterns in order to describe it in different ways. Because a photograph is not composed of discrete units strung out in a linear row of meaningful pieces, we do not understand it by looking at one element after another in a set sequence. The photograph is understood in one act of seeing; it is perceived in a gestalt.”
    —Joshua Meyrowitz, U.S. educator, media critic. “The Blurring of Public and Private Behaviors,” No Sense of Place: The Impact of Electronic Media on Social Behavior, Oxford University Press (1985)

    “War has always been the great wisdom of all those spirits who have grown too inward, too deep; its healing power lies even in the wound.”
    —Friedrich Nietzsche (1844–1900)

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

    “The obese is ... in a total delirium. For he is not only large, of a size opposed to normal morphology: he is larger than large. He no longer makes sense in some distinctive opposition, but in his excess, his redundancy.”
    —Jean Baudrillard (b. 1929)