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?

  • 3
    Set the bias to $0$ on the faces $1,2,5,6$ and $1/2$ on the faces $3,4$.2011-06-24
  • 0
    @Yuval: -_- Thanks, edited...2011-06-24
  • 2
    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?2011-06-25
  • 1
    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)...2011-06-25
  • 0
    @Brian: Yes that is what I mean. @Steven: I mean, if you were to roll the die a large number of times, the mean value would approach 3.5; obviously the expected value for any particular roll won't (necessarily) be 3.5, though.2011-06-25
  • 0
    is this based on a real-world problem?2011-06-25
  • 0
    @a little don: Somewhat. It's inspired by this [gamedev](http://gamedev.stackexchange.com/questions/14065) post; I was curious if there's a way to make the platform jump up by up to `playerJumpHeight` or down by *any* amount each frame, and still have an equal-distribution of platform heights. By "equal-distribution" I mean if you were to stop the game at any random point, there would be an equally-likely chance of the platform being at any height. I realize this is not quite the same question.2011-06-25
  • 2
    @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$.2011-06-25
  • 0
    @Blue: Anything unclear to you in my solution?2011-07-20
  • 0
    @Didier: Well, I am still trying to learn the math to understand the derivation; but, the solution appears to work correctly. Thanks!2011-07-20
  • 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. $$