Basically, what you're asking for is a "semi-random" event generator that generates events with the following properties:
The average rate at which each event occurs is specified in advance.
The same event is less likely to occur twice in a row than it would be at random.
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:
Initially, let e1 = e2 = ... = en = 0.
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).
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 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).