**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.)

## Archive for the ‘Solutions’ Category

8 Oct

### Probability and Computing: Chapter 3 Exercises (cont.3)

8 Oct

### Probability and Computing: Chapter 3 Exercises (cont.2)

**Exercise 3.15: **Let the random variable be representable as a sum of random variables . Show that, if for every pair of and with , then .

8 Oct

### Probability and Computing: Chapter 3 Exercises

**Exercise 3.2: **Let be a number chosen uniformly at random from . Find .

4 Oct

### Probability and Computing: Chapter 2 Exercises (Cont. 4)

**Exercise 2.34: **We roll a standard fair dice over and over. What is the expected number of rolls until the first pair of consecutive sixes appears? (*Hint*: The answer is not 36.)

2 Oct

### Probability and Computing: Chapter 2 Exercises (Cont. 2)

**Exercise 2.18:** The following approach is often called *reservoir sampling. *Suppose we have a sequence of item passing by one at a time. We want to maintain a sample of one item with the property that it is uniformly distributed over all the items that we have seen at each step. Moreover, we want to accomplish this without knowing the total number of items in advance or storing all of the items that we see.

Consider the following algorithm, which store just one item in memory at all times. When the first item appears, it is stored in the memory. When the th item appears, it replaces the item in memory with probability . Explain why this algorithm solves the problem.

2 Oct

### Probability and Computing: Chapter 2 Exercises (Cont. 1)

**Exercise 2.14: **The geometric distribution arise as the distribution of the number of times we flip a coin until it comes up heads. Consider now the distribution of the number of flips until the th head appears, where each coin flip comes up heads independently with probability . Prove that this distribution is given by

for . (This is known as the *negative binomial* distribution.**)**

2 Oct

### Probability and Computing: Chapter 2 Exercises

**Exercise 2.5**: If is a random variable with , show that the probability that is even is .

.

Since only depends on , all we need to prove is : .

Indeed, we have .

**Exercise 2.6**: Suppose that we independently roll two standard six-sided dice. Let be the number that shows on the first dice, the number on the second dice, and X the sum of the numbers of two dice.

## Recent Comments