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

## Related topics

## Warm-up Questions

- You roll a die \(3\) times. What is the probability of getting \(1,2\) and \(3\) in any order?
- 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 1Which of the \(3\) lines must we definitely change?
- Hint 2You 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 4If you change \((c)\) to output 3 for heads and go to a another step for tails, which step should that be?
- Hint 5Focus on the possible sequences of coin tosses that will output \(1\) (for now). Notice any pattern?
- Hint 6Try expressing the probability of each sequence of coin tosses in terms of the length of the sequence.
- Hint 7Sequences are independent. What can you say about the total probability of outputting \(1?\)
- Hint 8What 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.[email protected]. Please do not write to this address regarding general admissions or course queries.