Random Permutation Statistics - Expected Number of Cycles of A Given Size m

Expected Number of Cycles of A Given Size m

In this problem we use a bivariate generating function g(z, u) as described in the introduction. The value of b for a cycle not of size m is zero, and one for a cycle of size 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} \frac{z^m}{m}

or

\frac{1}{m} z^m \; + \; \frac{1}{m} z^{m+1} \; + \; \frac{1}{m} z^{m+2} \; + \; \cdots

This means that the expected number of cycles of size m in a permutation of length n less than m is zero (obviously). A random permutation of length at least m contains on average 1/m cycles of length m. In particular, a random permutation contains about one fixed point.

The OGF of the expected number of cycles of length less than or equal to m is therefore

\frac{1}{1-z} \sum_{k=1}^m \frac{z^k}{k} \mbox{ and } \frac{1}{1-z} \sum_{k=1}^m \frac{z^k}{k} = H_m \mbox{ for } n \ge m

where Hm is the mth harmonic number. Hence the expected number of cycles of length at most m in a random permutation is about ln m.

Read more about this topic:  Random Permutation Statistics

Famous quotes containing the words expected, number, cycles and/or size:

    “Accidents will occur in the best-regulated families; and in families not regulated by that pervading influence which sanctifies while it enhances ... in short, by the influence of Woman, in the lofty character of Wife, they may be expected with confidence, and must be borne with philosophy.”
    —Charles Dickens (1812–1870)

    “Nothing ever prepares a couple for having a baby, especially the first one. And even baby number two or three, the surprises and challenges, the cosmic curve balls, keep on coming. We can’t believe how much children change everything—the time we rise and the time we go to bed; the way we fight and the way we get along. Even when, and if, we make love.”
    —Susan Lapinski (20th century)

    “The stars which shone over Babylon and the stable in Bethlehem still shine as brightly over the Empire State Building and your front yard today. They perform their cycles with the same mathematical precision, and they will continue to affect each thing on earth, including man, as long as the earth exists.”
    —Linda Goodman (b. 1929)

    “In mathematics he was greater
    Than Tycho Brahe, or Erra Pater:
    For he, by geometric scale,
    Could take the size of pots of ale;
    Resolve, by sines and tangents straight,
    If bread and butter wanted weight;
    And wisely tell what hour o’ th’ day
    The clock doth strike, by algebra.”
    —Samuel Butler (1612–1680)