如何计算随机变量argmax函数的精确/近似期望？含非递增向量场景

给定非递增向量$b\in\mathbb{R}^n$，服从已知分布$F$，目标计算：
$$\mathbb{E}\left[\underset{i\in{1,2,\dots,n}}{\text{argmax}}\ (i\cdot b_i)\right]$$
这里的$\text{argmax}$指使$i\cdot b_i$取最大值的下标$i$；若存在多个下标取到最大值，需明确约定（下文默认取最小下标，特殊情况可按需调整）。

$\text{argmax}_i (i\cdot b_i)$是离散随机变量，取值为$1,2,\dots,n$。根据期望定义，可直接展开为概率加权和：
$$\mathbb{E}\left[\text{argmax}i (i\cdot b_i)\right] = \sum{k=1}^n k\cdot \mathbb{P}\left(\text{argmax}_i (i\cdot b_i) = k\right)$$
核心是计算每个$k$对应的概率$\mathbb{P}\left(\forall j\neq k,\ k\cdot b_k \geq j\cdot b_j\right)$，结合$b$的非递增性可简化条件。

利用非递增性简化概率条件 #

因$b_1\geq b_2\geq\cdots\geq b_n$，对$j<k$，$b_j\geq b_k$但$j<k$，$j\cdot b_j$与$k\cdot b_k$的大小关系不确定；对$j>k$，$b_j\leq b_k$且$j>k$，同样需具体分析。

固定$k$时，事件$\text{argmax}_i (i\cdot b_i)=k$等价于：
$$\begin{cases}
k\cdot b_k \geq j\cdot b_j & \forall j<k \
k\cdot b_k \geq j\cdot b_j & \forall j>k
\end{cases}$$
将其转化为$b$各分量的不等式组后，即可通过分布$F$的联合密度或分布函数计算概率。

要保证期望存在且可计算，通常对$F$做以下限制：

1. 正则性条件 #

• $F$绝对连续：存在联合概率密度函数$f(b_1,b_2,\dots,b_n)$，仅在满足$b_1\geq b_2\geq\cdots\geq b_n$的区域上$f>0$，其余区域为0。此时，各概率可通过在对应不等式区域上积分$f(b)$得到。
• 无平级最大值的零概率事件：$\mathbb{P}\left(\exists i\neq j,\ i\cdot b_i = j\cdot b_j\right)=0$。该条件在$F$绝对连续时自动满足，因等式对应$\mathbb{R}^n$中的低维子流形，测度为0。

2. 矩存在性条件 #

要求$\mathbb{E}[|i\cdot b_i|]<\infty$对所有$i=1,\dots,n$成立，确保$\text{argmax}$的期望收敛（因$\text{argmax}$取值被$n$限制，只要各$i\cdot b_i$的期望有限，概率加权和必收敛）。

3. Lipschitz连续性（用于近似计算） #

若$F$的密度函数$f(b)$满足Lipschitz连续性：存在常数$L>0$，对任意满足非递增条件的$b,b'$，有$|f(b)-f(b')|\leq L\cdot|b-b'|$，则可使用数值积分（如蒙特卡洛采样+拟牛顿法）近似计算期望，且误差可控。

若分布$F$的解析计算复杂度高，可采用蒙特卡洛采样：

1. 从$F$中抽取大量满足非递增性的样本$b^{(1)},b{(2)},\dots,b^{(m)}$；
2. 对每个样本$b^{(t)}$，计算对应的$\text{argmax}$下标$k_t$；
3. 计算样本均值$\frac{1}{m}\sum_{t=1}^m k_t$，作为期望的近似值。

当样本量$m$足够大时，根据大数定律，近似值会收敛到真实期望。若$F$满足Lipschitz连续性，还可通过方差缩减技术（如控制变量法）提升近似效率。

内容的提问来源于stack exchange，提问作者Sagi Levy