Quant Interview · Probability

折木棍 · Broken Stick

Complete Problem Set · Rigorous Derivations · Interview Extensions

目录 · Contents

  1. 第一类：一次折断（2段）
  2. 第二类：两次随机折断（3段 Dirichlet）
  3. 第三类：先折一次再折长段
  4. 第四类：分布函数与高阶结论
  5. 扩展题 · Extensions
  6. 速查表 · Cheat Sheet
Category 01

一次折断 · Single Break (2 Pieces)

木棍长度为 1，断点 \(X \sim \mathrm{Uniform}(0,1)\)，得到两段 \(X\) 和 \(1{-}X\)。

Q 01

短段与长段的期望长度

随机折断长为 1 的木棍，求较短段和较长段的期望长度。
Answer \(E[\text{短段}] = \dfrac{1}{4},\quad E[\text{长段}] = \dfrac{3}{4}\)
展开推导 · Full Derivation
S1
令 \(S = \min(X,\,1{-}X)\) 为短段长度。求其 CDF：
$$P(S > s) = P\bigl(\min(X,1{-}X)>s\bigr) = P(s < X < 1{-}s) = 1{-}2s, \quad s\in\left[0,\tfrac12\right]$$
S2
密度函数：\(f_S(s) = 2\)，\(s\in[0,\tfrac12]\)。即 \(S\sim\mathrm{Uniform}(0,\tfrac12)\)。
S3
计算期望：
$$E[S] = \int_0^{1/2} s\cdot 2\,ds = \left[s^2\right]_0^{1/2} = \frac{1}{4}$$
S4
长段 \(L = 1 - S\)，故 \(E[L] = 1 - \tfrac{1}{4} = \tfrac{3}{4}\)。
直觉 Intuition
短段均匀分布在 \([0,\tfrac12]\)，期望自然是 \(\tfrac14\)。长短段期望之和为 1。
Q 02

两段长度差的期望

求 \(E|X - (1{-}X)| = E|2X{-}1|\)。
Answer \(E|2X{-}1| = \dfrac{1}{2}\)
展开推导 · Full Derivation
方法一
利用对称性，在 \([\tfrac12,1]\) 上积分后乘 2：
$$E|2X{-}1| = 2\int_{1/2}^1(2x{-}1)\,dx = 2\left[x^2{-}x\right]_{1/2}^1 = 2\cdot\frac{1}{4} = \frac{1}{2}$$
方法二
等价于长短段之差：\(E[L - S] = \tfrac34 - \tfrac14 = \tfrac12\)。
Category 02

两次随机折断 · Two Random Breaks (3 Pieces)

在 \([0,1]\) 上均匀随机选两个断点，三段 \((L_1,L_2,L_3)\) 在 2-simplex 上均匀分布， 即 \((L_1,L_2,L_3)\sim\mathrm{Dirichlet}(1,1,1)\)。边缘分布：\(L_i\sim\mathrm{Beta}(1,2)\)，密度 \(f(x)=2(1{-}x)\)。

Q 03

三段能否构成三角形

将木棍随机折成三段，三段能构成三角形的概率？
Answer \(P(\text{三角形}) = \dfrac{1}{4}\)
展开推导 · Full Derivation

三角形条件：任意两边之和 > 第三边，等价于三边都 \(<\tfrac12\)。

S1
设两断点 \(U,V\sim U(0,1)\) 独立，不妨设 \(U{<}V\)（在面积 \(\tfrac12\) 的下三角区域）。 三段为 \(a=U,\ b=V{-}U,\ c=1{-}V\)。
S2
三角形条件：\(U{<}\tfrac12,\; V{-}U{<}\tfrac12,\; 1{-}V{<}\tfrac12\)，即：
$$U < \frac12,\quad V > \frac12,\quad V < U + \frac12$$
S3
几何法（最简）：在单纯形 \(\{l_1{+}l_2{+}l_3{=}1,\,l_i{\ge}0\}\) 上， 满足 \(l_i{<}\tfrac12\) 的区域是以 \((\tfrac13,\tfrac13,\tfrac13)\) 为中心的相似三角形， 线性缩放比为 \(\tfrac12\)，面积比 \((\tfrac12)^2 = \tfrac14\)。
$$P(\text{三角形}) = \frac{\text{小三角形面积}}{\text{总面积}} = \frac{1}{4}$$
验证
用容斥原理：\(P(\exists\,l_i\ge\tfrac12) = 3P(l_1\ge\tfrac12) = 3\cdot(\tfrac12)^2 = \tfrac34\)，故三角形概率 \(=1-\tfrac34=\tfrac14\)。（注意 \(P(l_1\ge\tfrac12)=\int_{1/2}^12(1{-}x)dx=\tfrac14\)，共三段，不会同时超过。）
Q 04

