当前位置: 首页 > news >正文

邮票收集问题正推证明

参考文献。

(题目:有一个 \(n\) 面的骰子,扔到各面的概率相等。求期望扔几次可以使每一面都被扔到。)

\(f_i\) 表示已经扔到过 \(i\) 个不同的面时,期望的扔的次数。

称事件 \(A\) 为扔到了已经扔过的面,事件 \(B\) 为扔到了新的面。

考虑如何求出 \(f_i\)。此前已经扔到过 \(i-1\) 个面,那么有 \(P(A)=\frac{i-1}{n}\);容斥一下,\(P(B)=1-P(A)=\frac{n-i+1}{n}\)

于是我们有:

  • \(1\) 次后触发事件 \(B\) 的概率为 \(P(B)=\frac{n-i+1}{n}\)

  • \(2\) 次后触发事件 \(B\) 的概率(即先发生 \(1\) 次事件 \(A\),再发生一次事件 \(B\))为 \(2\cdot P(A)\cdot P(B)=2\cdot\frac{i-1}{n}\cdot\frac{n-i+1}{n}\)

  • \(3\) 次后触发事件 \(B\) 的概率(即先发生 \(2\) 次事件 \(A\),再发生一次事件 \(B\))为 \(3\cdot [P(A)]^2\cdot P(B)=3\cdot(\frac{i-1}{n})^2\cdot\frac{n-i+1}{n}\)

  • ……

观察得到,扔 \(k\) 次后触发事件 \(B\) 的概率为 \(k\cdot [P(A)]^{k-1}\cdot P(B)=k\cdot (\frac{i-1}{n})^{k-1}\cdot \frac{n-i+1}{n}\)

总的期望即为所有情况的加权和,即:

\[E[X]=\sum\limits_{k=1}^{\infty}k\cdot [P(A)]^{k-1}\cdot P(B) \]

简要起见,设 \(q=P(A),p=P(B)\)。易得 \(p+q=1\)

\(S=\sum\limits_{k=1}^{\infty}k\cdot q^{k-1}\),易得 \(E[X]=S\cdot p\)

考虑将 \(S\) 变形。左右同乘 \(q\)

\[qS=\sum\limits_{k=1}^{\infty}k\cdot q^k \]

两式相减:

\[S-qS=(\sum\limits_{k=1}^{\infty}k\cdot q^{k-1})-(\sum\limits_{k=1}^{\infty}k\cdot q^k) \]

即:

\[(1-q)S=\sum\limits_{k=0}^{\infty}q^{k} \]

右式是几何级数,那么由 \(|q|<1\) 知:

\[\sum\limits_{k=0}^{\infty}q^{k}=\frac{1}{1-q} \]

回代上式:

\[(1-q)S=\frac{1}{1-q} \]

左右同乘 \(\frac{1}{1-q}\)

\[S=\frac{1}{(1-q)^2} \]

回代到 \(E[X]\)

\[\begin{align*} E[X]&=S\cdot p\\ &=\frac{p}{(1-q)^2} \end{align*} \]

\(p+q=1\),有:

\[\begin{align*} E[X]&=\frac{p}{(1-q)^2}\\ &=\frac{p}{p^2}\\ &=p^{-1}\\ &=[P(B)]^{-1}\\ &=\frac{n}{n-i+1} \end{align*} \]

易得 \(f_i=f_{i-1}+E[X]\),即:

\[f_i=f_{i-1}+\frac{n}{n-i+1} \]

得证。

http://www.hskmm.com/?act=detail&tid=24385

相关文章:

  • 2025多校冲刺CSP模拟赛2 2025.10.4 模拟炸
  • 算法乱谈
  • 2025 年 9 月习题集
  • C# 代码规范
  • 实用指南:babelfish for postgresql 分析--todo
  • NFC 贴卡自动拨打微信视频电话
  • 10.4
  • 实用指南:d-分离:图模型中的条件独立性判定准则
  • [MCP] 监听资源更新
  • [RAG] 基础知识
  • CF1408F Two Different
  • 数据结构 - 字典树 Trie
  • 激活函数实现
  • 漏洞赏金入门指南:从零开始的实战方法论
  • PMON failed to acquire latch 的报错及sqlplus / as sysdba 无法连接 - 详解
  • 2025CSP-S模拟赛58 比赛总结
  • 精读C++设计模式20 —— 结构型设计模式:桥接模式 - 详解
  • 用纯.NET开发并制作一个智能桌面机器人(六):使用.NET开发一个跨平台功能完善的小智AI客户端
  • 2025/10/4 总结
  • Qt处理Windows平板上摄像头
  • 你必须知道的TCP和UDP核心区别,快速搞懂这两大协议!
  • [swift 外部干涉法 extension]
  • 2025国庆Day3
  • 量子迁移计划启动:应对未来密码学挑战
  • HPE SPP 2025.09.00.00 - HPE 服务器固件、驱动程序和系统软件包
  • 详细介绍:Linux字符设备驱动开发全攻略
  • sql注入和xss漏洞
  • 数学 trick
  • 完整教程:精读C++20设计模式——行为型设计模式:解释器模式
  • js疑惑