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.

We're looking for long answers that provide some explanation and context. Don't just give a one-line answer; explain why your answer is right, ideally with citations. Answers that don't include explanations may be removed.

  • 4
    If you want a highly nuanced or sophisticated answer, you might have more luck asking at Mathematics.SE. The mathematicians there are comfortable answering complicated questions about probability. math.stackexchange.com – Kevin Feb 25 '15 at 23:05
  • 1
    PRNG – Frank Feb 26 '15 at 4:06
  • 6
    An alternative to the Mathematics site where you'd be more likely to understand the answers is Programmers.SE. Algorithm design is not particularly on-topic on Math and you'd probably need to come up with an initial design to get useful input. – Lilienthal Feb 26 '15 at 8:28
  • 1
    I agree with Kevin and Lilienthal that you might get a better answer there, but reading mklingen's answer I realized what is being described here can be modeled as a Markov chain and that might be a handy tool for game developers to know about. I'll try to write that up in more detail later. – nwellcome Feb 26 '15 at 15:05
  • 1
    As I've been running the numbers on some of the answers here, I'm finding there are a number of different constraints, and that a solution that solves all of them might me more complex than what you need. Some more specifics on your use case might help narrow-in on the best options. For instance, are the probabilities of your events fairly similar (eg. 5 diffetent outcomes with 20% chance each), or very different (eg. 10% miss 80% hit 10% critical)? Do you want to minimize runs (eg. 3 misses in a row) or clumps/waits (eg. 3 misses out of 8 tries, or 20 tries before I get a critical)? – DMGregory Feb 27 '15 at 14:13
up vote 17 down vote accepted

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 p1, p2, ..., pn be the relative likelihoods of the events 1 to n, and let s = p1 + p2 + ... + pn 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 e1 = e2 = ... = en = 0.

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

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