最长段大于 1/2 的概率

三段中最长段超过 \(\tfrac12\) 的概率？
Answer \(P(L_{\max} > \tfrac{1}{2}) = \dfrac{3}{4}\)
展开推导 · Full Derivation

\(L_{\max} \le \tfrac12\) 当且仅当三角形条件成立，概率 \(= \tfrac14\)。

$$P(L_{\max} > \tfrac12) = 1 - \tfrac14 = \frac{3}{4}$$
对称性论证
由对称性，三段中每段超过 \(\tfrac12\) 的概率各为 \(\tfrac14\)（\(P(L_i>\tfrac12)=(\tfrac12)^2=\tfrac14\)），且至多一段可超过 \(\tfrac12\)，故 \(P(\text{某段}>\tfrac12)=3\times\tfrac14=\tfrac34\)。
Q 05

排序后各段的期望长度（Order Statistics）

将三段排序 \(L_{(1)}\le L_{(2)}\le L_{(3)}\)，求 \(E[L_{(1)}],\,E[L_{(2)}],\,E[L_{(3)}]\)。
Answer \(E[L_{(1)}]=\dfrac{1}{9},\quad E[L_{(2)}]=\dfrac{5}{18},\quad E[L_{(3)}]=\dfrac{11}{18}\)
展开推导 · Full Derivation

核心公式（Broken Stick Order Statistics）：

对 \(n\) 段均匀 broken stick，第 \(k\) 大段（\(k=1\) 最大，\(k=n\) 最小）的期望为：

$$\boxed{E[L_{(n-k+1)}] = \frac{1}{n}\sum_{j=k}^{n}\frac{1}{j}}$$

对 \(n=3\)：

$$E[L_{(3)}] = \frac{1}{3}\left(\frac{1}{1}+\frac{1}{2}+\frac{1}{3}\right) = \frac{1}{3}\cdot\frac{11}{6} = \frac{11}{18}$$ $$E[L_{(2)}] = \frac{1}{3}\left(\frac{1}{2}+\frac{1}{3}\right) = \frac{1}{3}\cdot\frac{5}{6} = \frac{5}{18}$$ $$E[L_{(1)}] = \frac{1}{3}\cdot\frac{1}{3} = \frac{1}{9}$$

验证：\(\tfrac{2}{18}+\tfrac{5}{18}+\tfrac{11}{18}=1\) ✓

直接推导（\(E[L_{(3)}]\)）：

S1
在单纯形上，排序后的联合密度 \(f(l_1,l_2,l_3)=3!=6\)，其中 \(0\le l_1\le l_2\le l_3,\;\sum l_i=1\)。
S2
参数化：令 \(l_1=s,\;l_2=s+u\)，则 \(l_3=1{-}2s{-}u\)。条件：\(u\ge0,\;l_2\le l_3\Rightarrow u\le\tfrac{1{-}3s}{2}\)。
$$E[L_{(3)}]=6\int_0^{1/3}\!\int_0^{(1-3s)/2}(1{-}2s{-}u)\,du\,ds$$
S3
内层积分：
$$\int_0^{(1-3s)/2}(1{-}2s{-}u)\,du = (1{-}2s)\cdot\frac{1{-}3s}{2}-\frac{(1{-}3s)^2}{8}=\frac{(1{-}3s)(3{-}5s+s)}{8}$$
展开后得 \(\tfrac{(1{-}3s)(3{-}5s)}{8}\)（注意此处展开略去中间步骤）。
S4
外层积分（注意单纯形的二维测度为 \(\tfrac12\)，密度 \(6\) 在参数化后需乘以 Jacobian \(1\)，积分范围已是 \(\tfrac{1}{12}\) 的面积），最终计算得 \(\tfrac{11}{18}\)。
记忆口诀
调和级数倒序累加，再除以 \(n\)：最大段对应 \(\frac{1}{n}(H_n)\)，其中 \(H_n=\sum_{k=1}^n\frac{1}{k}\)。
Order statistics geometric decomposition

