Making it happen
Challenge 2
Given a coin, compute Random(a,b) that is x, a <= x <= b, each number between a and b having the same probability to be chosen. What's the expected time for your function ?
Does anyone know a better solution than (b-a)/2 ?
| Print article | This entry was posted by andrei on August 30, 2006 at 11:59 am, and is filed under Uncategorized. Follow any responses to this post through RSS 2.0. You can leave a response or trackback from your own site. |
about 5 years ago
think of binary search. first flip => the number is in one half or the other (you make a convention, heads=first half, tails=second half). second flip decides which of the halves from the new area.
the function will have a O(log2(b-a)) complexity
about 5 years ago
forgot to mention, the algorithm goes on and on until there’s a single number left.
about 5 years ago
What you said only guarantees an equal chance when a-b = a power of two, so you can split equal.
about 5 years ago
about 5 years ago
first flip chooses between {a} and {a+1}, be it x. second flip, between x and {a+2},etc. although this seems worse than your solution, since it’s O(b-a).
about 5 years ago
This doesn’t work also – think at the last number (b) – it will have a 50% chance to be chosen.
about 5 years ago
i got it. it’s O(b-a).
you flip the coin b-a times, getting a 0 or a 1 => a binary number with b-a digits. you turn it into base10, getting a number between 0 and 2^(b-a+1)-1, be it X.
P=X/(2^(b-a+1)) => P is between [0, 1), a float number.
we then divide [0,1) in b-a intervals, and where P falls, that’s our number. if it falls right on the border, the right interval is considered (that’s why the b has a “)”).
I might be thinking way too complicated stuff, but that’s all for now… if I find anything else, I’ll let you know
about 5 years ago
Sorry – this still doesn’t work
.
First of all – you could have chosen log (b-a) flips, this is enough for getting a random number > b-a.
Then – what you are saying maps a random number in the range 0 .. (2^n)-1 to a a .. b interval. This definitely doesn’t guarantee each a .. b number has the same chance to be chosen as some numbers may have more mappings than others.
As an example, try to match the 1..4 interval to 1..3.
1-1, 2-2, 3-2, 4-3
2 has a higher chance to be chosen.