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:

    “Vanessa wanted to be a ballerina. Dad had such hopes for her.... Corin was the academically brilliant one, and a fencer of Olympic standard. Everything was expected of them, and they fulfilled all expectations. But I was the one of whom nothing was expected. I remember a game the three of us played. Vanessa was the President of the United States, Corin was the British Prime Minister—and I was the royal dog.”
    —Lynn Redgrave (b. 1943)

    “In proportion as our inward life fails, we go more constantly and desperately to the post office. You may depend on it, that the poor fellow who walks away with the greatest number of letters, proud of his extensive correspondence, has not heard from himself this long while.”
    —Henry David Thoreau (1817–1862)

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

    “For truly I tell you, if you have faith the size of a mustard seed, you will say to this mountain, ‘Move from here to there,’ and it will move; and nothing will be impossible for you.”
    —Bible: New Testament, Matthew 17:20.