3
$\begingroup$

Here's a restatement of a programming problem I found on the Peking Online Judge website.

Your friend paints each side of each of 4 dice red or blue, independently, with equal probability. They roll the dice twice and reveal the number $k_1$ of dice with red faces showing after the first roll, and the number $k_2$ after the second roll. What is the expected number of dice that will have red faces up after the third roll?

I was able to solve this using Bayes' rule and total probability, expanding out and summing over all of the possible ways to paint the faces red. This was a little messy (but not too bad).

I found some solutions online (in Chinese, but Google Translate works well) that seem much simpler, but I wasn't able to follow the justification provided.

Alternate solution 1, which is the one implemented in the code snippet in the linked blog post, considers the conditional probability of a single die rolling red, given that die's initial two rolls, and somehow uses this to construct the overall expectation. I was able to understand how to compute the conditional probability of a single die rolling red, given its first two rolls, but not how to apply this in a straightforward way to solve the overall four-dice problem.

Alternate solution 2 directly computes the expectation as $(k_1 + k_2 + 10) / 7$. I wasn't able to understand how this was derived.

Question: How can one take advantage of symmetry or other characteristics of the problem to solve it in a way simpler than my initial approach? (In particular, where does the very simple formula in alternate solution 2 come from?)

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

For a single die rolled twice,

  • if you get $2$ red, the conditional probability the next is red is some number $p$

  • if you get $1$ red, the conditional probability the next is red is $\frac12$ by symmetry

  • if you get $0$ red, the conditional probability the next is red is $1-p$ by symmetry

so you could say the conditional probability the next is red is $(1-p)$ plus $(p-\frac12)$ times the number of reds seen on the first two rolls of the first die. Since you either get $0$ or $1$ red, this is also the conditional expectation of the number of reds seen on the third roll of the first die.

For four dice, you simply add these up across the four dice, using linearity of expectation, so the total conditional expectation of the number of reds seen on the third roll of all four dice is $4(1-p)+(p-\frac12)(k_1+k_2)$

The only difficult calculation you have to do is work out $p$, and this turns out to be $\frac9{14}$, so substituting this means the conditional expectation is $\frac{10}7+\frac17(k_1+k_2)$

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks! One quick question: we're conditioning the expectation for a single die on having seen zero, one, or two ones out of the prior two rolls. But when we're looking at all the dice together, it seems like we can't define the events we're conditioning on in the exact same manner. Is there essentially an implicit step that says something to the effect of: "No matter how we apportion the $k_1+k_2$ red faces rolled among the dice, the result is the same"? $\endgroup$
    – Urbana
    Commented Aug 12, 2021 at 6:31
  • $\begingroup$ @Urbana If there were $r_1$ red rolls on the first die the expectation for the third roll is $(1-p)+(p-\frac12)r_1$. Similarly for the other dice. So the total expectation is $(1-p)+(p-\frac12)r_1 +(1-p)+(p-\frac12)r_2+(1-p)+(p-\frac12)r_3+(1-p)+(p-\frac12)r_4$ which is $4(1-p)+(p-\frac12)(r_1+r_2+r_3+r_4)$ and you know $r_1+r_2+r_3+r_4=k_1+k_2$ $\endgroup$
    – Henry
    Commented Aug 12, 2021 at 7:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.