How to adjust the distribution of values in a random data stream?

Posted by BCS on Stack Overflow See other posts from Stack Overflow or by BCS
Published on 2010-03-10T20:20:38Z Indexed on 2010/05/26 18:11 UTC
Read the original article Hit count: 172

Filed under:

random-number-generator

|

information-theory

Given a infinite stream of random 0's and 1's that is from a biased (e.g. 1's are more common than 0's by a know factor) but otherwise ideal random number generator, I want to convert it into a (shorter) infinite stream that is just as ideal but also unbiased.

Looking up the definition of entropy finds this graph showing how many bits of output I should, in theory, be able to get from each bit of input.

The question: Is there any practical way to actually implement a converter that is nearly ideally efficient?

© Stack Overflow or respective owner

Related posts about random-number-generator

C# Random Number Generator getting stuck in a cycle

as seen on Stack Overflow - Search for 'Stack Overflow'
Hi, I am using .NET to create an artificial life program and I am using C#'s pseudo random class defined in a Singleton. The idea is that if I use the same random number generator throughout the application, I could merely save the seed and then reload from the seed to recompute a certain interesting… >>> More
Code Golf: MSM Random Number Generator

as seen on Stack Overflow - Search for 'Stack Overflow'
The challenge The shortest code by character count that will generate (pseudo)random numbers using the Middle-Square Method. The Middle-Square Method of (pseudo)random number generation was first suggested by John Von Neumann in 1946 and is defined as follows: Rn+1 = mid((Rn)2, m) For example: … >>> More
Get special numbers from a random number generator

as seen on Stack Overflow - Search for 'Stack Overflow'
I have a random number generator: int32_t ksp_random_table[GENERATOR_DEG] = { -1726662223, 379960547, 1735697613, 1040273694, 1313901226, 1627687941, -179304937, -2073333483, 1780058412, -1989503057, -615974602, 344556628, 939512070, -1249116260, 1507946756, -812545463, 154635395,… >>> More
Biased Random Number Generator

as seen on Stack Overflow - Search for 'Stack Overflow'
I am looking for a random number generator that can be biased. For instance, say I want a random number between 1-5, with the probability being: 1: Comes up 20% of the time 2: Comes up 10% of the time 3: Comes up 40% of the time 4: Comes up 25% of the time 5: Comes up 5% of the time Is there anything… >>> More
Random number Generator in C#

as seen on Stack Overflow - Search for 'Stack Overflow'
Why do i need to create an instance of Random class, if i want to create a random number between 1 and 100 ....like Random rand = new Random(); rand.Next(1,100); Is there any static function of Random class to do the same? like... Random.Next(1,100); I don't want to create an instance unnecessaril… >>> More

Related posts about information-theory

Are there any formalized/mathematical theories of software testing?

as seen on Programmers - Search for 'Programmers'
Googling "software testing theory" only seems to give theories in the soft sense of the word; I have not been able to find anything that would classify as a theory in the mathematical, information theoretical or some other scientific field's sense. What I'm looking for is something that formalizes… >>> More
Minimizing data sent over a webservice call on expensive connection

as seen on Programmers - Search for 'Programmers'
I am working on a system that has many remote laptops all connected to the internet through cellular data connections. The application will synchronize periodically to a central database. The problem is, due to factors outside our control, the cost to move data across the cellular networks are… >>> More
Is information a subset of data?

as seen on Stack Overflow - Search for 'Stack Overflow'
I apologize as I don't know whether this is more of a math question that belongs on mathoverflow or if it's a computer science question that belongs here. That said, I believe I understand the fundamental difference between data, information, and knowledge. My understanding is that information… >>> More
How do I compute the approximate entropy of a bit string?

as seen on Stack Overflow - Search for 'Stack Overflow'
Is there a standard way to do this? Googling -- "approximate entropy" bits -- uncovers multiple academic papers but I'd like to just find a chunk of pseudocode defining the approximate entropy for a given bit string of arbitrary length. (In case this is easier said than done and it depends on the… >>> More
Can information encoded with a one time pad be distinguished from random noise?

as seen on Stack Overflow - Search for 'Stack Overflow'
I understand that the cyphertext from a properly used one time pad cypher reveals absolutely no data about the encrypted message. Does this mean that there is no way to distinguish a message encrypted with a one time pad from completely random noise? Or is there some theoretical way to determine… >>> More