Left: Simplex divided into 6 equal ordering regions by symmetry.
Middle: Level-set / layer-cake visualization of E[L(3)] as swept area.
Right: Harmonic decomposition — each bar shows the contribution of each 1/j term.

Category 03

先折一次再折长段 · Sequential Break (Long Piece)

这是面试中最难且最常考的变体。注意它与 Dirichlet 模型的本质区别：此处三段分布不再是 Dirichlet(1,1,1)。

Q 06

先折一次再折长段 → 三角形概率

Step 1：随机折断，得到 \(X\) 与 \(1{-}X\)。Step 2：取较长段，在其上随机再折。问三段构成三角形的概率。
Answer \(P = 2\ln 2 - 1 \approx 0.3863\)
展开推导 · Full Derivation

设置（WLOG）：由对称性，设 \(X\le\tfrac12\)（较长段为 \(1{-}X\ge\tfrac12\)），并对 \(X\in[0,\tfrac12]\) 积分。

S1
第二次折：设比例 \(U\sim U(0,1)\) 独立，将长段 \((1{-}X)\) 切为 \(U(1{-}X)\) 和 \((1{-}U)(1{-}X)\)。 三段为：
$$a = X,\quad b = U(1{-}X),\quad c = (1{-}U)(1{-}X)$$
S2
三角形条件（每段 \({<}\tfrac12\)）：
  • \(a = X < \tfrac12\)：已满足。
  • \(b = U(1{-}X) < \tfrac12 \;\Rightarrow\; U < \dfrac{1}{2(1{-}X)}\)。
  • \(c = (1{-}U)(1{-}X) < \tfrac12 \;\Rightarrow\; U > 1 - \dfrac{1}{2(1{-}X)}\)。
S3
给定 \(X\in[0,\tfrac12]\)，\(U\) 需落在：
$$1-\frac{1}{2(1{-}X)} < U < \frac{1}{2(1{-}X)}$$
区间长度为：
$$\Delta = \frac{1}{2(1{-}X)} - \left(1-\frac{1}{2(1{-}X)}\right) = \frac{1}{1{-}X} - 1 = \frac{X}{1{-}X}$$
S4
\(X\sim U(0,1)\)，在 \([0,\tfrac12]\) 上密度为 1（原始密度），乘以 2 归一化后对 \([0,\tfrac12]\) 积分：
$$P = 2\int_0^{1/2}\frac{X}{1{-}X}\,dX$$
S5
计算积分（令 \(t=1{-}X\)）：
$$\int_0^{1/2}\frac{X}{1{-}X}\,dX = \int_0^{1/2}\left(-1+\frac{1}{1{-}X}\right)dX = \left[-X-\ln(1{-}X)\right]_0^{1/2}$$ $$= -\frac12 - \ln\frac12 = -\frac12 + \ln 2$$
S6
$$\boxed{P = 2\left(\ln 2 - \frac12\right) = 2\ln 2 - 1 \approx 0.3863}$$
关键比较
Dirichlet 模型（两次随机折）三角形概率 \(= 0.25\)，而此处 \(= 2\ln2{-}1\approx0.386\)，更容易成三角形。原因：限定在长段上再折，避免了出现极长段的情况。
Category 04

分布函数与高阶结论

Q 07

最长段的分布函数 CDF

