Archive for October, 2009

Linear algebra viewpoint of function of discrete random variable

Suppose X is a discrete random variable can take on n values x_{1} < x_{2} <\ldots <x_{n} with probability p_{x_{1}},p_{x_{2}},\ldots ,p_{x_{n}}; and Y is a random variable defined by Y = g(X).

Continue reading

Advertisements

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

Exercise 3.21: A fixed point of a permutation \pi : [1,n] \to [1,n] is a value for which \pi (x) = x. Find the variance in the number of fixed points of a permutation chosen uniformly at random from all permutations. (Hint: Let X_{i} be 1 if \pi (i) =i, so that \sum_{i=1}^{n}X_{i} is the number of fixed points. You cannot use linearity to find Var[\sum_{i=1}^{n}X_{i}], but you can calculate it directly.)

Continue reading

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

Exercise 3.15: Let the random variable X be representable as a sum of random variables X=\sum_{i=1}^{n}X_{i}. Show that, if E[X_{i}X_{j}]=E[X_{i}]E[X_{j}] for every pair of i and j with 1 \leq i <j\leq n, then Var[X] = \sum_{i=1}^{n}Var[X_{i}].

Continue reading

Probability and Computing: Chapter 3 Exercises

Exercise 3.2: Let X be a number chosen uniformly at random from [-k,k]. Find Var[X].

Continue reading

Bounding probability of an event

1.

– If  A \Rightarrow B then Pr(A) \leq Pr(B).

– If A \Rightarrow B and A \Rightarrow C then Pr(A) \leq \frac{1}{2}(Pr(B) +Pr(C)).

Continue reading

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

Continue reading

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

Exercise 2.22: Let a_{1},a_{2},\ldots ,a_{n} be a list of n distinct numbers. We say that a_{i} and a_{j} are inverted if i<j but a_{i}>a_{j}. 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 n! permutations of the n distinct numbers. Determine the expected number of inversions that need to be corrected by Bubblesort.

Continue reading