Grenander递减密度估计

若某种等待时间的密度从零开始只会下降，可以利用这项形状信息估计整条密度，而不先挑选一个平滑带宽。不过“把柱子排成递减”还不是答案：相邻观测之间的空隙有长有短，柱子的面积必须恰好为一。Grenander估计把这些长度和样本频数同时放进合并规则，最后得到一条能直接核验最大似然的阶梯。

形式陈述

密度的支持和点值版本先固定

观测来自已知支持半直线 $[0,\infty)$ 上的Lebesgue 概率密度。候选密度非负、非增，在每个 $x>0$ 处取左连续版本，且积分为一；在零处取右侧极限，允许该极限为无穷。版本约定在看到数据前固定，不能为了提高似然单独改几个样本点的值。

给定一份非空样本，将相同正数合并为

0=x_0<x_1<\cdots<x_m,\qquad n_j\ge1,\quad n=\sum_jn_j,\quad p_j=n_j/n,\quad \Delta_j=x_j-x_{j-1}>0. \tag{1}

此处所有实际观测严格大于零；零观测的失败情形另在下文处理。IID模型的归一化对数似然为

\ell(f)=\sum_{j=1}^m p_j\log f(x_j), \qquad \log0=-\infty. \tag{2}

频数产生经验分布函数 $F_n(x)=\sum_{x_j\le x}p_j$ 。它有原子，估计的密度却相对于Lebesgue长度；这两种量不能直接混成一列“概率”。

定理给出唯一的阶梯解（并在所选版本下确定所有正点值）：

\widehat f(x)=\widehat q_j\quad(x_{j-1}<x\le x_j), \qquad \widehat f(x)=0\quad(x>x_m), \tag{3}

其中 $\widehat q$ 唯一最大化

\sum_jp_j\log q_j, \qquad q_1\ge\cdots\ge q_m\ge0, \qquad \sum_j\Delta_jq_j=1. \tag{4}

最优的每个 $\widehat q_j$ 都严格为正。将点 $(0,0)$ 、 $(x_j,\sum_{i\le j}p_i)$ 的最小凹上界连成折线，之后恒等于一，则 $\widehat f$ 正是这条折线的左斜率。这里最小凹上界是所有盖住这些点的凹函数中逐点最小者；以下合并证明也会直接构造并认证它的最小性。

为什么无穷维问题真的缩成式(4)

对一份似然有限的竞争密度 $f$ ，令 $q_j=f(x_j)>0$ 。单调性保证在 $(x_{j-1},x_j)$ 内 $f(x)\ge q_j$ ，所以

0<c:=\sum_j\Delta_jq_j\le\int_0^\infty f(x)\,dx=1.

把各间隔改成常数 $q_j$ ，删去 $x_m$ 后的尾部，再除以 $c$ 。所得密度仍非增、左连续、积分一，而且样本处的高度由 $q_j$ 升为 $q_j/c$ 。其对数似然是 $\ell(f)-\log c\ge\ell(f)$ 。因此式(4)覆盖一个全局最优者，而非只在预定直方图类里寻找局部答案。

式(4)允许零坐标的可行集非空、闭且有界，因为 $q_j\le1/\Delta_j$ 。乘积 $\prod_jq_j^{p_j}$ 在其上连续，且常数 $q_j=1/x_m$ 给严格正值，故最大值达到并且没有零坐标。正坐标上的对数目标严格凹，保证唯一最优向量。若原密度也最优，上述 $c$ 必为一；单调下界与总积分相等又迫使原密度等于阶梯几乎处处。左连续版本于是固定所有 $x>0$ 的值。

直觉

密集的观测会让短区间中的初始高度 $p_j/\Delta_j$ 很大。如果右边的高度反而高于左边，就不能把两根柱子原样保留。将它们拼成一个长区间，用总质量除以总长度作为新高度；重复处理违反递减的相邻块。

同一个规则在CDF图上更容易看：某一段斜率低于后一段，折线向上弯，不是凹函数。把这两段换成连接外端点的一根弦，便把中间点盖在下方。反复合并后，斜率从左到右不再增加，柱高递减而面积自动保留。

