Computer Laboratory > Teaching > Course material 2009–10 > Mathematical Methods for Computer Science > Revision exercises


Revision exercises on Probability

  1. Derive the Moment Generating Function for a Poission distribution.
    Use this to show that the sum of n independent Poission variables with means λ1, λ2, ..., λn is itself a Poisson variable with mean λ12+...+λn.
    Let Sn be the sum of n independent, identically distributed Poission variables each with mean λ, let Xn be Sn/n and let Zn be (Xn-λ)/(√λ/√n). Derive the MGFs for Xn and for Zn.
    Consider the limit of the MGF for Zn as n becomes large. How does this relate to the Central Limit Theorem?
  2. CST 2008 Paper 4 Question 4 (random walk and gambler's ruin)
    Hint: The second part of the question was not covered in lectures this year, but is fairly straightforward probability. Let ra be the probability of ruin starting with a capital of a. Consider the first time step to express ra in terms of ra+1 and ra-1 for 0<a<N. Establish boundary conditions for r0 and rN. Solve the resulting second order linear difference equation, bearing in mind the possibility of degenerate special cases.
  3. Consider a Markov chain with transition matrix P, such that the states constitute a single class. Relate the nature of these states to the solutions to πP=π.
    A prisoner on Devil's Island has probability p0 of escaping on any given day; if he is still free i days after the escape, the he will continue to evade capture for a further day with probability pi. If recaptured, he immediately resumes his attempts at escape. Formulate a Markov chain that models the number of days for which he reamins free after each attempt to escape.
    Show that 'ultimate escape' (appropriately defined) is almost certain if Πpi>0, and has zero probability otherwise.
    Relate these two cases to the character of the process.
  4. A slot machine works on inserting a penny. If the player wins, the penny is returned with an additional penny, otherwise the original penny is lost. The probability of winning is arranged to be 1/2 (independently of previous plays) unless the previous play has resulted in a win, in which case the probability is p<1/2. If the cost of maintaining the machine averages c pence per play, show that the owner must arrange that p<(1-3c)/2(1-c) (with c<1/3) in order to make a profit in the long run.
    A player determines to play the machine until he has won r times in succession. Calculate the expected number of plays required to achieve this.