# Magical Loaded Dice and expected values

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?

-
Set the bias to $0$ on the faces $1,2,5,6$ and $1/2$ on the faces $3,4$. – Yuval Filmus Jun 24 '11 at 23:30
@Yuval: -_- Thanks, edited... – BlueRaja - Danny Pflughoeft Jun 24 '11 at 23:33
How is the extra condition enforced? Do you mean, for instance, that if the previous roll was a 1, the current roll will be 1 with probability $\frac{p_1}{p_1 + p_2}$ and a 2 with probability $\frac{p_2}{p_1 + p_2}$, where $p_1$ and $p_2$ are the initial probabilities of 1 and 2? – Brian M. Scott Jun 25 '11 at 0:16
In addition to Brian's comment: how does the condition you specify (between 1 and prev+1) interact with the calculation of E.V.? Given that the distribution of a roll would seem to depend on the values of previous rolls, it's not clear that a 'global' notion of E.V. makes any sense any more; you have a conditional expectation on the previous roll, and there are values for the previous roll (e.g., if a 1 was rolled) that make it impossible for the E.V. on the next roll to be 'right' (as the mean can't be greater than the highest achievable value, prev+1)... – Steven Stadnicki Jun 25 '11 at 0:39
@Steven: BlueRaja defined a Markov chain. The requirement is that the chain be ergodic, and the stationary probability correspond to a r.v. of expectation $3.5$. – Yuval Filmus Jun 25 '11 at 2:13

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

-