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 with probability $p_{x_{1}},p_{x_{2}},\ldots ,p_{x_{n}}$; and $Y$ is a random variable defined by $Y = g(X)$.

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

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 , then $Var[X] = \sum_{i=1}^{n}Var[X_{i}]$.

Probability and Computing: Chapter 3 Exercises

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

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

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