Can anyone help me with this probability question??
You are out to dinner with two friends. You discover that there is only one remaining slice of chocolate cake, and so you all want to devise a fair way of choosing one person to receive the slice. All your friends have is a fair coin. Can you devise a fair way with this coin? How?
On
There are 3 friends "competing" for the remaining slice. Assign a number for to each of the friends starting at zero, and represent it as a binary number:
Now note that you used two binary digits to write down the respective number for each friend. This is how often you will have to toss the coin: Twice. The last thing you will need to do is map "head" to 0 and "tails" to 1 (or vice versa, doesn't matter).
Toss the coin twice and compare it with the binary representation of the number for each friend (comparing digits from left to right or right to left does not matter either, as long as you do it in the same direction for all of them). The one that matches, gets to eat the last piece.
Example: Say you tossed twice, and the coin came up heads (1), and tails (0). Reading the numbers from right to left, Friend two would get the last piece.
In case there is no match, just repeat the process.
You can generalize this approach for $n$ friends (longer list), and for experiments that have more then two (say $k$) outcomes (base $k$ instead of base 2).
You always can simulate the uniform law on $\{1, \ldots, n\}$ with a fair coin. The rough idea is quite natural: write $n$ in its binary development (say with $k$ digits, i.e. $n <2^k$), then toss a coin for each digit.
We quickly understand there is a slight "waste" of undesired possible numbers with this method (safe the ideal case $n=2^k$): if you hit such a number with the algorithm, you can restart, and the algorithm terminates with probability 1.