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.
-
- 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.$
- You roll a die
-
Which of the
$3$lines must we definitely change? -
You are allowed to go to another step, as done in step (a).
-
… you are also allowed to output a number for heads, and go to another step for tails.
-
If you change
$(c)$to output 3 for heads and go to a another step for tails, which step should that be? -
Focus on the possible sequences of coin tosses that will output
$1$(for now). Notice any pattern? -
Try expressing the probability of each sequence of coin tosses in terms of the length of the sequence.
-
Sequences are independent. What can you say about the total probability of outputting
$1?$ -
What about the probabilities of outputting
$2$and$3?$
-
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.