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}$

$\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 H_m 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:

“I call it our collective inheritance of isolation. We inherit isolation in the bones of our lives. It is passed on to us as sure as the shape of our noses and the length of our legs. When we are young, we are taught to keep to ourselves for reasons we may not yet understand. As we grow up we become the “men who never cry” and the “women who never complain.” We become another generation of people expected not to bother others with our problems.”
—Paula C. Lowe (20th century)

“I who have been involved with all styles of painting can assure you that the only things that fluctuate are the waves of fashion which carry the snobs and speculators; the number of true connoisseurs remains more or less the same.”
—Pablo Picasso (1881–1973)

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

“To believe her limited in range because she was harmonious in method is as sensible as to imagine that when the Atlantic Ocean is as smooth as a mill-pond it shrinks to the size of a mill-pond.”
—Rebecca West (1892–1983)