三段（Dirichlet 模型）最长段 \(L_{\max}\) 的 CDF 是什么？
Answer \(P(L_{\max}\le t)=\begin{cases}0 & t<\tfrac{1}{3}\\ 1-3(1-t)^2 & t\in[\tfrac12,1]\end{cases}\)
展开推导 · Full Derivation
S1
单段边缘分布：\(L_1\sim\mathrm{Beta}(1,2)\)，密度 \(f(x)=2(1{-}x)\)，故：
$$P(L_1 > t) = \int_t^1 2(1{-}x)\,dx = (1{-}t)^2$$
S2
对 \(t>\tfrac12\)：至多一段超过 \(t\)（因为若两段都 \(>t\)，总和 \(>1\)）。 由容斥（无重叠项）：
$$P(L_{\max}>t) = \sum_{i=1}^3 P(L_i>t) = 3(1{-}t)^2,\quad t\in\left[\tfrac12,1\right]$$
S3
故：
$$P(L_{\max}\le t) = 1 - 3(1{-}t)^2,\quad t\in\left[\tfrac12,1\right]$$
验证：\(t=\tfrac12\)：\(1{-}\tfrac34=\tfrac14=P(\text{三角形})\) ✓. \(t=1\)：\(1\) ✓.
完整CDF
$$P(L_{\max}\le t) = \begin{cases}0 & 0\le t < \tfrac13\\ \text{复杂表达式} & \tfrac13\le t < \tfrac12\\ 1-3(1-t)^2 & \tfrac12\le t\le 1\end{cases}$$
对 \(t\in[\tfrac13,\tfrac12)\) 需用容斥（可能有两段同时 \({>}t\)）：
$$P(L_{\max}>t)=3(1{-}t)^2 - 3P(L_1{>}t,L_2{>}t)$$
其中 \(P(L_1{>}t,L_2{>}t)=P(l_1{>}t,l_2{>}t,l_1{+}l_2{\le}1)\)，可积分得到。
Q 08

最短段的分布与密度

三段（Dirichlet 模型）最短段 \(L_{(1)}\) 的分布？
Answer \(f_{L_{(1)}}(x) = 6(1{-}3x),\; x\in[0,\tfrac13]\)
展开推导 · Full Derivation
S1
\(P(L_{(1)}>x) = P(\text{所有段}{>}x) = P\bigl((l_1,l_2,l_3)\in\{l_i>x,\forall i\}\bigr)\)。
S2
在单纯形上，满足所有段 \(>x\) 的区域是以 \((x,x,x)\) 为角的平移单纯形（边长 \(1{-}3x\)），面积比 \((1{-}3x)^2\)（对 \(x\le\tfrac13\)）。
$$P(L_{(1)}>x) = (1{-}3x)^2,\quad x\in\left[0,\tfrac13\right]$$
S3
密度：\(f_{L_{(1)}}(x) = -\tfrac{d}{dx}(1{-}3x)^2 = 6(1{-}3x)\)，\(x\in[0,\tfrac13]\)。
验证
\(E[L_{(1)}]=\int_0^{1/3}x\cdot6(1{-}3x)dx = 6\left[\tfrac{x^2}{2}-x^3\right]_0^{1/3}=6\left(\tfrac{1}{18}-\tfrac{1}{27}\right)=6\cdot\tfrac{1}{54}=\tfrac{1}{9}\) ✓
Triangle probability geometric proof

Left: Unit square — valid triangle region (dark teal) has area 1/8 out of total 1/2  →  P = 1/4.
Right: 2-Simplex — central similar triangle has similarity ratio 1/2, area ratio 1/4.

Category 05

扩展题 · Extension Problems

🔭 相关拓展问题全解

Extension A · n 段推广

将木棍随机折成 \(n\) 段，能构成凸 \(n\) 边形的概率？

\(n\) 段构成 \(n\) 边形 \(\Leftrightarrow\) 每段 \({<}\tfrac12\)。 每段边缘分布为 \(\mathrm{Beta}(1,n{-}1)\)，\(P(L_i{>}\tfrac12)=(\tfrac12)^{n-1}\)。 当 \(t=\tfrac12\) 时至多一段能超过（因为 \(n\ge3\)，两段超过 \(\tfrac12\) 则和 \({>}1\)），故：

$$P(\text{n-gon}) = 1 - n\cdot\left(\tfrac12\right)^{n-1}$$
\(n=3: 1-3/4=1/4\) ✓  |\;  \(n=4: 1/2\)  |\;  \(n\to\infty: \to1\)
Extension B · 先折再折短段

先随机折，取较短段再折，三角形概率？

较短段 \(X\le\tfrac12\)，长段 \(1{-}X\ge\tfrac12\)。无论如何再折短段，长段 \(1{-}X\ge\tfrac12\) 始终存在， 三角形要求每段 \({<}\tfrac12\)，但长段 \(\ge\tfrac12\)（等号概率为0），故：

\(P(\text{三角形}) = 0\)
Extension C · 圆上三点包含圆心

圆上随机取 3 点，三角形包含圆心的概率？

固定一点为参考，其余两点对应圆弧长度（归一化到1）与 Broken Stick 三段完全等价。 三角形包含圆心 \(\Leftrightarrow\) 三段弧长都 \({<}\tfrac12\)。

