无限重掷骰子的收益期望
probability - Expected value of game involving 100-sided die - Mathematics Stack Exchange
题干
给定已知概率分布\(D\)，记第一次采样结果为\(a_1\)。你可以：
- 接受该采样，获得收益\(a_1\)；
- 拒绝该采样，花费\(k\)（\(k>0\)）的代价重新采样，记第二次采样结果为\(a_2\)；
然后你可以接受\(a_2\)，获取等量的收益，或者再次花费\(k\)的代价重新采样。重新采样次数无限制。
请给出一个最优策略，最大化获得的收益，并计算该策略下收益的数学期望。
特例：\(D\)为整数集\(\{1, \dots, 100\}\)上的均匀分布，\(D=U(1,100)\)等。
解答
设投掷者在使用最优策略，且已经重采样了\(m\)次，最近一次采样结果为\(n\)时，应当进行的决策：
- 若此时接受采样，则收益为\(n - km\)。
- 若此时仍选择重新采样，记在\(m=0\)时的期望收益为\(E\)，由马尔可夫性知，此时的期望收益为\(E - k(m + 1)\)。
要使收益最大化，我们可以有：当且仅当\(E - k(m + 1) > n - km\)，即\(n < E - k\)时，选择重新采样。可见该决策与\(m\)无关。该不等式可以取等号。
考虑\(m=0\)时的决策：
- 当\(n > E - k\)时，接受采样，获得\(n\)的收益。\(E(n)\)取决于\(D\)在\([E-k, +\infty)\)的条件分布；
- 当\(n \leq E - k\)时，重新采样，获得\(E - k\)的收益。
我们对\(D\)为整数集\(\{1, \dots, N\}\)上的均匀分布的特例进行计算：
\[ E = \frac{N - E + k}{N} \cdot \frac{N + E - k}{2} + \frac{E - k}{N}(E-k) \]
其中\(\frac{N - E + k}{N}\)为事件\(n > E - k\)发生的概率，\(\frac{N + E - k}{2}\)为该事件下的条件期望\(E(n)\)的大小。
整理得到
\[ E^2 - (2k + 2N)E + N^2 + k^2 = 0. \]
由求根公式得\(E = k + N \pm \sqrt{2kN}\)。其中大根\(k + N + \sqrt{2kN} > N\)，故舍去。于是
\[ E = k + N - \sqrt{2kN}. \]
但这一结果有一点小问题。原因在于，概率\(\frac{N - E + 1}{N}\)是连续的，而非离散的。上式实际上是\(D = U(1, N)\)时的结果。
为方便计算，我们接下来只讨论\(k=1\)的特例。若要离散化概率，我们需要修改方程为
\[ E^* = \frac{N - e + 1}{N} \cdot \frac{N + e}{2} + \frac{e - 1}{N}(E^* - 1) \]
化简为
\[ E^* = \frac{N^2+N+2-e-e^2}{2(N-e+2)} \]
其中\(e \in \mathbb Z\)，表示我们能接受的最差的采样结果。直觉上，\(e = \lceil E \rceil\)或\(e = \lfloor E \rfloor\)，然后需要代入上式求解\(E^*\)。
对于\(N = 100\)的特例，我们计算一个具体的\(E^*\)。首先
\[ E = 101 - 10\sqrt{2} \approx 86.8, \]
于是\(e = 86\)或\(e = 87\)。带入分别求得\(E^* = 87\frac{1}{3}, E^* = 87\frac{5}{14}\)。
由于\(\frac{5}{14} > \frac{1}{3}\)，故最优策略对应的\(e = 87\)，\(E^* = 87\frac{5}{14}\)。