What’s the expected number of fixed points of a uniformly distributed random permutation of elements?

Advertisements

Skip to content
# Still expecting my fix

##
2 thoughts on “Still expecting my fix”

### Leave a Reply

What’s the expected number of fixed points of a uniformly distributed random permutation of elements?

Advertisements

%d bloggers like this:

Burnside’s lemma?

LikeLiked by 2 people

Consider a permutation of , and let be the random variable that takes the value if this permutation fixes , and takes the value zero elsewhen. Set .

For every , . By the linearity of the spected value, . So, the expected number of fixed points is independently of .

Let’s compute its variance. If , obviously . In the case we have

But and takes the value if and are fixed points and takes the value otherwise. Thus

So, for its variance is also independently of .

A related topic is https://thenoriegabook.wordpress.com/2016/04/16/derrangements/

LikeLiked by 2 people