Timeline for Whitening a random bit sequence
Current License: CC BY-SA 2.5
4 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 25, 2010 at 23:14 | comment | added | BCS | the Von Neumann extractor is very inefficient for high biases. Also see my comment to qwerty1793. | |
| Jun 25, 2010 at 23:12 | comment | added | Joseph O'Rourke | @BCS: Perhaps then you want the simplest (and first?) randomness extractor, the Von Neumann extractor: "His extractor took successive pairs of consecutive bits (non-overlapping) from the input stream. If the two bits matched, no output was generated. If the bits differed, the value of the first bit was output. The Von Neumann extractor can be shown to produce a uniform output even if the distribution of input bits is not uniform so long as each bit has the same probability of being one and there is no correlation between successive bits." | |
| Jun 25, 2010 at 23:05 | comment | added | BCS | After reading about half the the first page, that seems like a solution to a much more general problem. See edit. | |
| Jun 25, 2010 at 22:46 | history | answered | Joseph O'Rourke | CC BY-SA 2.5 |