Monday, 3 February 2014

Problem solving strategies

Students sometimes say that the theory in Probability IA is all very well, but that the tripos questions require ingenuity. That is sometimes true, of questions like 2004/II/12: "Planet Zog is a sphere with centre O. A number N of spaceships land at random on its surface. ... ". Of course this makes the subject fun.

But to help with this, let's compile a collection of some frequently helpful problem solving strategies. More will be added as the course progresses.
  1. You are asked to find $P(A)$. For example, $A$ might be the event that at least two out of $n$ people share the same birthday. Might it be easier to calculate $P(A^c)$? The simple fact that $P(A)=1-P(A^c)$ can sometimes be remarkably useful. For example, in Lecture 1 we calculated the probability that amongst $n$ people no two have the same birthday.
  2. You are asked to find $P(A)$. Is there a partition of $A$ into disjoint events, $B_1,B_2,\dotsc, B_n$, so that $P(A)=\sum_i P(B_i)$?
  3. Probabilities of intersections are usually easier to calculate than probabilities of unions. Fortunately, the inclusion-exclusion formula gives us a way to convert between the two. You are asked to find $P(A)$.  Can $A$ be written as the union of some other events? Might the inclusion-exclusion formula be helpful?
  4. The expectation of a sum of random variables is the sum of their expectations. The random variables need not be independent. This is particularly useful when applied to indicator random variables. You are asked to find $EN$, the expected number of times that something occurs. Can you write $N=I_1+\cdots+I_k$, where this is a sum of indicator variables, each of which is concerned with a distinct way in which $N$ can be incremented? This idea was used Example 8.3 in lectures, where $N$ was the number of couples seated next to one another. It is the way to do the Planet Zog question, mentioned above. You can use it in Examples sheet 2, #11.
  5. You are asked to place a bound on some probability. Can you use one of the inequalities that you know? Boole, Bonferroni, Markov, Chebyshev, Jensen, Cauchy-Schwarz, AM-GM. The ones in bold are key ones.
  6. You are asked something about sums of independent random variables. Might a probability generating function help? For example, suppose $X$ has the discrete uniform distribution $P(X=r)=1/(n+1)$, $r=0,1,\dotsc,n$. Is it possible for $X$ to have the same distribution as $Y_1+Y_2$, where $Y_1$, $Y_2$ are some two independent random variables with the same distribution? Hint: what would the p.g.f. of $Y_i$ have to be?
  7. This is like 2 above, but with the tower property of conditional expectation. You are asked to find $EX$. Maybe there is some $Y$ so that $E[X]$ is most easily computed as $E[E[X\mid Y]]=\sum_y E[X \mid Y=y]\,P(Y=y)$.
  8. It is often useful to use what you know about the relations between different standard distributions. For example, if $X\sim U[0,1]$ then $-\log X\sim \mathscr{E}(1)$. So make sure to learn well all the distributions that we cover in the course and understand the relations between them. Recall their special properties: such the memoryless property of the geometric and exponential distributions. As you approach a question ask yourself, what distribution(s) are involved in this question?
  9. You are given the joint density function of continuous random variables $X_1,\dotsc,X_n$ and want to prove that they are independent. Try to spot, by inspection, how to factor this as $f(x_1,\dotsc,x_n)=f_1(x_i)\cdots f_n(x_n)$, where each $f_i$ is a p.d.f.
  10. In questions about transformation of continuous random variables there are a couple things to look out for. Always start with a bijection between $R\subseteq\mathbb{R}^n$ and $S\subseteq\mathbb{R}^n$ and make sure that you specify $S$ correctly. If $Y_1,\dotsc,Y_n$ is more variables that really interest you, then you can always integrate the unneeded ones out at the end. In computing the Jacobian $J$, remember that it is sometimes easier to compute $1/J= \partial(y_1,\dotsc,y_n)/\partial(x_1,\dotsc,x_n)$.