The CSAT and Practice[+] are designed by the Climb Foundation to help candidates. We are advocates for more opportunity to shine and less opportunity to fail, and we strive to level the playing field.

The Computer Laboratory

Practice Paper 2 Question 9

Using a fair coin we can generate random integers in \(\{1,2,3,4\}\) with equal probability by doing:

  • \((a)\) toss coin, if heads go to \((b)\) otherwise go to \((c)\)
  • \((b)\) toss coin, if heads output \(1\) otherwise output \(2\)
  • \((c)\) toss coin, if heads output \(3\) otherwise output \(4\)

By altering just one of the lines \((a),\) \((b)\) or \((c),\) we can generate random integers in \(\{1,2,3\}\) with equal probability. Identify which line and give the new version. Prove that it is correct.

The above links are provided as is. They are not affiliated with the Climb Foundation unless otherwise specified.

Warm-up Questions

  1. You roll a die \(3\) times. What is the probability of getting \(1,2\) and \(3\) in any order?
  2. A geometric series has terms \(3, 6, 12, 24, 48, \ldots.\) Find an expression for the \(n^{th}\) term in the sequence, in terms of \(n.\)

Hints

  • Hint 1
    Which of the \(3\) lines must we definitely change?
  • Hint 2
    You are allowed to go to another step, as done in step (a).
  • Hint 3
    ... you are also allowed to output a number for heads, and go to another step for tails.
  • Hint 4
    If you change \((c)\) to output 3 for heads and go to a another step for tails, which step should that be?
  • Hint 5
    Focus on the possible sequences of coin tosses that will output \(1\) (for now). Notice any pattern?
  • Hint 6
    Try expressing the probability of each sequence of coin tosses in terms of the length of the sequence.
  • Hint 7
    Sequences are independent. What can you say about the total probability of outputting \(1?\)
  • Hint 8
    What about the probabilities of outputting \(2\) and \(3?\)

Solution

Since we are not outputting \(4,\) we must change the second part of \((c)\) and we must go to another step instead of outputting \(4.\) Going to any other step than to (a) would make the probabilities of 1, 2, 3 unequal (this is easy to verify). Hence the only viable option is to go to (a) instead of outputting 4:

\((c)\) toss coin, if heads output \(3\) otherwise go to \((a)\)

To prove the probabilities are indeed equal, let's consider first the probability \(P(1)\) of outputting \(1,\) which we get when we flip \(HH\) or \(TTHH\) or \(TTTTHH\) and so on. The probability of flipping any particular sequence of heads or tails of length \(k\) is \(\big(\frac{1}{2}\big)^k.\) Therefore \(P(1)\) is just the sum of the even powers of \(\frac{1}{2}\) (infinite geometric series): \[ P(1) = \sum_{n=1}^{\infty}\frac{1}{4^n} = \frac{1/4}{1-1/4} = \frac{1}{3}. \] Probabilities for \(2\) and \(3\) are the same by symmetry of the coin.

If you have queries or suggestions about the content on this page or the CSAT Practice Platform then you can write to us at oi.foo[email protected]. Please do not write to this address regarding general admissions or course queries.