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:

    Liberty is a blessing so inestimable, that, wherever there appears any probability of recovering it, a nation may willingly run many hazards, and ought not even to repine at the greatest effusion of blood or dissipation of treasure.
    David Hume (1711–1776)

    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)

    There is probably an element of malice in the readiness to overestimate people: we are laying up for ourselves the pleasure of later cutting them down to size.
    Eric Hoffer (1902–1983)

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

    O hideous little bat, the size of snot,
    With polyhedral eye and shabby clothes,
    Karl Shapiro (b. 1913)