Hi,
I would like to "bias" a pseudorandom binary sequence to contain a variable amount more 1's than 0's (or 0's than 1's) and still maintain the pseudorandom properties of the original sequence, is it ok to just switch every nth one to a zero, or does a more random type of biasing need to be done to maintain the original pseudorandom sequence properties?
cheers, Jamie
I 'thought' I tried what you're asking by taking 10,000 numbers that had a white noise uniform pdf [value somewhere between 0 and 1]. In other words,
10,000 values somewhere between 0 and 1, that are uniformly distributed. Usually called rand() function.THEN, subtrascted 0.5 from that, and then took the sign() of that stream to create another stream of 10,000 random 1's or 0's. To check the characteritics of the 10,000 0's and 1's there were Approximately the same quantity of 0's or 1's. To check for some qualifier of random sequence, I then took the differences between each binary number in sequence to produce a new stream of -1, 0, or 1's. Checking the histogram of that distribution there were indeed 1/4 of -1, 1/2 of zero change, and 1/4 of
+1. I know, I know, a LOT of sequences can produce that histogram, but at least there was osme measure of something in it. Then I started to change every nth value to '1' there were more 1's than 0's, but EXACTLY how does one measure the 'preservation' of a random sequnce after weighting the sequence towards more 1's than 0's?In other words, how does one measure the 'whatever you're trying to preserve' in such a stream?
PS: this test was done empirically using octave. You tell me what the stream is AND how to check for 'whatever you're trying to preserve' and I can write a script to do it. Should be able to answer your question. ...If that's any help.
It depends on what you are trying to do. Setting every N'th the way you want it is certainly the easiest and give the most control, but for some applications the regular bias might be unacceptable. For example it may add a fixed frequency component to an otherwise nosy irregular signal.
Assuming you have available a large amount of suitable random data you can try this:
work out the bias you want in terms of how many random sequences need to be AND together. 2 streams will give a bias of .25, three streams .125 etc. If you need something in between then like .375 get an AND-ed stream of .25 bias and an AND-ed stream of .125 and OR them together.
When you have the right amount of bias OR that stream with a new unbiased stream. The new stream will now have an excess of 1's equal to 1/2 of the bias on the other stream.
I've diligently spent the past 38 hours, 29 minutes and 52 seconds[1] creating 5 different random, bivalued generators. The first 10 outputs from each are listed below:
How does your answer change if I tell you the period of each of the generators is 2,456,342,765,788,543,985,453,774,302 cycles? Or, *10*??
Testing for randomness only makes sense in some particular context. What is the nature of your application? Are you modeling a "fair coin" to which you have introduced a known bias?
How is what you are calling "randomness" (pseudorandom) different from "unpredictability"?
The criteria you use for these "evaluations" *may* be dictated by, e.g., legislation (e.g., when designing gaming devices, there are typically rules/standards set forth governing their nature.
Google "diehard" to get yourself thinking about how *you* consider something "(pseudo)random".
Have fun! It's an interesting intellectual exercise!
(Now, time for my nap...)
[1] Give or take 38 hours, 29 minutes and 50 seconds...
If you have a function which returns pseudorandom values between 0 and 1 exclusive from a uniform distribution, and you want to return 1 with probability p and 0 with probability 1 - p it's pretty simple. In Python:
def gen(p): return 1 if random.random() < p else 0
Other distributions may be more challenging as others have mentioned
-- ----Android NewsGroup Reader---- http://usenet.sinaapp.com/
Hi,
That's a pretty good built in rand function, thanks. I might have to do the AND OR method David mentioned (I'm using C#)
cheers, Jamie
Oops, I just realized to create a biased sequence you just need to start with a pseudorandom number range ie 0 to 1000, and then if the output number is between 0 and 550 then set it to 0 and if above 550 set it to
1, and this will give a biased output binary pseudorandom sequence with the same pseudorandom properties of the input sequence I think.cheers, Jamie
That's a much better idea.
drop every nth zero, if you translate them you'll see no runs of n zeroes and that will bias the sequence.
-- umop apisdn
Of course not you would be creating a trivial defect in the sequence.
Simplest quick fix is generate a random number uniform on some range 0-N and alter the threshold for a one from being exactly N/2.
-- Regards, Martin Brown
This would seem to be the most entropy-efficient method.
Suppose you need a cryptographic TRNG, weighted for whatever purpose. This must come from diverse sources of entropy (random.org uses atmospheric noise; the Linux kernel uses device states), and that source limits your bitrate. (random() can hang, awaiting additional entropy.) Generating a number (like 550) takes a lot of entropy (i.e., about 10 bits worth!). All this just to produce one bit of output. What an embarassing waste! At least having the decency to factor it will help, but only in some cases (550/1000 = 55/100 = 11/20, needs slightly over 4 bits; but 557/1000 doesn't reduce).
I suspect there's an accumulative method that could be used for any rational P/Q < 1/2 (e.g. Bresenham's algorithm). Dropping every Nth zero and Mth one would indeed seem to be the trick, but N/M != P/Q, so you have to figure out how to get nice integers from the desired ratio.
Note: you won't eliminate runs of N or M zeroes or ones, because the chance of a subsequent 1/0 after the removed bit is still 50%, just as it always was.
I don't think that conditionally dropping bits is the best method (you'll get a notch in the autocorrelation at N and a peak at M), but it's a start.
Tim
-- Seven Transistor Labs Electrical Engineering Consultation Website: http://seventransistorlabs.com
As I said upthread, there's a difference between randomness and (lack of) predictability. The OP has to decide his ultimate goal.
Gaming devices must be "provably fair" (not as much so for grey area devices) -- so, there can't be any bias in the RNG (note that such bias could potentially work in favor of the House *or* Player, depending on the game). But, realistically, you aren't looking for *TRUE* randomness as much as "lack of predictability".
E.g., a slot machine typically has to come up with a new random number every 2-3 seconds (the minimum cycle time on a slot). As there are, conceivably, many possible outcomes -- all of which are theoretically equally probable (before adding house bias), that's about 16b.
And, of course, any entropy sources can't be (too) heavily influenced by the user (Player) as they *will* figure out how to use this information to cut the House margin!
[I've often toyed with building a really ornate/steam-punkish "coin flipper" under a glass bell jar that just sits there all day long generating a bit at a time...]Usually, you want a really wide generator for exactly that reason. E.g., just rolling a fair, six sided die requires at least three bits *if* you discard
2 of the 8 "unwanted" states. Consider picking one of 52 cards from a deck (then, one of the 51 remaining, etc.). [I've audited sources where there was obvious bias in the algorithms owing to the use of an insufficiently wide RNG]In practice, this means you end up with a PRNG instead of TRNG -- but, the "unpredictability" issue is your saving grace (over any "randomness" criteria)!
That's only the case for a TRNG. There can be short-term biases in PRNG's (e.g., betting "black" after a black win *can* be a strategy that marginally increases your return)
Bottom of
There's also a robotic dice machine that's web-linked; they discuss how it all works (dice flipper, machine vision and pattern counting, web integration).
Hence why houses prefer 4 deck+ Blackjack, etc. Card counting is a fun idea, but less likely to be beneficial under those conditions. Naturally they don't want anyone having just a little too much fun, only a nominal amount of it.
Tim
-- Seven Transistor Labs Electrical Engineering Consultation Website: http://seventransistorlabs.com
Ha! Amusing! I'm surprised he doesn't have a "gender detector", as well! (though I think they are no longer as effective given fashion changes)
I knocked up a "weekend version" many years ago with just a solenoid and some reflective sensors. While it's amusing to *watch*, it doesn't produce very good random numbers. And, coins wear out when you're jabbing them with a metal plunger, repeatedly!
[I'd originally thought something like the "popping" dice roller (was the centerpiece of some childhood game the name of which now escapes me) would work. But, I think a die tumbles a lot more actively than a coin "flips"]Most of the "live" games are reasonably fair. They follow the rules that one would *expect* (e.g., 52 cards per deck -- plus jokers -- lets you
*know* what the probability of a given hand are likely to be). Electronic machines are free to impose their *own* rules which may be contrary to what the sucker^H^H^H Player expects! (e.g., many "poker" games are actually *slots*, in some venues -- the probabilities that one would tend to associate with "playing cards" don't apply!)
Most (good) sources of cryptographic pseudo random data are OK in this application. They start with a pool of true random data (an entropy pool) gathered from sources such as you have said, and that is used to feed a CSPRNG. The output of the cryptographic pseudo random number generator provides the output and some of it is also feed into the entropy pool. This doesn't increase entropy, but it does allow the CSPRNG to degrade gracefully from true random data to practically random data with a predefined security level. Plus the entropy pool is topped up with the sources of true randomness periodically. Done properly this gives both forward and backward security.
For what that was, see
Matt Roberds
ElectronDepot website is not affiliated with any of the manufacturers or service providers discussed here. All logos and trade names are the property of their respective owners.