**Exercise 3.21: **A fixed point of a permutation is a value for which . Find the variance in the number of fixed points of a permutation chosen uniformly at random from all permutations. (*Hint*: Let be if , so that is the number of fixed points. You cannot use linearity to find , but you can calculate it directly.)

**Solution:**

First we will calculate .

About :

We can calculate in the same way as with :

can be worked out as followed:

Then

So

**Exercise 3.22: **Suppose that we flip a fair coin times to obtain random bits. Consider all pairs of these bit in some order. Let be the exclusive-or of the th pair of bits, and let be the number of that equal to .

**(a) **Show that each is with probability and with probability .

**(b) **Show that the are not mutually independent.

**(c) **Show that the satisfy the property that .

**(d) **Using Exercise 3.15, find .

**(e) **Using Chebyshev’s inequality, prove a bound on .

**Exercise 3.25: **The weak law of large numbers state that, if are independent and identically distributed random variables with mean and standard deviation then for any constant we have

.

Use Chebyshev’s inequality to prove the weak law of large numbers.

**Solution: **Let .

.

Thus has standard deviation

For any constant we will have for all sufficiently large .

Applying Chebyshev’s inequality yields

for all sufficiently large .

Therefore