How can I make a "random" generator that is biased by prior events?

Question

I am looking to implement a chance based system which is biased by prior event.

Background: Some years back, I remember an update for World of Warcraft announcing that they implemented a new chance calculator that would counteract spiky chains of events. (e.g. making critical strikes or dodging several times in a row). The idea was that in the event that you would dodge a hit, the chance that you would dodge the next hit would be diminished, but it would work both ways. Not dodging a hit would equally increase the chance of dodging the next hit. The major trick here, was that over several trials the dodge chance would still correspond to the percentage given to the player in his or hers stat-sheet.

This kind of system very much intrigued me at the time, and now I am in the situation of needing such a solution.

Here are my troubles:

• I am guessing that I would be able to find online resources on implementing such a system, but I may just be lacking the relevant buzz words for finding it.
• Also I need this approach to fit a system that is not binomial (i.e. two outcomes), but instead contains 4 mutually exclusive events.

My current approach is similar to that of a raffle ticket system. When an event occurs I change the weights in favor of all other events. This could work if the four event were meant to be equally likely, but in my case, on needs to be much more prevalent. But as the prevalent event happens more often, it shifts the weights of the other a lot higher than intended and I cannot seem to find the numbers for the weight shifts that are needed to keep the average ticket count around the initial values that the event were given.

A few direction pointers or a clear cut example would be much appreciated.

Answer 1

Basically, what you're asking for is a "semi-random" event generator that generates events with the following properties:

1. The average rate at which each event occurs is specified in advance.

2. The same event is less likely to occur twice in a row than it would be at random.

3. The events are not fully predictable.

One way to do that is to first implement a non-random event generator that satisfies goals 1 and 2, and then add some randomness to satisfy goal 3.

---

For the non-random event generator, we can use a simple dithering algorithm. Specifically, let p₁, p₂, ..., p_n be the relative likelihoods of the events 1 to n, and let s = p₁ + p₂ + ... + p_n be the sum of the weights. We can then generate a non-random maximally equidistributed sequence of events using the following algorithm:

1. Initially, let e₁ = e₂ = ... = e_n = 0.

2. To generate an event, increment each e_i by p_i, and output the event k for which e_k is largest (breaking ties any way you want).

3. Decrement e_k by s, and repeat from step 2.

For example, given three events A, B and C, with p_A = 5, p_B = 4 and p_C = 1, this algorithm generates something like the following sequence of outputs:

A B A B C A B A B A A B A B C A B A B A A B A B C A B A B A

Notice how this sequence of 30 events contains exactly 15 As, 12 Bs and 3 Cs. It's not quite optimally distributes — there are a few occurrences of two As in a row, which could've been avoided — but it gets close.

---

Now, to add randomness to this sequence, you have several (not necessarily mutually exclusive) options:

• You can follow Philipp's advice, and maintain a "deck" of N upcoming events, for some appropriately sized number N. Every time you need to generate an event, you pick a random event from the deck, and then replace it with the next event output by the dithering algorithm above.

  Applying this to the example above, with N = 3, produces e.g.:

  A B A B C A B B A B A B C A A A A B B A B A C A B A B A B A
  

  whereas N = 10 yields the more random-looking:

  A A B A C A A B B B A A A A A A C B A B A A B A C A C B B B
  

  Note how the common events A and B end up with a lot more runs due to the shuffling, whereas the rare C events are still fairly well spaced out.

• You can inject some randomness directly into the dithering algorithm. For example, instead of incrementing e_i by p_i in step 2, you could increment it by p_i × random(0, 2), where random(a, b) is a uniformly distributed random number between a and b; this would yield output like the following:

  A B B C A B A A B A A B A B A A B A A A B C A B A B A C A B
  

  or you could increment e_i by p_i + random(−c, c), which would produce (for c = 0.1 × s):

  B A A B C A B A B A B A B A C A B A B A B A A B C A B A B A
  

  or, for c = 0.5 × s:

  B A B A B A C A B A B A A C B C A A B C B A B B A B A B C A
  

  Note how the additive scheme has a much stronger randomizing effect for the rare events C than for the common events A and B, as compared to the multiplicative one; this might or might not be desirable. Of course, you could also use some combination of these schemes, or any other adjustment to the increments, as long as it preserves the property that the average increment of e_i equals p_i.

