Random Permutation Statistics - Expected Cycle Size of A Random Element

Expected Cycle Size of A Random Element

We select a random element q of a random permutation and ask about the expected size of the cycle that contains q. Here the function is equal to, because a cycle of length k contributes k elements that are on cycles of length k. Note that unlike the previous computations, we need to average out this parameter after we extract it from the generating function (divide by n). We have

\frac{\partial}{\partial u} g(z, u) \Bigg|_{u=1} = \frac{1}{1-z} \sum_{k\ge 1} k^2 \frac{z^k}{k} = \frac{1}{1-z} \frac{z}{(1-z)^2} = \frac{z}{(1-z)^3}.

Hence the expected length of the cycle that contains q is

\frac{1}{n} \frac{z}{(1-z)^3} = \frac{1}{n} \frac{1}{2} n (n+1) = \frac{1}{2} (n+1).

Read more about this topic:  Random Permutation Statistics

Famous quotes containing the words expected, cycle, size, random and/or element:

    “Accidents will occur in the best regulated families; and in families not regulated by that pervading influence which sanctifies while it enhances the—a—I would say, 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)

    “Only mediocrities progress. An artist revolves in a cycle of masterpieces, the first of which is no less perfect than the last.”
    —Oscar Wilde (1854–1900)

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

    “Man always made, and still makes, grotesque blunders in selecting and measuring forces, taken at random from the heap, but he never made a mistake in the value he set on the whole, which he symbolized as unity and worshipped as God. To this day, his attitude towards it has never changed, though science can no longer give to force a name.”
    —Henry Brooks Adams (1838–1918)

    “The element running through entire nature, which we popularly call Fate, is known to us as limitation. Whatever limits us, we call Fate.”
    —Ralph Waldo Emerson (1803–1882)