#### Archived

This topic is now archived and is closed to further replies.

# Self-balancing random number generation

This topic is 5993 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Just a little suggestion....say for instance you only store a certain number of past values. Say 50, for example. First you start with your basic algorithm for generating a random number, then store the result in a linked list, queue, whatever. Then build the first 50 numbers by taking the number of past values that are opposite to what you want (In your case this would involve numbers less than .5, greater then .5), and using that number as the probability of generating the value you need on this one. Makes Sense? Then, when you reach 51, 11, etc., you simply discard the first value and add the new value. A linked list would be great for this.

##### Share on other sites
Sorry if my wading into this thread so late causes a rehash of old stuff...

Kylotan: You have a problem in your requirements for the system that makes a solution not possible.

By biasing the coin flip (or roulette wheel for continuous variables) so that in the limit as the number of trials approaches a given number N, the apparent bias of the coin approaches the actual bias (i.e., k/n -> p(success,t=0); k= number of successes, n = number of trials held so far) means that you no longer have a random process of independant trials. You''re coin flips will be correlated and what you will be producing is the equivalent of a coloured noise process.

However, you state that you desire a system that does not maintain information about prior flips. I don''t see this as being possible. You will need to maintain some information regarding the sequence generated so far. In particular, the coloured noise will be a time varying function (time is the number of trials conducted so far).

quote:
Original post by Kylotan
I have seen the term ''stochastic'' used in some contexts similar to this, but have yet to find an explanation of the term that is both precise and yet not overly complex. Perhaps this is the solution to my problem, but I don''t know.

Stochastic is best defined as ''containing an element of unpredictability''. More formally, if a variable X can be explained as a (possibly non-linear) function of a set of other variables, Y, then X is a random (or stochastic) variable if there exists a residual variance in the values of X when Y is held constant.

quote:
Original post by Kylotan
(For those who are interested, basically I just want this so that I can have a random number system in a game that allows for freak events, but takes corrective action to reduce the chance of an unlucky streak damaging a player''s chances.)

You would be far better off just to stick with random numbers and maintain a moving window of behaviour that broke streaks of good luck or bad luck by inserting a failure or success respectively.

The easiest way to do this is to reject any coin flip if the sequence of previous flips (over a window of length k) are identical. Simply resample from the distribution (which, if it is binary, means return the desired result). In the limit as the number of trials is large, this insertion will not appreciably harm the statistics of your sequence.

Cheers,

Timkin

##### Share on other sites
quote:
Original post by Timkin
However, you state that you desire a system that does not maintain information about prior flips. I don''t see this as being possible. You will need to maintain some information regarding the sequence generated so far. In particular, the coloured noise will be a time varying function (time is the number of trials conducted so far).

The system will not be able to store the previous sequence in its entirety due to implementational limitations. (Finite RAM and all that.) But it could happily store the number of samples, plus the mean of the returned values. Or any other measure of central tendency, or any other value that needs recording. It just can''t record the whole sequence because that will grow infinitely, and is thus impractical.

quote:
You would be far better off just to stick with random numbers and maintain a moving window of behaviour that broke streaks of good luck or bad luck by inserting a failure or success respectively.

The easiest way to do this is to reject any coin flip if the sequence of previous flips (over a window of length k) are identical. Simply resample from the distribution (which, if it is binary, means return the desired result). In the limit as the number of trials is large, this insertion will not appreciably harm the statistics of your sequence.

This is all very well for coin flips. Coin flips are trivial to deal with. However, I am not using coin flips. How do I do something like this if I get 2 true results from 10 calls, when in fact I only expected 1 true result (ie. a 10% chance)?

##### Share on other sites
Kylotan, did you see my last post? I think that''s what you''re looking for...

~ Dragonus

##### Share on other sites
double post deleted; I am the Anonymous Poster signing ld

ld

##### Share on other sites
quote:
Original post by Dragonus
Kylotan, did you see my last post?

Well, I don''t quite see how to get around the ''max calls'' problem, for starters. But the other issue is that it assumes the same percentage being passed to it each time. I don''t want to limit the procedure to only working on a given probability: I just want it to know whether it''s been scoring true more than it ''should'' or false more than it ''should'', on input values which can vary.