For example, given three events A, B and C, with pA = 5, pB = 4 and pC = 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 ei by pi in step 2, you could increment it by pi × 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 ei by pi + 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 ei equals pi.

  • 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 pi). 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 eis (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
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).

  • Very alaborate answer. Adding random factors to the dithering algorithm seems straight forward. :) – Sonaten Feb 26 '15 at 8:05
  • Decided to go with your answer. :) But I would recommend that you put the additions of the method overview at the top. What I am going to do, based on your answer is to try both the "Red" and "Purple" solution. – Sonaten Mar 5 '15 at 19:31

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.

  • 1
    lookup "shuffle bag" (on this site even) – jhocking Feb 25 '15 at 17:15
  • 3
    This is how many Tetris games avoid leaving the player starved for key pieces for too long. It's important to empty the bag/deck as Philipp suggests before inserting new cards if you want to control the occurrences over a set interval. By re-inserting cards as you go (or re-adjusting weights), you can distort the probability distribution in ways that are difficult to calculate, and easy to get wrong. – DMGregory Feb 25 '15 at 17:33
  • 2
    @DMGregory: Actually, it's perfectly fine to mix in new cards before the deck is emptied (and, in fact, I'd recommend doing this to make the outcomes more natural and harder to predict). The important thing is to make sure that the (average) fraction of new cards shuffled into the deck equals the desired fraction that you want to draw out of it. – Ilmari Karonen Feb 25 '15 at 18:46
  • 4
    Illmari Karonen: when you replace items, you can lose the benefits of the shuffle bag in terms of limiting runs of identical outcomes or long gaps between particular outcomes. If your replacement rate is equal to the target probability distribution, you're now provably in the same position as generating each outcome independently at random. If it isn't equal to the target probability distribution, then you can warp the effective probabilities in ways that are difficult to predict and balance accordingly - the asker describes struggling with exactly this issue. – DMGregory Feb 25 '15 at 20:33
  • 2
    Agreed with @DMGregory. By shuffling in new cards, you invalidate the very system itself. The card-dealing system is specifically and perfectly suited for the desired outcome. For instance, when you remove a queen (to use traditional cards for example) from the deck, the probability of drawing a queen decreases, and the probability of drawing a card other than a queen increases. It's a a self-adjusting system, if you will. – Volte Feb 27 '15 at 20:29

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!

  • 1
    The reweighting scheme you propose does not preserve the desired probabilities of each state. Doing an empirical test with these numbers, misses happen about 41% of the time and Criticals about 25%, way off of the input values. Transitioning to the remaining states proportional to their probabilities (eg. Miss has a 25% chance of going to Crit and a 75% chance of going to Hit) does slightly better, with a 44% miss rate and 17% crit, but it's still not reflective of the desired probabilities in the input. – DMGregory Feb 25 '15 at 17:30
  • I forgot bayes rule :( Will recalculate again later. It may not be possible to maintain the prior probability distribution because the transition model as it stands leaves out possible sequences like CCHM or CHHM or the very likely MMHM, etc. – mklingen Feb 25 '15 at 17:33
  • The "no repeats" constraint might tie your hands here, with regard to extreme high & low weights. If you want 1 in 10 attempts to be Critical, the only way this method can meet that is to alternate 5 Misses & 5 hits, which distorts the hit & miss probabilities toward their average. No sequence without consecutive misses can satisfy the requirements of the input here. – DMGregory Feb 25 '15 at 17:38
  • 4
    @mklingen, I agree with DMGregory, the "strictly no repeats" is not desirable here. Rather, they want the probability of long chains of the same outcome to be less likely than it would be with a uniform random probability. You could do this with a Markov Chain (which is directed) that looks like this. This uses multiple states to represent repeated events where the probabilities of transitioning from "Hit 1" to "Hit 2" and "Hit 2" to "Hit 3+" goes down and the probabilities of transitioning back to "Hit 1" and "Crit 1" go up. – nwellcome Feb 26 '15 at 14:53
  • @nwellcome that's a great idea. – mklingen Feb 26 '15 at 16:55

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!

  • 1
    This reweighting scheme tends to lead the events to be equiprobable. Resetting the weights periodically is really just a band-aid that limits how bad it gets, while ensuring that 1 in 10 rolls gets no benefit at all from the reweighting. Also, one algorithm note: you're wasting a lot of work by filling a table of 100 entries in order to do your random selection. Instead, you can generate a random roll and then iterate over your 4 outcomes, summing their probabilities as you go. As soon as the roll is less than the sum, you have your outcome. No table-filling required. – DMGregory Feb 27 '15 at 4:10

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

  • Testing this empirically, this still results in a distortion away from the input probabilities over many runs. If a_i/p_i = 0.5 for instance, (and using numbers from mklingen's answer) an input miss rate of 60% becomes an observed rate of 50.1%, and an input critical rate of 10% is observed as 13.8%. You can verify this by taking the resulting transition matrix to a high power. Choosing ratios of a_i:p_i closer to 1 results in less distortion, but also less effectiveness in reducing runs. – DMGregory Feb 26 '15 at 21:21
  • @DMGregory good point: you cannot simply take powers of the transition matrix. I'll expand on my answer later on that – Tobias Kienzler Feb 27 '15 at 4:30
  • @DMGregory I started describing the full process (variant b) ), but it gets quite tedious and I'm currently short on time :/ – Tobias Kienzler Feb 27 '15 at 19:05

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.

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.

  • Note that this only works if your +1s/-3s are applied relative to the original weights, rather than to the most recently used weights. (Continuously modifying the weights uniformly like this makes them drift toward being equiprobable). While this keeps the probability on-target over the long run, it does very little to reduce runs. Given that I've missed once, the chance that I'll miss twice more in a row is 22% with this scheme, vs 25% with independent draws. Increasing the weight shift for a bigger effect (say to +3/-9) results in biasing the long-run probability. – DMGregory Feb 27 '15 at 3:59
  • Actually the data presented above is applying the +1/-3 to the most recent weight each time a roll is processed. So if you miss once at the initial 50% weight, the next miss weight would be 47%, and if you miss again, the following weight would be 44%, and so on. It does reduce runs (separate metric was tracking runs, found as much as a 24% reduction in runs), but they are still inevitable as this scheme still has a strong chance of leaving each of the 4 weights with a non-zero probability (e.g. Four crits in a row would leave the crit weight with zero chance of occurring). – David C Ellis Feb 27 '15 at 15:46
  • If that was your intent, then your implementation has a bug. Look at the graph - The fumble weight only ever bounces between 7 and 11, with no values outside of that. I ran a simulation using the continuous modification that you describe, and the graphs are drastically different, with the probabilities of each state converging toward 25% each within the first hundred trials. – DMGregory Feb 27 '15 at 16:24
  • Dangit, indeed it was bugged as you pointed out. Well, strike this answer. – David C Ellis Feb 27 '15 at 18:04
  • @DavidCEllis are you saying your implementation was flawed, or the idea itself is? My back-of-a-napkin intuition came to roughly the model you describe (adjust a probability down when drawn, gradually restore all probabilities to their original values over time) and it still makes sense to me. – dimo414 Feb 28 '15 at 15:46

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.

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.
  • I think you may have misread the question: the OP is not asking how to generate weighted random outcomes, but how to adjust the weights to reduce the likelihood of the same outcome occurring several times in a row. – Ilmari Karonen Feb 25 '15 at 18:48
  • I see, I've changed some of my answer to explain how that would be possible using this system. – erikgaal Feb 25 '15 at 19:18

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.