Ok, although I am ok at mathematics, I''m no expert, so excuse any apparent ignorance or misuse of terminology. 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. I am looking for a way to ''counterbalance'' this, so that by the time that 10th flip comes about, the system is biased so that it tends towards rectifying any imbalances in the probability sequence. In other words, the chance of flipping the coin and getting tails would be greater than 50%. Ideally, the chance in this case of getting tails on the final flip would be 100%. However, this requires that the system knows that we are working with a sample size of 10. This will not always be possible. Therefore any system that can guarantee a tails chance of greater than 50% will be better than nothing. And for every subsequent flip that results in heads, this chance should grow somewhat. Another constraint is that the system will be called many times. Therefore it''s not viable to store all the past scores. However, it would be viable to store the average of the past scores plus the number of scores in the sample that made up that average, which I guess should be just as useful in the circumstances. Finally, this random number generator wouldn''t just be generating true/false or heads/tails values based on a 50% probability. (I used the coin-flipping as a simple example.) It would be generating true/false values based on a supplied variable that represents a percentage, or other continuous value (between 0.0 and 0.1, perhaps). For example, via a function call such as "RandPercent(60)", which has a 60% chance of returning true, given no prior calls to the function. This makes a solution based on formulating a ratio from the nominal data (ie. count the heads, count the tails, and weight the new result based on the proportion) insufficient. However, since the random number generator knows what the ''threshold'' for each test is, it can see whether it returned the ''expected'' result or not, and can also see how likely/unlikely its result was. 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. (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.)

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

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.

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.

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.

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

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

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?

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.

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.