paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Drawing with Distance

带距离的抽取
LMCS vol.Volume 21, Issue 22025匹配度 1/10 · 该论文是概率论与度量空间的理论研究,讨论抽取操作在Kantorovich距离下的等距性与极限,与静态分析、LLM/Agent、浮点程序分析、贝叶斯程序分析等核心方向无直接关联。仅标签“量子与概率编程”略有概率编程背景,但内容不涉及程序分析或LLM交叉。引用 1 inbox
Bart Jacobs
crossref: 2026-09-10

AI 速览

一句话:证明多项、超几何与Polya抽取在Kantorovich距离下均为等距映射,并给出大瓮与大抽取量极限。

经典离散概率中,从瓮中抽取彩色球有三种基本模式:多项(抽取后放回)、超几何(抽取后删除)与Polya(抽取后添加)。论文将瓮与抽取分布分别置于Kantorovich度量空间,并用Kantorovich-over-Kantorovich距离比较抽取结果。核心结果是证明这三种抽取操作都是等距映射,即精确保持Kantorovich距离。进一步研究极限行为:当瓮规模增大时,超几何与Polya抽取到多项抽取的Kantorovich距离趋于零;当抽取量增大时,瓮与归一化多项抽取的距离依概率趋于零。作者将后两个结论称为大瓮律与大抽取律。该工作以新颖的度量方式重新表述了已知结果。

问题
如何用统一的度量框架刻画并比较从瓮中抽取彩色球的不同随机操作及其极限行为。
方法
把瓮和抽取分布建模为Kantorovich度量空间,用Kantorovich-over-Kantorovich距离分析三种抽取映射,并证明等距性与极限定理。
评估
通过数学证明证明三种抽取均为等距映射,并证明大瓮与大抽取量下的Kantorovich距离极限。
原文摘要(Abstract)

Drawing (a multiset of) coloured balls from an urn is one of the most basic models in discrete probability theory. Three modes of drawing are commonly distinguished: multinomial (draw-replace), hypergeometric (draw-delete), and Polya (draw-add). These drawing operations are represented as maps from urns to distributions over multisets of draws. The set of urns is a metric space via the Kantorovich distance. The set of distributions over draws is also a metric space, using Kantorovich-over-Kantorovich. It is shown that these three draw operations are all isometries, that is, they exactly preserve the Kantorovich distances. Further, drawing is studied in the limit, both for large urns and for large draws. First it is shown that, as the urn size increases, the Kantorovich distances go to zero between hypergeometric and multinomial draws, and also between P\'olya and multinomial draws. Second, it is shown that, as the drawsize increases, the Kantorovich distance goes to zero (in probability) between an urn and (normalised) multinomial draws from the urn. These results are known, but here, they are formulated in a novel metric manner as limits of Kantorovich distances. We call these two limit results the law of large urns and the law of large draws.

链接与引用

DOI 原文 · arXiv · PDF(开放获取) · DBLP

BibTeX
@article{Jacobs25,
  title = {Drawing with Distance},
  author = {Bart Jacobs},
  journal = {Logical Methods in Computer Science},
  volume = {Volume 21, Issue 2},
  year = {2025},
  doi = {10.46298/lmcs-21(2:11)2025}
}