Suppose is a discrete random variable can take on values with probability ; and is a random variable defined by .

## Archive for October, 2009

8 Oct

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

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

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

**Exercise 2.22: **Let be a list of distinct numbers. We say that and are *inverted *if but . The *Bubblesort* algorithm swaps pairwise adjacent inverted numbers in the list until their are no more inversions, so the list is sorted in order. Suppose that the input to Bubblesort is a random permutation, equally likely to be any of the permutations of the distinct numbers. Determine the expected number of inversions that need to be corrected by Bubblesort.

## Recent Comments