• Alternatively, you could perturb the output of the dithering algorithm by sometimes replacing the chosen event k with a random one (chosen according to the raw weights p_i). As long as you also use the same k in step 3 as you output in step 2, the dithering process will still tend to even out random fluctuations.

  For example, here's some example output, with a 10% chance of each event being chosen randomly:

  B A C A B A B A C B A A B B A B A B A B C B A B A B C A B A
  

  and here's an example with a 50% chance of each output being random:

  C B A B A C A B B B A A B A A A A A B B A C C A B B A B B C
  

  You could also consider feeding a mix of purely random and dithered events into a deck / mixing pool, as described above, or perhaps randomizing the dithering algorithm by choosing k randomly, as weighed by the e_is (treating negative weights as zero).

Ps. Here are some completely random event sequences, with the same average rates, for comparison:

A C A A C A B B A A A A B B C B A B B A B A B A A A A A A A
B C B A B C B A A B C A B A B C B A B A A A A B B B B B B B
C A A B A A B B C B B B A B A B A A B A A B A B A C A A B A

---

Tangent: Since there has been some debate in the comments about whether it's necessary, for deck-based solutions, to allow the deck to empty before it's refilled, I decided to make a graphical comparison of several deck-filling strategies:

^{Plot of several strategies for generating semi-random coin flips (with 50:50 ratio of heads to tails on average). Horizontal axis is number of flips, vertical axis is cumulative distance from the expected ratio, measured as (heads − tails) / 2 = heads − flips / 2.}

The red and green lines on the plot show two non-deck-based algorithms for comparison:

• Red line, deterministic dithering: even-numbered outcomes are always heads, odd-numbered outcomes are always tails.
• Green line, independent random flips: each outcome is chosen independently at random, with a 50% chance of heads and a 50% chance of tails.

The other three lines (blue, purple and cyan) show the results of three deck-based strategies, each implemented using a deck of 40 cards, which is initially filled with 20 "heads" cards and 20 "tails" cards:

• Blue line, fill when empty: Cards are drawn at random until the deck is empty, then the deck is refilled with 20 "heads" cards and 20 "tails" cards.
• Purple line, fill when half empty: Cards are drawn at random until the deck has 20 cards left; then the deck is topped up with 10 "heads" cards and 10 "tails" cards.
• Cyan line, fill continuously: Cards are drawn at random; even-numbered draws are immediately replaced with a "heads" card, and odd-numbered draws with a "tails" card.

Of course, the plot above is just a single realization of a random process, but it's reasonably representative. In particular, you can see that all the deck-based processes have limited bias, and stay fairly close to the red (deterministic) line, whereas the purely random green line eventually wanders off.