经验CDF的凹上界与同一份递减阶梯密度：合并按实际间距加权，不把相同频数误作相同高度

块栈怎样计算

每块保存左右索引、长度 $W=\sum\Delta_j$ 、质量 $P=\sum p_j$ ，高度为 $v=P/W$ 。

从左到右读入一个间隔，压入单点块
若末尾左块高度小于右块高度，合并其长度和质量
重复第二步，直到末尾不再违反递减，再读下一间隔
全部读完后，把每块高度赋给块内全部间隔；相等的相邻块可再合并以便展示

这是相邻违反块合并的同一栈结构，但这里要求递减，权重是间距 $\Delta_j$ ，原始数值是 $p_j/\Delta_j$ 。原始数值不必位于 $[0,1]$ ；输出是密度高度，也不是校准后的分类概率。排序之后压栈 $m$ 次、合并至多 $m-1$ 次，所以合并使用 $O(m)$ 次算术和 $O(m)$ 空间。有理输入的位成本还要计分子分母增长。

合并为什么给最小凹上界

每个块 $[a,b]$ 始终保持下面的不变量：若高度为 $v$ ，则

\sum_{j=a}^k p_j\le v\sum_{j=a}^k\Delta_j\quad(a\le k<b), \qquad \sum_{j=a}^bp_j=v\sum_{j=a}^b\Delta_j. \tag{5}

单点显然成立。合并高度 $v_L<v_R$ 的两块后，新高度 $v$ 介于两者之间。前缀若完全落在左块，原上界 $v_L$ 不超过 $v$ 。若前缀进入右块，改看右块剩余后缀：原前缀不等式与整块等式给后缀平均至少 $v_R\ge v$ ，从合并块的总质量中减去后缀，就得到新前缀上界。这证明每次合并保留式(5)。

最终折线在每个块的两个端点碰到经验累计质量，在块内盖住所有数据点，斜率又非增，所以是一条凹上界。任何其他凹上界，在这些块端点至少同样高；凹性使它在两端之间至少等于端点弦，而我们的折线恰好就是这根弦。因此其他上界处处不低于它，最小性得到证明。样本点之间 $F_n$ 保持常数，折线非降，所以盖住点也就盖住了整条经验CDF。

例子与边界

从合并结果拿到完整似然证书

对合并产生的 $\widehat q$ ，定义

\eta_k=\sum_{j=1}^k\left(\Delta_j-\frac{p_j}{\widehat q_j}\right), \qquad \eta_0=0. \tag{6}

每个完整块对这项和的贡献为零；块内贡献由式(5)除以该块高度得非负。因此

\eta_k\ge0, \quad \eta_m=0, \quad \eta_k(\widehat q_k-\widehat q_{k+1})=0. \tag{7}

最后一个式子只对 $k<m$ 使用。严格下降只能发生在块边界，而那里累计乘子为零。

这些数字足够认证对全部可行密度的最优性。对式(4)中任意正可行 $q$ ，负对数的凸性给对数切线不等式 $\log t\le t-1$ ，从而

\begin{aligned} \ell(q)-\ell(\widehat q) &\le\sum_j\frac{p_j}{\widehat q_j}(q_j-\widehat q_j)\\ &=\sum_j(\Delta_j+\eta_{j-1}-\eta_j)(q_j-\widehat q_j)\\ &=\sum_{k=1}^{m-1}\eta_k(q_{k+1}-q_k)\le0. \end{aligned} \tag{8}

第二到第三行使用两份面积都为一、端点乘子为零及互补等式。含零坐标的竞争解似然为负无穷，不必作非法除法。有限化证明再把结论传给任意原候选密度。由严格的对数切线取等条件，等号只能在每个 $q_j=\widehat q_j$ 时出现。

一份不等距算例

取位置 $(1,3,4)$ ，各出现一次。间距为 $(1,2,1)$ ，初始高度为 $(1/3,1/6,1/3)$ 。合并后两块，得到