##### Share on other sites
It''s early, I''m tired, so maybe this has already been suggested. Why not generate a number between 0 and 1. A value greater than the number of successes divided by the number of roles would be needed for a success. So if you had ten roles already and six successes you would only have a 40% chance of a success. With a bit of thought this could be expanded out to more than a true/false outcome, but as I said it is too early to think clearly.

##### Share on other sites
Sigh.

I don''t think that you have fixed your design requirements firmly enough in your own head. First you complain that a standard PRNG won''t get enough samples, then you state that storing values will ''grow to infinity.''

I think you need to figure out how many calls you really expect this system to get, and when resets will or will not be noticable by the user. Then you''ll really know if you can cap the number of calls or not... and make no mistake, you will either have to cap the number of calls, or stick with one percentage per instance of your generator object.

##### Share on other sites
Oops, I goofed a bit on the equation. Here's what it should be...

  original * (maxCalls / 100) - trueReturnstweaked = ----------------------------------------- maxCalls - totalCalls

That's done so that the numerator will be with the same order of magnitude (roughly) as the denominator. (Also assumes original is between 0 and 100. If original is between 0 and 1, i.e., a fraction, replace the 100 with 1.)

~*~*~*~

Actually, Kylotan, it doesn't assume that it will get the same probability every time -- I was just using the same probability case as an example:

If you assume maxCalls == 100, your first call to the function (let's say original == 90 the first time), trueReturns == totalCalls == 0, so you get 90%.

Assume you get a true next time you call it 50% being the original percent. trueReturns == totalCalls == 1, so the real probability is (50-1)/(100-1) = 49/99 = 49.5%.

Assume you then get a false and call it at 30%. TrueCalls == 1 and totalCalls == 2. So your chance now is (30-1)/(100-2) = 29.6%. A similar call to 70% would give (70-1)/(100-2) = 70.4%. It will keep the odds you want.

As far as "getting rid of" the maxCalls number, I still think setting it "high enough" would work. All you have to do is make sure you don't call it that many times. If you set it to exactly the number of calls you'll be making, this equation will be exact. However, if you increase the maxCalls number, it won't be perfectly exact, BUT the probabilities will follow the distribution you're looking for.

Given your explanation of the problem (when you specified a number of calls), this is exactly the equation you're looking for. But if you want to make any number of calls to the function, all you have to make sure is that maxCalls is significantly bigger than the actual number of times you intend on calling the function; if you set it "high enough", you'll never run into that problem.

~ Dragonus

Edited by - Dragonus on August 22, 2001 9:56:57 AM

##### Share on other sites
quote:
Original post by Anonymous Poster
Sigh.

I don't think that you have fixed your design requirements firmly enough in your own head. First you complain that a standard PRNG won't get enough samples, then you state that storing values will 'grow to infinity.'

Where did I say anything about a standard PRNG not getting enough samples? *looks very confused*

EDIT: Oh, I see: you misunderstood what I was referring to. Any random sampling is subject to higher rates of error given smaller samples. A normal PRNG is going to have almost zero error, eventually, but 'eventually' is too late. All I want is a system that can calculate the error (which is theoretically possible since we always know what the 'expected' outcome is, and just how likely it is), and take action to reduce that error by biasing subsequent calls.

quote:
I think you need to figure out how many calls you really expect this system to get.

As many as it needs. There is no fixed amount, nor can there be.

Edited by - Kylotan on August 22, 2001 12:02:04 PM

##### Share on other sites
quote:
Original post by Dragonus
But if you want to make any number of calls to the function, all you have to make sure is that maxCalls is significantly bigger than the actual number of times you intend on calling the function; if you set it "high enough", you''ll never run into that problem.

Ok, I''m with you, and this is certainly along the right lines, but: if you make ''maxCalls'' too high, then the balancing effects become minimal.

I feel sure there must be some way of doing this that doesn''t have some fixed bound, because given enough ''error-correction'', what has gone previously can be considered to have been adequately compensated for. Am I making sense?