j*****y
发帖数: 22 | 1 given a circle, make n random cuts, what is expected length of longest piece?
不知如何下手，多谢 |
m**********l
发帖数: 28 | 2 我猜是 (3/4)^(n-1)*周长，
可以这样想，这个问题等价于在[0,1]上随机选择 n-1 个点， 最长区间的期望是多少
。在圆上选择两个点相当于在[0,1]上选一个点，第一个圆上的点相当于确定端点。所
以圆上n个点相当于[0,1]上n-1个。
然后先考虑[0,1]上随机选一个点，最长区间的期望。这个很容易求是3/4 .
n个的时候用递推， 要想区间尽量长，那么第n个点落在最长的区间上将其分割的最长
为3/4比例，所以是 (3/4)^n
如果要严格写出来肯定是用条件概率， |
j*****y
发帖数: 22 | 3 thanks.
第n个点也可能落在非最长分割上。如果这个点落在最长分割上那么原来的第二长分割
可能变成最长。所以我想应该比(3/4)^(n-1)大，但不知道到底是多少。
【在 m**********l 的大作中提到】
: 我猜是 (3/4)^(n-1)*周长，
: 可以这样想，这个问题等价于在[0,1]上随机选择 n-1 个点， 最长区间的期望是多少
: 。在圆上选择两个点相当于在[0,1]上选一个点，第一个圆上的点相当于确定端点。所
: 以圆上n个点相当于[0,1]上n-1个。
: 然后先考虑[0,1]上随机选一个点，最长区间的期望。这个很容易求是3/4 .
: n个的时候用递推， 要想区间尽量长，那么第n个点落在最长的区间上将其分割的最长
: 为3/4比例，所以是 (3/4)^n
: 如果要严格写出来肯定是用条件概率，
|
s**e
发帖数: 1834 | 4 It must be bigger than (3/4)^(n-1), because (3/4)^(n-1) < 1/n for big n.
【在 j*****y 的大作中提到】
: thanks.
: 第n个点也可能落在非最长分割上。如果这个点落在最长分割上那么原来的第二长分割
: 可能变成最长。所以我想应该比(3/4)^(n-1)大，但不知道到底是多少。
|
m**********l
发帖数: 28 | |
w**k
发帖数: 112 | 6 L*( n + 1)/(2n)
L是圆的周长
最长段是在[L/n, L]的均匀分布 |
j*****y
发帖数: 22 | 7 最长段是L/n和L的概率密度应该为0，因为唯一的可能是另外n-2个点重叠在一点。但是
如果最长段在L/n和L之间是概率密度大于0。看似不能是均匀分布。其实只要是对称分
布在[L/n, L]就可以了，但是不知道怎么证明它是对称分布。
【在 w**k 的大作中提到】
: L*( n + 1)/(2n)
: L是圆的周长
: 最长段是在[L/n, L]的均匀分布
|
l******e
发帖数: 470 | 8 我印象中是\Omega(logn/n)
前面的常数不好求
以前写过个note，现在怎么也找不到了。
大致想法好象是证 对比较大的常数C(e.g. 1000)
Pr(there exists a piece of length Clogn/n which was not cut) -> 0
对比较小的常数c(e.g. 0.001)
Pr(there is a piece of length clogn/n which was not cut)->1
piece?
【在 j*****y 的大作中提到】
: given a circle, make n random cuts, what is expected length of longest piece?
: 不知如何下手，多谢
|
l******e
发帖数: 470 | 9 看下an introdution to geometric probability, Chapter 2.
里面给了largest piece的分布的公式。推倒挺复杂的。
【在 l******e 的大作中提到】
: 我印象中是\Omega(logn/n)
: 前面的常数不好求
: 以前写过个note，现在怎么也找不到了。
: 大致想法好象是证 对比较大的常数C(e.g. 1000)
: Pr(there exists a piece of length Clogn/n which was not cut) -> 0
: 对比较小的常数c(e.g. 0.001)
: Pr(there is a piece of length clogn/n which was not cut)->1
:
: piece?
|
