For the first lecture of Michael Mitzenmacher's Algorithms and Data Structures class this semester, he gave a lecture on how to extract "fair" randomness from a biased coin. That is, given a coin which is possibly unfair, how can we use it to simulate a fair coin?
The canonical first solution is attributed to Von Neumann -- flip the coin twice. If the output is HT, call the result 0; if it's TH, call the result 1; if it's HH or TT, repeat. It turns out that this scheme can be extended, which isn't surprising since we just threw out quite a bit of information. One starts by saying that if the first four flips turn up HHTT or TTHH we call the result 0 or 1, respectively; this means that there's only a one-in-eight chance that we don't get a bit out of the first four flips. Not surprisingly, this can be iterated.
Furthermore, if we consider the problem of extracting a stream of bits 0 or 1 which are independent and identically distributed, with probability one-half of being 0 or 1, a more complex iteration scheme can actually do maximally well. That is, if the heads probability of the original coin is p, it's possible to get H(p) = -p log2 p - (1-p) log2 (1-p) bits per coin flip, which is the binary entropy of a single flip of the coin and thus the best one could hope to do.
Subscribe to:
Post Comments (Atom)
8 comments:
How does one decide something is not random?
I have a Dilbert cartoon taped to my office door, where someone points to a guy saying 'nine, nine, nine, .....' Dilbert asks 'Is that random?' and is answered 'That's the problem with randomness you never know.'
So do you apply these algorithms assuming the data isn't random? Is there a way to use this as a test for randomness? You got data and you want to know if someone has messed with it.
To me, the next obvious question is: Can you get a fair roll from a loaded die? How? Or a fair probability distribution from a pair of (possibly differently) loaded dice?
Clem,
Mitzenmacher actually brings that question up at the end of his notes.
The things one immediately thinks of don't work -- the answers for the "coin" version of this problem that I know of basically pair up sequences that have the same probability of occurring (which have to be permutations of each other, since we're assuming don't know how they die is loaded) and call one "0" and the other "1" -- for example HT and TH are paired, or HHTT and TTHH.
With a six-sided die the following scheme suggests itself: roll the die three times. If any two of the three rolls are the same, ignore. If all three are different, then look at the "pattern" formed by the results -- that it, label the smallest one 1, the middle one 2, and the largest one 3. There are six such patterns, and they're all equally likely; assign each of them to one of the numbers 1 through 6. But I don't see how to generalize this to the multi-level scheme that Mitzenmacher writes about for coins, and it also seems to depend too strongly on the fact that 6 = 3!. Ideally I'd want a scheme that works for arbitrary-sided dice.
'Can you get a fair roll from a loaded die?'
But how do you know the dice are or not loaded? How long a data stream do you need? I assume the length would be different for different problems.
I'm playing craps on Flatbush Ave. how long a data stream would I need to believe the dice are loaded; also can I use this to hide data? i want to send a message to Olga can I use this to hide the message in what appears to be random?
Hmm... It looks like it will take a lot of flips if your coin is really loaded.
There's a fairly simple scheme that gives you uniform, random samples from 0 to n-1, given a loaded die/coin/etc. (Well, it's simple if you don't handle the edge cases; I assume that n is not too big, and that the source of randomness is not too unfair.)
Start by taking 1000 samples from your possibly-biased distribution. We require that samples are independent, and that each sample has the same discrete probability distribution. We do not require that we know this probability distribution ahead of time (we do not even require that we know ahead of time how many events are possible; if you're flipping a coin, and writing down a sequence of H and T, and the coin lands on its edge, just write down an E and continue.)
Compute the number of permutations of this 1000-element multiset; call this number P. Consider some standard ordering of these permutations, and compute the index of our particular 1000-element sequence in this ordering; call this index k (using a 0-based index, so 0<=k<P).
Now, repeat these steps:
while k < n*floor(P/n):
output mod(k, n)
k = floor(k/n)
P = floor(P/n)
Once this loop has terminated, start over with another 1000 samples.
I believe that this does a very good job of extracting bits from the input samples; and if you replace 1000 by J, then as J goes to infinity the process approaches optimality. Of course, the approach from the notes is much nicer, in that you are likely to start getting bits immediately, instead of having to wait for 1000 samples.
[url=http://community.bsu.edu/members/buy+online+Viagra.aspx]how to get Viagra prescription[/url]
[url=http://eterporno.ru/web-sayty-znakomstv.php]web сайты знакомств[/url]
[url=http://eterporno.ru/loveplanet-ru-znakomstva.php]loveplanet ru знакомства[/url]
[url=http://pc.eterporno.ru/index.php]интимсити ру сайт[/url]
[url=http://pc.eterporno.ru/blyadi-piter-vhod.php]бляди питер вход[/url]
[url=http://pv.eterporno.ru/gei-prostitutki-ostavili-soobscheniy.php]геи проститутки оставили сообщений[/url]
[url=http://pv.eterporno.ru/dosug-almaty-transseksual.php]досуг алматы транссексуал[/url]
[url=http://px.eterporno.ru/dvorovaya-shluha.php]дворовая шлюха[/url]
[url=http://px.eterporno.ru/g-marks-znakomstva.php]г маркс знакомства[/url]
[url=http://pz.eterporno.ru/index.php]знакомства секс пары доска[/url]
[url=http://pz.eterporno.ru/hochu-seks-piter.php]хочу секс питер[/url]
Post a Comment