(In fact, the deviation of the blue, purple and cyan lines away from zero is strictly bounded by the deck size: the blue line can never drift more than 10 steps away from zero, the purple line can only get 15 steps away from zero, and the cyan line can drift at most 20 steps away from zero. Of course, in practice, any of the lines actually reaching its limit is extremely unlikely, since there's a strong tendency for them to return closer to zero if they wander too far off.)

At a glance, there's no obvious difference between the different deck-based strategies (although, on average, the blue line stays somewhat closer to the red line, and the cyan line stays somewhat further away), but a closer inspection of the blue line does reveal a distinct deterministic pattern: every 40 draws (marked by the dotted gray vertical lines), the blue line exactly meets the red line at zero. The purple and cyan lines are not so strictly constrained, and can stay away from zero at any point.

For all the deck-based strategies, the important feature that keeps their variation bounded is the fact that, while the cards are drawn from the deck randomly, the deck is refilled deterministically. If the cards used to refill the deck were themselves chosen randomly, all of the deck-based strategies would become indistinguishable from pure random choice (green line).

Answer 2

Don't roll dice, deal cards.

Take all possible results of your RNG, put them in a list, shuffle it randomly, and return the results in the randomized order. When you are at the end of the list, repeat.

The results will still be uniformly distributed, but individual results won't repeat unless the last of the list also happens to be the first of the next one.

When this is a bit too predictable for your taste, you could use a list which is n times the number of possible results and put each possible result into it n times before shuffling. Or you could reshuffle the list before it is iterated completely.

Answer 3

You could try a Markov Random Graph. Consider each event that can occur to be a node in a graph. From each event, make a link to each other event that could possibly come after it. Each of these links is weighted by something called the transition probability. Then, you perform a random walk of the graph according to the transition model.

For instance, you can have a graph that represents the outcome of an attack (critical hit, dodge, etc.). Initialize the starting node to one picked at random given the player's stats (just "roll the dice"). Then, on the next attack, decide what happens next given the transition model.

Care needs to be taken to decide how to weight the transitions. For one thing, all the transitions coming out of a node need to add up to a probability of 1. One simple thing you could do is make a transition from every node to every other node, with weights equivalent to the probability that those events happen a priori, given that the current event cannot occur again.

For instance, if you have three events:

  Critical, P = 0.1
  Hit,      P = 0.3
  Miss,     P = 0.6

You can set up the transition model such that a critical hit does not occur again simply by redistributing its probability mass to the other events uniformly:

  Critical -> Critical,   P = 0.0
  Critical -> Hit,        P = 0.35
  Critical -> Miss,       P = 0.65

EDIT: As the comments say below, this model is not complicated enough to get the desired behavior. Instead, you may have to add multiple additional states!

Answer 4

Here's an implementation I created in C# which will:

• Activate events based on probabilities
• Adjust those probabilities to decrease chances of recurring events
• Not stray too far from original probabilities

I've added a few comments so that you can see what I'm doing.

    int percentageEvent1 = 15; //These are the starter values. So given a scenario, the
    int percentageEvent2 = 40; //player would have around a 15 percent chance of event
    int percentageEvent3 = 10; //one occuring, a 40 percent chance of event two occuring
    int percentageEvent4 = 35; //10 percent for event three, and 35 percent for event four.

    private void ResetValues()
    {
        percentageEvent1 = 15;
        percentageEvent2 = 40;
        percentageEvent3 = 10;
        percentageEvent4 = 35;
    }

    int resetCount = 0; //Reset the probabilities every so often so that they don't stray too far.

    int variability = 1; //This influences how much the chance of an event will increase or decrease
                           //based off of past events.

    Random RandomNumberGenerator = new Random();

    private void Activate() //When this is called, an "Event" will be activated based off of current probability.
    {
        int[] percent = new int[100];
        for (int i = 0; i < 100; i++) //Generate an array of 100 items, and select a random event from it.
        {
            if (i < percentageEvent1)
            {
                percent[i] = 1; //Event 1
            }
            else if (i < percentageEvent1 + percentageEvent2)
            {
                percent[i] = 2; //Event 2
            }
            else if (i < percentageEvent1 + percentageEvent2 + percentageEvent3)
            {
                percent[i] = 3; //Event 3
            }
            else
            {
                percent[i] = 4; //Event 4
            }
        }
        int SelectEvent = percent[RandomNumberGenerator.Next(0, 100)]; //Select a random event based on current probability.

        if (SelectEvent == 1)
        {
            if (!(percentageEvent1 - (3 * variability) < 1)) //Make sure that no matter what, probability for a certain event
            {                                                //does not go below one percent.
                percentageEvent1 -= 3 * variability;
                percentageEvent2 += variability;
                percentageEvent3 += variability;
                percentageEvent4 += variability;
            }
        }
        else if (SelectEvent == 2)
        {
            if (!(percentageEvent2 - (3 * variability) < 1))
            {
                percentageEvent2 -= 3 * variability;
                percentageEvent1 += variability;
                percentageEvent3 += variability;
                percentageEvent4 += variability;
            }
        }
        else if (SelectEvent == 3)
        {
            if (!(percentageEvent3 - (3 * variability) < 1))
            {
                percentageEvent3 -= 3 * variability;
                percentageEvent1 += variability;
                percentageEvent2 += variability;
                percentageEvent4 += variability;
            }
        }
        else
        {
            if (!(percentageEvent4 - (3 * variability) < 1))
            {
                percentageEvent4 -= 3 * variability;
                percentageEvent1 += variability;
                percentageEvent2 += variability;
                percentageEvent3 += variability;
            }
        }

        resetCount++;
        if (resetCount == 10)
        {
            resetCount = 0;
            ResetValues();
        }

        RunEvent(SelectEvent); //Run the event that was selected.
    }

Hope this helps, please do suggest improvements to this code in the comments, thanks!

Answer 5

Let me generalize mklingen's answer a bit. Basically, you want to implement the Gambler's Fallacy, though I'll provide a more general method here:

Say there are n possible events with probabilities p_1, p_2, ..., p_n. When event i happened, its probability shall rescale with a factor 0≤a_i≤1/p_i (the latter is important, otherwise you end up with a probability greater than one and the other events must have negative probabilities, which basically mean "anti"-events. Or something), though typically a_i<1. You could for example choose a_i=p_i, which means the probability of an event happening a second time is the original probability the event happening precisely two times in a row, e.g. a second coin toss would have a probability of 1/4 instead of 1/2. On the other hand, you can also have some a_i>1, which would mean triggering a "stroke of luck/misfortune".

All the other events shall remain equally probable relative to one another, i.e. they all have to be rescaled by the same factor b_i such that the sum of all probabilities equals one, i.e.

1 = a_i*p_i + b_i*(1-p_i)  # Σ_{j≠i) p_j  = 1 - p_i
⇒ b_i = (1 - a_i*p_i) / (1 - p_i).   (1)

---

So far, so simple. But now let's add another requirement: Considering all possible sequences of two events, the single-event probabilities extracted therefrom shall be the original probabilities.

Let

        / p_i * b_i * p_j  (j≠i)
p_ij = <
        \ a_i * (p_i)²     (j=i)

denote the probability of event j happening after event i and note that p_ij≠p_ji unless b_i=b_j (2) (which by (1) implies a_j = 1 - a_i*p_i + (1-a_i)*p_i/p_j). This is also what Bayes' theorem requires and this also implies

Σ_j p_ij = p_i * b_i * (1 - p_i) + a_i * (p_i)²
         = b_i * p_i + (a_i - b_i) * (p_i)²
         = p_i  # using (1)

just as desired. Just note how this means one a_i fixes all the other ones.

---

Now let's see what happens when we apply this procedure multiple times, i.e. for sequences of three and more events. There are basically two options for the choice of the third event's rigged probabilities:

a) Forget about the first event and rig as if only the second one occurred, i.e.

         / p_ij * a_j * p_j  (j=k)
p_ijk = <
         \ p_ij * b_j * p_l  (j≠k)

Note that this usually violates Bayes, since e.g. p_jik≠p_ikj in most cases.

b) Use use the probabilities p_ij (for fixed i) as new probabilities pi_j from which you obtain the new probabilities pi_jk for event k to happen next. Whether you modify the ai_j or not is up to you, but be aware that the new bi_j are definitely different due to the modified pi_j. Then again, the choice of ai_j is probably restricted by requiring all permutations of ijk occurring with the same probability. Let's see...

         / p_ij * bi_j * pi_k  (j≠k)
p_ijk = <
         \ (p_ij)² * ai_j      (j=k)

         / b_i * bi_j * p_i * p_j * pi_k  (i≠j≠k≠i)
         | b_i * ai_j * p_i * (p_j)²      (i≠j=k)
      = <  a_i * (p_i)² * bi_i * pi_k     (i=j≠k)
         | b_i * p_i * bi_j * p_k * pi_i  (i=k≠j)
         \ a_i * ai_i * (p_i)² * pi_i     (i=k=j)

and cyclic permutations thereof, which must be equal for the respective cases.

I'm afraid my continuation on this will have to wait a while...

Answer 6

I think the best option is to use random-weighted item selection. There's an implementation for C# here, but they can be easily found or made for other languages as well.

The idea would be to reduce an option's weight every time it's picked, and increase it every time it's not picked.

For example, if you decrease the weight of the picked-option by NumOptions-1 and increase the weight of every other option by 1 (being careful to remove items with weight < 0 and readd them when they rise above 0), every option will be picked approximately the same number of times over a long period, but recently-picked options will be much less likely to be picked.

---

The problem with using a random ordering, as suggested by many other answers, is that after every option but one has been picked, you can predict with 100% certainty what option will be picked next. That's not very random.

Answer 7

My answer is incorrect, my test was flawed.

I'm leaving this answer here for the discussion and comments that point out the flaws in this design, but the actual test was incorrect.

What you're looking for is a weighted weight: the weights for your four possible outcomes need to be further adjusted (weighted) by previous outcomes, while still remaining the proper weights overall.

The easiest way to accomplish this is to alter all of the weights for each roll by decreasing the weight for the specific value rolled and increasing the other weights.

As an example, lets say you have 4 weights: Fumble, Miss, Hit, and Crit. Lets also say your desired overall weights for them are Fumble = 10%, Miss = 50%, Hit = 30%, and Crit = 10%.

