autocorrelation and killing monster RPG game

I had a discussion with a friend about a gaming problem. In an online RPG game, when player kill monsters, there is a 1/2 chance for the monster to drop an item. The possibility of getting nothing for 5 continuous kills is 1/32, thus one out of 32 players will get nothing in 5 kills. Obviously, those players won't be happy. So the question is, how to lower the chance of getting nothing and at the same time not biased toward awarding player by increasing the probability of dropping an item.
The idea is to add conditional dependencies between continous kills. E.g. If last kill doesn't drop an item, this kill should have a larger chance of dropping and vice versa. In another word, the series should not be $i.i.d$, but be negatively autocorrelated. We can design the random sequence as a stationary process: $x_n = a_0 + a_1 x_{n-1}+\epsilon$, where $\epsilon$ is a uniform random variable of $[-0.5, 0.5]$ and $a_1$ is a negative number other than -1. The mean of the sequence is $E(x_n) = a_0/(1-a_1)$. Since I would like the mean to be 0.5, I can simply pick $a_0 =0.75, a_1=-0.5$. $a_1$ controls how strong the prior kill affect current kill. The more negative $a_1$, the more likely this kill have opposite result as previous kill. Here I choose $AR(1)$ process, higher order $AR$ processes are also possible.

In [1]:

import pandas as pd
import numpy as np
import matplotlib.pyplot as plt

In [2]:

nsamples = 5000
window_size = 5
x = np.random.rand(nsamples)
y = np.zeros_like(x)
ar_order = 1
y[:ar_order] = x[:ar_order]

for i in range(ar_order, len(x)):
    y[i] = 0.75 - 0.5*y[i-1] + (x[i] - 0.5)

def count_drops(x, window_size=window_size):
    return pd.DataFrame(pd.rolling_sum(x>0.5, window=window_size)[window_size-1:].astype(int), columns=['cnt']).groupby('cnt').apply(len)

In [3]:

count_drops(y)

Out[3]:

cnt
0      50
1     582
2    1856
3    1896
4     557
5      55
dtype: int64

In [4]:

count_drops(x)

Out[4]:

cnt
0     167
1     893
2    1505
3    1561
4     737
5     133
dtype: int64

From the example of 5000 simulations, if the series is uncorrelated, there are 133 times that 5 consecutive kills drop nothing. In the autocorrelated case, the number drops to 55. We can try stronger negative autocorrelation effect. E.g. $a_0=0.9, a_1=-0.8$

In [5]:

z = np.zeros_like(x)
z[:ar_order] = x[:ar_order]

for i in range(ar_order, len(x)):
    z[i] = 0.9 - 0.8*z[i-1] + (x[i] - 0.5)

In [6]:

count_drops(z)

Out[6]:

cnt
0      18
1     371
2    2157
3    2129
4     300
5      21
dtype: int64

In [7]:

np.mean(x)

Out[7]:

0.49617767242116295

In [8]:

np.mean(y)

Out[8]:

0.49742403582370553

In [9]:

np.mean(z)

Out[9]:

0.49780965153743334

In [ ]: