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

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

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