首页 > 技术相关 > 随机把绳子剪开,最短一段会有多长?

随机把绳子剪开,最短一段会有多长?

2012年11月20日 发表评论 阅读评论

这是个很经典的题目哈,把一根一米长的绳子随机剪成几段,最短一段的期望应该是多少呢?



比方说先来看看剪成三段的情况?这三段不管怎么分,加起来都是同一根绳子(废话)——那有什么好办法来表示这几段呢?

这三段正好可以表示成正三角形形中一点到各边的距离。由于各边等长,面积守恒,所以这一点不管搁在哪里,这三段加起来都是一样长的。不同的剪法无非是这一点在三角形中不同的位置。把中心和各个顶点连接起来,落在哪个小三角里,距离哪个边就最近,也就是最短的一段咯。很显然落在每个小三角里的概率是一样的。那我们只需要算,在一个小三角里面,这个距离的期望是多少呢?

三角形的高度 \(h\) 就是 \(1/3\),那么距离 \(x\) 的期望

\[ \begin{aligned} \mathbb{E}(X) =&\displaystyle \int_0^h x \cdot \frac{2(h-x)\cot \alpha \, {\rm d}x}{h\cdot h\cot \alpha} \\ =&\displaystyle \left.\left(\frac{x^2}{h}-\frac{2x^3}{3h^2}\right)\right|_0^h=\frac{1}{3}h=\frac{1}{9}\end{aligned}. \]

那多边形是不是也可以如法炮制呢?结果是不是就是 \(\frac{1}{3n}\) 了呢?很不幸不是的……因为这种做法相当于给这几条边加了额外的限制条件。比方说下面这个五边形,四段很短,一段很长情况就没有包含在内。

好吧我们还是来用一个正常一点的思路吧……假设我们把一根绳子剪成 \(n\) 段,每段的长度分别是 \(l_1, l_2, \ldots, l_n\)。设最短的一段是 \(x\)。那其他的 \(n-1\) 段都要大于等于 \(x\)。换句话说,每一段都得预留出了 \(x\) 的长度,只能落在余下的 \(1-nx\) 里。也就是说

\[ {\rm P}(L_{\min} \ge x) = {\rm P}(L_1 \ge x, L_2 \ge x, \ldots L_n \ge x) = (1-nx)^{n-1} \]

这样就可以得出

\[ \begin{aligned} \mathbb{E}(L_\min) &= \displaystyle \int_0^{1/n}x \, {\rm dP}(L_\min \le x) \\ &= x{\rm P}(L_\min \le x)\Big|_0^{1/n} – \int_0^{1/n} \big[1-{\rm P}(L_\min \ge x) \big]{\rm d} x \\
&= \int_0^{1/n} {\rm P}(L_\min \ge x) {\rm d} x = \int_0^{1/n} (1-nx)^{n-1} {\rm d} x = \frac{1}{n^2}. \end{aligned}\]

这就是最短的那一段的平均长度:\(1/n^2\)。那可能又要问了,其他的几段呢?我们来算算倒数第二段先。和上面的做法一样,先把最短的一段从每一段中截走,绳子的总长度剩下 \(1-nx\)。那倒数第二段就是剩下里面最短的一段啦,再把刚才的那一段加回去,于是长度就是

\[ \displaystyle \frac{1-n\cdot \mathbb{E}(L_\min)}{(n-1)^2} + \mathbb{E}(L_\min) = \frac{1-\frac{1}{n}}{(n-1)^2}+\frac{1}{n^2} = \frac{1}{n}\left(\frac{1}{n}+\frac{1}{n-1}\right) \]

最后,加上一点数学归纳法,就可以得到第 \(k\) 长的一段的期望是

\[ \displaystyle \frac{1}{n}\left(\frac{1}{n}+\frac{1}{n-1} + \cdots + \frac{1}{n-k+1}\right) \]

比方说切三段,那三段的期望就分别是 \(\displaystyle \frac{1}{9}, \frac{5}{18}, \frac{11}{18}\),这个差异很大哦~

分类: 技术相关 标签:
  1. 2012年12月28日15:27 | #1

    亲爱的犊犊,

    你貌似没有定义“随机剪开”。
    是不是这么说:在[0,1)取n-1个值,x_1, x_2, …, x_{n-1}。
    其中每个x都是均匀分布的随机数。
    然后这n-1个点把[0,1)分成的n段就是你说的随机的n段?
    我想这并不是不言自明的。

    另外,在n=3的情况下,确实每个特定的L1+L2+L3=1都可以对应于在三角形中的一个点到三边的距离,但为什么说这随机获取的三段长度就会对应于一个在三角形内的均匀随机分布的点呢?对应的点的分布的均匀性是怎么推出来的?

    我是被你在Chinese板的坎昆休假贴勾引过来的。你的画风还是那么可爱。
    祝好!
    ajax

    • 犊犊
      2012年12月28日16:19 | #2

      谢谢… 貌似这个地方确实是欠严谨…

  2. 大沈
    2018年11月12日18:10 | #3

    题目等价于:n个数加在一起等于1,求其中最小值的期望。
    以三个数为例,a+b+c=1, a<b<c 。
    则3a, 2b-2a, c-b是三个没有限制的和为1的正实数,所以3a期望均为1/3。
    那么a的期望是1/9。

  1. 2013年7月23日12:27 | #1
  2. 2013年8月18日20:21 | #2

%d 博主赞过: