4
$\begingroup$

Let's say we have a magical biased die that allows us to set the probability of every side to whatever we want (nonzero and add up to 1, of course). And let's say this die enforces the condition that the value of every roll must be between 1 and previousRoll + 1.

What would we set the bias on the sides to be to keep the expected value (mean over a large number of rolls) at 3.5, the same as an unbiased non-magical die?

More interestingly, what if the die has an arbitrary number of sides? What if it's output is continuous?

  • 0
    @Blue: Feel free to ask for expanded versions of specific steps if this is useful to you.2011-07-20

1 Answers 1

3

Say the weights $(p_k)$ yield the asymptotic distribution $(q_k)$. The one-step Markov dynamics of the process means that, for every $k$ between $1$ and $N$, $ q_k=\sum_{i=1}^Nq_i\frac{p_k}{P_{i+1}}[i+1\ge k],\quad\text{where}\ P_k=\sum_{i=1}^kp_i, $ with the convention that $P_{N+1}=1$.

If a collection of weights $(p_k)$ yields the uniform distribution $q_k=1/N$ for every $k$ between $1$ and $N$, the asymptotic mean will be $\frac12(N+1)$, as required. But this happens if and only if, for every $k$, $ \frac1{p_k}=\sum_{i=1}^N\frac1{P_{i+1}}[i+1\ge k]. $ In particular, $ \frac1{p_1}=\sum_{i=1}^N\frac1{P_{i+1}}=\frac1{p_2}, $ hence $p_1=p_2=x$, say, and $P_1=x$, $P_2=2x$. Likewise, $ \frac1{p_3}=\sum_{i=2}^N\frac1{P_{i+1}}=\frac1{p_2}-\frac1{P_2}=\frac1{x}-\frac1{2x}, $ hence $p_3=2x$ and $P_3=4x$. From here, using the relations $ \frac1{p_k}=\frac1{p_{k-1}}-\frac1{P_{k-1}},\quad P_k=P_{k-1}+p_k, $ one proves recursively that $p_k=2^{k-2}x$ and $P_k=2^{k-1}x$ for every $k$ between $2$ and $N$. Since $P_N=1$, this yields $x=2^{1-N}$.

Finally, a suitable collection of weights $(p_k)$ is $ p_1=2^{1-N},\quad p_k=2^{k-1-N},\quad 2\le k\le N. $