#### Archived

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

# Self-balancing random number generation

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

## Recommended Posts

##### Share on other sites
Hello. I think this is the sort of thing you are looking for...

First, let me describe some terms:

SUM: This term is equal to the sum of all the previous return values from the function. "True" is counted as +1, "False" is counted as -1. Ex: If the fn had returned 10 trues and 8 falses, then SUM would be -2.

C: C is a constant which will need to be tweaked in order to get it to fit perfectly. C is the cap for the difference in the number of true and false responses. For example, if C = 5, then there can be no greater than 5 more true responses than false responses (and vise versa) before the fn forces a response of the opposite type.

The function below will return a weighted probability that can be used as as usual for determining a true or false. It needs to be given a probability (called x below) between 0 and 1 (inclusive). Here is the actual (simple) fn in psuedocode:

if (sum >=0)
p = x - (SUM / C)*x
else
p = x - (SUM / C)*(1-x)

I hope this helps. If it''s not what you are looking for, let me know and I''ll see what I can do.

Mike Melson

##### Share on other sites
What application do you have in mind for this?

If you really care about this kind of binary coin flipping example, you will be much better off by randomly sorting or permuting an equal number of true and false values.

##### Share on other sites
quote:
Original post by Kylotan

Imagine you are about to flip a coin 10 times. You expect 5 heads. So you flip it coin 9 times, and get 5 heads and 4 tails. Given a proper coin, the 10th flip has a 50% (p = 0.5) chance of being heads. This means that, once you''ve had 9 flips, you have a 50% chance of scoring 6 heads. However at the start, it was a 50% chance of scoring 5.

A small correction. Probability that in 10 flips you get 5 heads
is not 0.5 but smaller. To solve such problems (k succeses in N trials) you must use Bernoulli schema:
P(N,k)= N!/(k!*(N-k)!)*pk*(1-p)N-k
N - number of trials, k - number of succeses
p - probability of success, P(N,k) - probability that in
N trials you have k succeses.
So P(10,5) = (10!/5!*5!)*1/1024 = 252/1024
quote:

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.

The only meaning of "stochastic" I know about are stochastic processes. In such case stochastic means random as opposite to deterministic. I dont think they can help you,but I can be wrong.
quote:

(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.)

Maybe you can try something like this, each time the "bad" event
happens decrease its basic probability by some amount. After that
let it slowly grow, so after some time it reaches its base probability.

K.

##### Share on other sites
mmelson... that system seems close to what I am getting at. I was hoping there wouldn''t be a magic constant that I would have to pick on trial and error, though And I couldn''t just add +1 or -1 to ''sum'', rather it would be fractional parts of 1 indicating how far from the expected result the actual result was. If that makes sense. Ideally, I would have liked to eliminate any ''hard upper bound'' on the function, which is what is represented by the constant. I know that if I remove the hard upper bound, then there is always a chance that the correction method I use will not kick in, but I guess I would just prefer the corrective element itself to be based on a probability than a certainty.

Anonymous... I thought I made myself clear in the original post... it would be working on a percentage system, where I say "ok, this action has a 37% chance of success" and I want the system to return true about 37 times when called 100 times. The only difference between what I want, and a standard pseudo random number generator, is that when I''ve called it 99 times and had 36 true results, I want a better than average chance of getting a 37th true result on that 100th call. Whereas a normal PRNG is stateless (as far as probabilities are concerned... I know they have internal state for their own purposes) and would just have a 37% chance of returning true on that 100th call, regardless of what had gone before.

##### Share on other sites
quote:
Original post by Grudzio
A small correction. Probability that in 10 flips you get 5 heads
is not 0.5 but smaller. To solve such problems (k succeses in N trials) you must use Bernoulli schema:
P(N,k)= N!/(k!*(N-k)!)*pk*(1-p)N-k
N - number of trials, k - number of succeses
p - probability of success, P(N,k) - probability that in
N trials you have k succeses.
So P(10,5) = (10!/5!*5!)*1/1024 = 252/1024

Yes, of course. I only understood 1% of what you just said but I do know that what I said was wrong What I should have said was more like "However at the start, you had a higher chance of getting 5 heads than 6."

quote:
The only meaning of "stochastic" I know about are stochastic processes. In such case stochastic means random as opposite to deterministic. I dont think they can help you,but I can be wrong.

I read that stochastic processes were (sometimes) to do with some sort of probabilistic compensation for events that take a random amount of time and can only be measured once they complete. I figured this had a relevance to my system since you can''t know how many heads or tails you will have got until you flip it 9 times, however you know how many you want after 10 flips. But I know I''m largely stumbling in the dark here

##### Share on other sites
Well, how about replacing C with the term (NUM_TIMES + 1), where NUM_TIMES is (obviously) the total number of time that the function has been called. That way, there is always a positive probability that any given option will be selected (unless, of course, the given probabilites are 0 or 1, which still work correctly).

Also, I''m not sure why you would have to add a fractional value to SUM instead of +1 or -1. Maybe you could explain what sorts of return values the function would be spitting out. If they are just true/false values, then this system would work (I may just not be explaining what I mean well enough...).

Hope this helps.

Mike Melson

##### Share on other sites
The reason for the fractional values is because I don''t want it ''overreacting''.

Scenario: I call RandPercent(99) 5 times. It returns true 5 times. If C was 5, then the next call to RandPercent(99) will return false. This is obviously erroneous behaviour. Scoring 5 trues in a row for a 99% query is less ''unbalanced'' than 5 trues in a row for a 50% (coin flipping) query. Therefore it should be ''tipping the scales'' far less. With me?

##### Share on other sites
I''m not ready to stop pushing permutation yet.

You''re chance is 37%. You generate a list of true/false values, and you set 37% of them to ''true.'' Then you permute the list randomly. (Fairly easy and cheap to do) Each call to get random returns the next value in the queue. When you hit the end, you have a choice of looping back to start or re-permuting the list and starting over.

This also has the advantage of cutting down the number of potentially expensive calls to your system rand function, by essentially generating a look up table of random values.

Want more general percentages? Permute the numbers from 0 to 99, then treat chance < randvalue as a true. You''ll be true exactly chance out of 100 times.

##### Share on other sites
I''m not ready to stop pushing permutation yet.

You''re chance is 37%. You generate a list of true/false values, and you set 37% of them to ''true.'' Then you permute the list randomly. (Fairly easy and cheap to do) Each call to get random returns the next value in the queue. When you hit the end, you have a choice of looping back to start or re-permuting the list and starting over.

This also has the advantage of cutting down the number of potentially expensive calls to your system rand function, by essentially generating a look up table of random values.

Want more general percentages? Permute the numbers from 0 to 99, then treat chance < randvalue as a true. You''ll be true exactly chance out of 100 times.

1. 1
2. 2
3. 3
4. 4
frob
14
5. 5

• 16
• 13
• 20
• 12
• 19
• ### Forum Statistics

• Total Topics
632168
• Total Posts
3004543

×