\(P = \dfrac{1}{4}\)
Extension D · 条件期望

给定三段构成三角形，最长段的条件期望？

在三角形区域（单纯形中心小三角形）上均匀分布，密度放大4倍为 \(f=4\)（原本为2，三角形区域面积为 \(\tfrac14\)）。 设条件分布均匀在 \(\{l_i{<}\tfrac12,\sum l_i{=}1\}\) 上：

$$E[L_{(3)}\mid\triangle] = \frac{E[L_{(3)}\cdot\mathbf{1}_\triangle]}{P(\triangle)} = \frac{4\cdot E[L_{(3)}\cdot\mathbf{1}_\triangle]}{1} \approx \frac{5}{12}$$
\(E[L_{(3)}\mid\text{三角形}] = \dfrac{5}{12} \approx 0.417\)（远小于无条件期望 \(\tfrac{11}{18}\approx0.611\)）
Extension E · 先折再折，两段均可选

先折一次，然后在任意一段（等概率）上再折，三角形概率？

各以 \(\tfrac12\) 概率选折长段或短段。先折短段概率为 0，折长段概率为 \(2\ln2{-}1\)：

\(P = \tfrac12\cdot 0 + \tfrac12\cdot(2\ln2{-}1) = \ln2-\tfrac12\approx 0.193\)
Extension F · 重复折最长段

不断重复折最长段，\(n\) 次后三角形概率趋势？

每次折最长段，段长趋于均等。三角形概率单调递增趋向1（因为越来越均匀就越难有段超过 \(\tfrac12\)）。 初始（1次折）概率 \(=\tfrac14\)，第一次再折长段后 \(=2\ln2-1\approx0.386\)，继续增大直到趋于1。

三角形概率单调趋向 1
Extension G · 两段 vs 三段最大值期望比较

一次折断最长段期望 \(\tfrac34\)，两次折断最长段期望 \(\tfrac{11}{18}\)，规律是什么？

\(n\) 次折断（共 \(n{+}1\) 段）最长段期望为 \(\tfrac{1}{n+1}\cdot H_{n+1}\)，其中 \(H_n=\sum_{k=1}^n\tfrac1k\)。 随 \(n\) 增大，最长段期望减小（趋向 \(\tfrac{1}{n}\)），验证：\(n=1\)：\(\tfrac12\cdot(1+\tfrac12)=\tfrac34\) ✓. \(n=2\)：\(\tfrac13\cdot(1+\tfrac12+\tfrac13)=\tfrac{11}{18}\) ✓.

\(E[L_{\max}^{(n\text{ breaks})}] = \dfrac{H_{n+1}}{n+1}\)
Quick Reference

速查表 · Cheat Sheet

问题 Problem答案 Answer关键工具 Key Tool
一折：短段期望 \(1/4\) \(\min(X,1-X)\sim U(0,\tfrac12)\)
一折：长段期望 \(3/4\) 互补
一折：两段差期望 \(E|2X-1|\) \(1/2\) 对称积分
两折：三段三角形概率 \(1/4\) 几何 / 容斥 / Dirichlet
两折：最长 \({>}1/2\) 概率 \(3/4\) \(1-1/4\)
两折：最短段期望 \(E[L_{(1)}]\) \(1/9\) Order stat: \(\tfrac13\cdot\tfrac13\)
两折：中间段期望 \(E[L_{(2)}]\) \(5/18\) Order stat: \(\tfrac13(\tfrac12+\tfrac13)\)
两折：最长段期望 \(E[L_{(3)}]\) \(11/18\) Order stat: \(\tfrac13(1+\tfrac12+\tfrac13)\)
最长段 CDF（两折） \(1-3(1{-}t)^2,\;t\in[\tfrac12,1]\) Beta(1,2) 边缘 + 容斥
最短段密度（两折） \(6(1{-}3x),\;x\in[0,\tfrac13]\) 平移单纯形面积
先折再折长段：三角形概率 \(2\ln 2-1\approx0.386\) \(\int_0^{1/2}\frac{X}{1-X}dX\)
\(n\) 段能成 \(n\) 边形概率 \(1-n/2^{n-1}\) 容斥 + Beta(1,n-1)
圆上3点包含圆心概率 \(1/4\) 等价于折木棍三角形
\(n\) 折最长段期望 \(H_{n+1}/(n+1)\) 调和级数
↑ Back to Top