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:

    “Don’t be so ready to defy everybody. Act as if you expected to have your own way, not as if you expected to be ordered about. The way to get on as a lady is the same as the way to get on as a servant: you’ve got to know your place.”
    —George Bernard Shaw (1856–1950)

    “You are the majority—in number and intelligence; therefore you are the force—which is justice. Some are scholars, others are owners; a glorious day will come when the scholars will be owners and the owners scholars. Then your power will be complete, and no man will protest against it.”
    —Charles Baudelaire (1821–1867)

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

    “Eat your meals according to the size of your bowl.”
    —Chinese proverb.