If you use a random number generator (RNG) to produce values between 1 and 100, and then compare that value to where it falls within this range (1-10 Fumble, 11-60 miss, 61-90 hit, 91-100 crit), you're generating an individual roll.

If, when you make that roll, you then immediately adjust those ranges based on the value rolled, you'll be weighting future rolls, but you also need to reduce the rolled weight by the same total amount that you increase the other weights by. So in our example above, you would reduce the rolled weight by 3 and increase the other weights by 1 each.

If you do this for each roll, you will still have the chance of streaks, but they will be greatly reduced, because for each roll you are increasing the chance that future rolls will be anything other than what the current roll is. You can increase this effect, and thereby further reduce the chance of streaks, by increasing/decreasing the weights by a greater factor (e.g. reduce current by 6 and increase others by 2).

I ran a quick app to validate this approach, and after 32000 iterations with those weights, it produces the following graphs. The upper graph shows the 4 weights immediate values at each roll, and the lower graph shows the sum count of each type of result rolled up to that point.

As you can see, the weights fluctuate slightly around their desired values, but the overall weights stay within the desired ranges, and after the initial variety of the starting numbers settles out, the results fit our desired percentages almost perfectly.

Note that this example was produced using the .NET System.Random class, which is not really one of the better RNGs out there, so you probably can get more accurate results by using a better RNG. Also note that 32000 was the maximum results I could graph with this tool, but my test tool was able to generate over 500 million results with the same overall patterns.

Answer 8

You could do what is essentially a filter. Keep track of the past n events. The probability is the some of some filter applied to those events. The 0th filter is the base probability, if 0 then you dodged, if 1 you failed. Let's say the base was 25%, and the filter decreases by half each iteration. Your filter would then be:

[.25 .125 .0625 .03125] 

Feel free to continue if you wish. The overall probability of this scheme is slightly higher than the base probability of .25. In fact, the probability, given the same scheme, is (I'm calling x the real probability, p is the probability input):

x=p+(1-x)*(p/2+p/4+p/8)

Solving for x, one finds the answer is p(1+1/2+1/4+1/8)/(1+p(1/2+1/4+1/8), or for our given case, x=0.38461538461. But what you really want is to find p, given x. That turns out to be a more difficult problem. If you assumed an infinite filter, the problem becomes x+x*p=2*p, or p=x/(2-x). So increasing your filter, you could then solve for a number p which will on average give you the same results, but at a rate dependent on how much success has recently happened.

Basically, you use the previous values to determine what the acceptance threshold is this round, and take a random value. Then produce the next random value given the filter.

Answer 9

Just like you proposed yourself, one of the approaches to this is to implement a weighted random. The idea is to make a random number (or outcome) generator where weights and outcomes can be modified.

Here is an implementation of this in Java.

import java.util.Map;
import java.util.Random;

/**
 * A psuedorandom weighted outcome generator
 * @param <E> object type to return
 */
public class WeightedRandom<E> {

    private Random random;
    private Map<E, Double> weights;

    public WeightedRandom(Map<E, Double> weights) {
        this.random = new Random();
        this.weights = weights;
    }

    /**
     * Returns a random outcome based on the weight of the outcomes
     * @return
     */
    public E nextOutcome() {
        double totalweight = 0;

        // determine the total weigth
        for (double w : weights.values()) totalweight += w;

        // determine a value between 0.0 and the total weight
        double remaining = random.nextDouble() * totalweight;

        for (E entry : weights.keySet()) {
            // subtract the weight of this entry
            remaining -= weights.get(entry);

            // if the remaining is smaller than 0, return this entry
            if (remaining <= 0) return entry;
        }

        return null;
    }

    /**
     * Returns the weight of an outcome
     * @param outcome the outcome to query
     * @return the weight of the outcome, if it exists
     */
    public double getWeight(E outcome) {
        return weights.get(outcome);
    }

    /**
     * Sets the weight of an outcome
     * @param outcome the outcome to change
     * @param weight the new weigth
     */
    public void setWeight(E outcome, double weight) {
        weights.put(outcome, weight);
    }
}

EDIT In the case where you want to adjust the weights automatically, for example increase the chance of A when the result was B. You can either,

1. Change the behaviour of the nextOutcome() method, so it modifies the weight according to the result
2. Use setWeight() to modify the weight of according to the result.