Panda's Birthday Present
题目描述
On Panda’s Birthday party, he received a strange present from Jason. The present is a black box with $4$ dices in it which is used to play a game. The dice in the box is unusual. Instead of the digits, only red or blue is painted on each side of the dice. Before the first round of the game, the box can repaint every side of every dice red or blue with equal probability. Then for each round of the game, the box will roll the $4$ dices and tell the player the number of red side facing up, which is the point the player get. Now, Panda has play it for two rounds and he tell you the point he has got for each round. Can you tell him the expected point he can get for next round.
题意概述
一个盒子里有四个骰子，初始时它们每一面都被等概率染成红色或蓝色（你并不知道具体的染色方案）。每次你会摇动盒子，然后观察有几个骰子朝上的面是红色的。给定前两次观察到的值$p, q$，求第三次观察到的值的期望。
算法分析
为了方便起见，我们假设$0^0=1$。首先可以知道的结论：
- 对于一个骰子，它有$t$个面被染成红色的概率$P(x=t)={ {6 \choose t} \over 2^6}={ {6 \choose t} \over 64}$；
- 扔一个骰子$n$次，其中有$k$次朝上的面是红色的概率为$\sum_{i=0}^6 P(x=i) \cdot {i^k(6-i)^{n-k} \over 6^n}$。
考虑不管是一次操作中的多个骰子还是多次操作，它们其实是独立重复实验，与顺序无关。因此，只要$p+q$是确定的，那么第三次的期望也是确定的。令$1$表示红色面朝上、$0$表示蓝色面朝上，那么我们所要求的就是$P(??1|??)$，其中$??$表示前两次骰子朝上的面分别是什么。
根据贝叶斯定理，$P(H|E)={P(H)P(E|H) \over P(E)}$，所以$P(111|11)={P(111)P(11|111) \over P(11)}$。经计算可得
$$
\begin{align}
P(111|11)&={9 \over 14} \\
P(101|10)&={1 \over 2} \\
P(001|00)&={5 \over 14}
\end{align}
$$
再次考虑独立重复实验。因为它们可以任意交换顺序，所以可以直接将前两次朝上的面是红色的骰子两两并在一起算，朝上的面是蓝色的骰子两两并在一起算，若有剩下的一对红色蓝色则将它们并在一起。
具体来说，若$2 \mid p+q$，则期望为
$$
{p+q \over 2} \cdot {9 \over 14}+\left(4-{p+q \over 2}\right) \cdot {5 \over 14}={p+q+10 \over 7}
$$
否则，期望为
$$
{p+q-1 \over 2} \cdot {9 \over 14}+\left(4-{p+q+1 \over 2}\right) \cdot {5 \over 14}+{1 \over 2}={p+q+10 \over 7}
$$