球盒分配优化问题：求证平均分配是否为最大化取球期望数量的最优策略

大家好，我最近碰到了一个看似简单直观，但折腾了很久都没完全解决的球盒问题，想在这里和大家讨论：

问题描述 #

假设我们有M个完全相同的盒子，N个完全相同的球，先把N个球以某种方式分配到M个盒子里。之后按照以下规则无放回地取球：

• 每次先观察所有有球的盒子，从中等概率随机选一个盒子，再从这个盒子里等概率取走一个球；
• 当只剩一个盒子还有球时，停止取球。

核心问题：初始时怎么分配N个球到M个盒子，才能最大化取球的总数量的期望值？

我的直觉是平均分配（每个盒子要么$\lfloor N/M \rfloor$个球，要么$\lceil N/M \rceil$个球）是最优策略，但一直没找到反例，也没能给出严谨证明。

我的建模尝试：马尔可夫决策过程（MDP） #

我把这个问题建模成了马尔可夫过程，具体如下：

• 定义状态 $X = (x_1,x_2,\ldots,x_M)\in \mathbb N^M$，其中$x_i$表示第i个盒子的球数；
• 由于盒子是同质的，状态的顺序不影响结果，所以可以假设状态已经按球数降序排列：$x_1\ge x_2 \ge \dots \ge x_M$；
• 定义状态空间 $\Delta(N,M) \triangleq \left{X=(x_1,\ldots,x_M)\in \mathbb{N}^M\bigg|\displaystyle\sum\limits_{i = 1}^M x_i = N, x_1\ge x_2 \ge \dots \ge x_M\right}$；
• 目标是求解优化问题：$\max\limits_{X\in \Delta(N,M)}V(X)\triangleq\mathbb E[\mathcal T\mid X_0 = X]$，其中$\mathcal{T}$是取球的总数量；
• 边界条件：当只有一个盒子有球时（即$X = m\cdot \mathbf e_k$，$m\in\mathbb N$，$\mathbf e_k$是第k位为1的单位向量），$V(X)=0$；另外如果状态中出现负分量（不可能的状态），也定义$V(X)=0$。

递推公式推导 #

利用迭代期望法则，我推导出了状态价值函数$V(X)$的递推关系：
$$
V(X) = 1+\frac{1}{\sum\limits_{k = 1}^M\mathbb 1{x_{k}\ge 1}}\cdot\displaystyle\sum\limits_{k = 1}^M V(X-\mathbf{e}k)
$$
解释一下：每次取球后，我们会进入$X-\mathbf{e}k$的状态（从第k个盒子取走一个球），而当前有球的盒子数是$\sum\limits{k = 1}^M\mathbb 1{x{k}\ge 1}$，每个有球的盒子被选中的概率相等，所以递推式里先加1（当前取的这一个球），再加上后续期望的平均。

已取得的进展与卡住的地方 #

通过这个递推公式，我只证明了一个比较直观的结论：对任意状态X和任意k，$V(X)<V(X+\mathbf e_k)$——也就是给任意盒子多加一个球，都会提高取球的期望总数量。

我原本想尝试用归纳法证明平均分配的最优性，但尝试了好几次都没成功，卡在了如何比较“不均等分配”和“均等分配”状态的V值大小上。

备注：内容来源于stack exchange，提问作者koko