Still expecting my fix

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

Advertisements
Still expecting my fix

2 thoughts on “Still expecting my fix

  1. Consider a permutation \sigma of [n], and let X_n^j be the random variable that takes the value 1 if this permutation fixes j, and takes the value zero elsewhen. Set X_n= \sum_{j=1}^n X_n^j.
    For every j\in [n], P(X_n^j=1)=(n-1)!/n!=1/n. By the linearity of the spected value, E[X_n]= \sum_{j=1}^nE[X_n^j] = \sum_{j=1}^n1/n =n/n=1. So, the expected number of fixed points is 1 independently of n\in\mathbb{N}.

    Let’s compute its variance. If n=1, obviously Var[X_1]=0. In the case n>1 we have Var[X_n]=E[(X_n)^2]-E[X_n]^2 = E[(\sum_{j=1}^n X_n^j)^2]-1 = E[\sum_{j=1}^n (X_n^j)^2] + 2E[\sum_{j\neq i}X_n^jX_n^i] -1
    But (X_n^j)^2=X_n^j and X_n^jX_n^i takes the value 1 if i and j are fixed points and takes the value 0 otherwise. Thus Var[X_n] = E[\sum_{j=1}^n X_n^j] + 2\sum_{j\neq i}E[X_n^jX_n^i] -1 = 1 +2\sum_{j\neq i}(n-2)!/n! -1 = 2\sum_{j\neq i}1/(n-1)n = 2\binom{n}{2}1/(n-1)n = 2(n!)/2!(n-2)!(n-1)n = 1
    So, for n>1 its variance is also 1 independently of n.

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

    Liked by 2 people

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s