\widehat q=(1/3,2/9,2/9), \qquad \eta=(0,1/2,0).

面积为 $1/3+2(2/9)+2/9=1$ 。在 $x=3$ ，拟合CDF为 $1/3+4/9=7/9$ ，高于经验CDF的 $2/3$ ；块的终点 $x=4$ 则同为一。后两点高度相等，对应唯一非零乘子的位置。若错误地按两根柱子等权平均为 $1/4$ ，总面积变成 $1/3+3/4=13/12$ ，连合法密度都没有得到。

平票、零与原点分别是什么问题

相同正观测必须累计其频数，不能制造零长度间隔再除以零。连续IID模型中精确平票是概率零事件，但估计准则仍能处理这份输入；如果平票来自仪器取整，真实观测是一个区间或分箱事件，正确似然应使用区间概率。把取整值当精确点继续最大化式(2)，是另一项模型选择。

零观测更严重。若至少一个数据为零，选一份在所有正观测处为正的递减密度 $g$ ，并令

f_\varepsilon(x)=\frac{1}{2\varepsilon}\mathbf1_{[0,\varepsilon]}(x) +\frac12 g(x), \qquad \varepsilon\downarrow0. \tag{9}

每份密度都归一化、递减且采用规定版本。零处高度趋于无穷，固定正观测处在足够小的 $\varepsilon$ 下仍为 $g(x)/2>0$ ，所以似然无界。不能把零偷偷替换成一个软件小常数，再声称得到原问题的有限MLE。

已知原点同样重要。把数据单位放大为 $y=cx$ 、 $c>0$ ，所有间距乘以 $c$ ，拟合密度变成 $\widehat f(y/c)/c$ ，块划分不变。若只是把观测减去样本最小值却仍把零当新支持原点，第一间距和模型都改变，还会产生零观测。已知支持起点 $a$ 时可以同时平移支持和数据；未知起点不能由这一步免费估出。

推论与应用

一张可独立验收的输出表

交付应包括去重正位置、正确频数、每个块的总长度与总质量、拟合高度、面积和式(6)的全部累计乘子。检查非增、正值、面积一、乘子非负和互补即可，再由式(8)证明全局最优。只有画出来的阶梯看似递减，或只比较少数备选似然，都不是同一份证书。

末端 $x_m$ 取左侧高度，随后立刻为零，这是规定的密度版本；CDF本身仍连续。若交换成右连续阶梯而在样本点取了较低一侧，积分虽不变，样本似然却可能降低。版本与点值应随结果一起保存。

形状约束没有自动解决推断

核密度估计通过核和带宽平滑样本，本页通过递减形状限制似然。这里无需选择带宽，却需要已知半直线和可信的递减假设。真实密度若先升后降，所得最优仅是所设类别内的最优，不会因计算证书正确就变成无偏估计。

本页的有限样本结论是存在、唯一、算法和似然最优性。它没有给逐点正态近似、置信带或端点一致性；这些统计问题需要额外的抽样、局部形状和极限理论。尤其不能因为CDF已经被一条凹曲线盖住，就把那条曲线当成具有指定覆盖率的置信上界。

参考资料

Piet Groeneboom，Estimating a monotone density，CWI Report MS-R8403，1984，§1：非增左连续密度、经验CDF凹上界与MLE的对象约定。本文对有限样本另给间距加权块不变量与完整对数切线证明，不调用该文后续渐近率。
Piet Groeneboom and H. P. Lopuhaä，Isotonic estimators of monotone densities and distribution functions: basic facts，1993。此处核对的是官方书目与摘要所说明的左连续MLE性质，未把未取得的全文当作已读证明。

形式陈述 ​

密度的支持和点值版本先固定 ​

为什么无穷维问题真的缩成式(4) ​

块栈怎样计算 ​

合并为什么给最小凹上界 ​

从合并结果拿到完整似然证书 ​

一份不等距算例 ​

平票、零与原点分别是什么问题 ​

一张可独立验收的输出表 ​

形状约束没有自动解决推断 ​

反向链接