训练营成员的能力值分布
某个训练营起初只有 1 个人（能力值为0）。然后新成员一个个地加入进来。假设所有新成员的能力值都是一个在(0,1)区间均匀分布的独立随机数。
训练营门口由一名已有成员担任守卫，后续新人只有能力值大于营门守卫才能入为成员。
每次有人闯营之后，不论成败，守卫都要在整个营内重新随机选派。
假定一共有n个人闯营
问：当n趋向于无穷大时，
(1) 训练营里的成员个数和 n 呈现什么样的函数关系？
(2) 这些成员的能力值分布有什么规律（是否可以用某个概率密度函数来表示）？ 写一个简单的matlab程序：
就可以模拟n=1000000的情况。
上述实验重复做了10次，结果大约有13~16万个成员加入了训练营。
以【训练营中成员的能力值】为y，【该成员的能力值是第几小的】为横轴x作图，结果如下：
可见10次实验得到的曲线形状基本上是一样的。
我想知道的是：
(1)若取更大的n，这些曲线最终是否都会稳定下来？
(2)若都能稳定下来，那么能否找到某个函数，准确地拟合稳定后的曲线？ 有点像气泡水，我愿称之为“气泡分布”。
成员个数有点像素数分布，大致是$c*n/log(n)，c≈2.$
我们可以先考虑下面一个简化的模型$A_k$，
$A_{k+1}$会连续尝试随机产生一个体力值为(0,1)上均匀分布的成员，直到产生的成员的体力值大于$A_k$中所有成员（或者说第k个加入的成员）的体力值，然后将他添加到$A_k$中形成$A_{k+1}$。
所以$A_k$的k个成员体力值是依次增加的，假设第h个成员体力值为$e_h$,那么$e_{h+1}$就是$(e_h,1)$之间的均匀分布。
可以证明，$A_k$中最后一个成员$B_k$的体力值期望为$E_k=E(B_k)=1-\frac1{2^k}$。而随机产生一个体力值为(0,1)上均匀分布的成员，它的体力值会大于$A_k$中最后一个成员$B_k$的概率为$p_k=\frac1{2^k}$. 这是因为设$B_k$的概率分布函数为$F_k(x)$, 密度分布函数为$f_k(x)=F'_k(x)$,于是在添加一个均匀分布成员成功的概率为$p_k=\int_0^1 f_k(x) \int_x^1 dydx=\int_0^1 (1-x)f_k(x)dx=1-\int_0^1 xf_k(x)dx = 1- E_k$
于是我们就可以尝试用计算机枚举n次添加以后的成员分布。特别的$p_0=1$
n=1, 只有一个$B_1$成员
n=2, 那么$1/2 *p_0$概率两个$B_1$, $1/2 * (1-p_1)$的概率只有一个$B_1$, $1/2*p_1$的概率一个$B_1$, 一个$B_2$三种情况, 所以$1/4$概率一个成员，$3/4$的概率两个成员
n=3,计算结果是$1/16: B_1$; $7/24: 2B_1$; $1/6: B_1+B_2$ ; $1/6: 3B_1$; $1/4: 2B_1+B_2$; $1/24: B_1+2B_2$; $1/48: B_1+B_2+B_3$
...
计算机计算结果:
Step 2
set{ B1 } 1/4
set{ 2B1 } 1/2
set{ B1 B2 } 1/4
Average members:11/4
Step 3
set{ B1 } 1/16
set{ 2B1 } 7/24
set{ 3B1 } 1/6
set{ B1 B2 } 1/6
set{ B1 2B2 } 1/24
set{ 2B1 B2 } 1/4
set{ B1 B2 B3 } 1/48
Average members:41/12
Step 4
set{ B1 } 1/64
set{ 2B1 } 37/288
set{ 3B1 } 23/144
set{ 4B1 } 1/24
set{ B1 B2 } 49/576
set{ B1 2B2 } 7/144
set{ B1 3B2 } 1/192
set{ 2B1 B2 } 151/576
set{ 2B1 2B2 } 7/96
set{ 3B1 B2 } 1/8
set{ B1 B2 B3 } 115/4608
set{ B1 B2 2B3 } 1/768
set{ B1 2B2 B3 } 1/128
set{ 2B1 B2 B3 } 1/48
set{ B1 B2 B3 B4 } 1/1536
Average members:6191/1536
Step 5
Average members:10190881/2211840
Step 6
Average members:182474969/35389440
Step 7
Average members:20271707449003/3567255552000
Step 8
Average members:1583033001386661119/255700877967360000
Step 9
Average members:551271389495989946205329/82478875197151641600000
Step 10
Average members:4235051544636225280407516211/591208577413182966988800000
Step 11
Average members:80042140036759368619109170585941991/10488513130171796380754903040000000
Step 12
Average members:66897680622096097560468020490111023479993/8269982832877858010297625948979200000000
Step 13
Average members:78165083904260613969625565563984532444987348235521/9155085353950817011479098839984571940864000000000
Step 14
Average members:40442010092611893918642467937486326340378480297621323881/4504407460727079483059688868491046017173846753280000000
Step 15
Average members:11732311755663160869471611766306991420305900205794651870432134683961/1246623953316564758411819121138764807231053375497201254400000000000
Step 16
Average members:193081092776582967118257601559297628629384473763196402565136335123829277154039/19627307076470146174868221176209529719304241999344279837544022016000000000000
Step 17
Average members:242479625583075319335894637059626249011255099328165393739854233249519372989274849280980649/23639996188715638826883555087876238384304770842038693972877348205885768335360000000000000
Step 18
Average members:750223733698131892176036737352457425110892332690335106777493016797031787486373453278028396165485131/70303842765963093766670901913040095121368990424580743554479569313387095831403319787520000000000000
Step 19
Average members:802160979314014123222996622922653041379174336090773128095724748702029016859979722297878892386863022803662232594419/72398882644591050016933604919513666420829216048733918315523531902212875281704238212310105289916416000000000000000
Step 20
Average members:2113954779084423181662459030945303610426463345363758730627818778283256590554021586864738325721058092511782151837032896488397079/184089763643107144352071868298495922024075215140485568959846926819413250340603502879195058714587787719092469760000000000000000
Step 21
Average members:50056833586831426715883032095157736155213416813035569152047145956113092004680515006458619354615487605819532914832751756605364509459948588721/4212791117244711418725172988332249235870009029273622469792822391841475943927968043520673886127967480826832182852287096422400000000000000000
Step 22
Average members:6575252033599677583677802703792828086774095183908459675092478685971858306764206253625637296285092293592882928770023328296625251999729524301537564937817/535596471052236946159624168186792307466908046211875643510289090817829710050868230252882103979692325523963456463706529809005137834803200000000000000000
Step 23
Average members:571334438566488806464110681410106862886890307418057099222999564003168649729190007400415512933240557383557778118306788269072785730689327916353623770508070660398541085601/45105116767856430348724309504845948238448432859033095416599665870725709600806167340559437361786098803038218155394599596819053696466036392823346954240000000000000000000
准确分析很困难，我们看看假设成员分布情况能够达到比较稳定的状态是如何分布的。
假设某个稳定的状态共有K个成员（不包含初始成员），其中在状态$B_1,B_2,...,B_s,...$的期望比例分别为$c_1,c_2,...,c_s,...$
那么$B_h$状态的成员数目为$Kc_h$. 而且$c_1+c_2+...+c_s+...=1$
那么在下一轮尝试添加新成员时，有${Kc_h}/{K+1}$的概率选择某个$B_h$,然后再有$1/{2^h}$的概率会添加一个$B_{h+1}$的成员
同样还有$1/{K+1}$的概率添加一个$B_1$的成员，所以一次选择以后，状态在$B_1$的期望数目改变为$Kc_1+1/{K+1}$,
而状态在$B_h (h\ge 2)$的期望数目为$Kc_h+{Kc_{h-1}}/{(K+1)2^{h-1}}$.
容易看出在总人数K比较大时，成功添加成员的概率是极其低的，所以这是总人数K的变化期望会很小，假设变化为某个K'(数目看成是一个浮点数)
由于在稳定状态而且总人数几乎没有变化，那么我们可以认为各状态比例分布还是保持不变，那么应该有
$Kc_1+1/{K+1}=K'c_1, Kc_h+{Kc_{h-1}}/{(K+1)2^{h-1}}=K'c_h (h\ge 2)$
于是有第一个等式得出$K'=K+1/{c_1(K+1)}$,代入二式得出
${Kc_1}/{2^{h-1}}={c_h}/{c_{h-1}} (h\ge 2)$
于是容易计算得出
$c_1={K^0c_1}/{2^0}$
$c_2={Kc_1^2}/{2^1}$
$c_3={K^2c_1^3}/{2^3}$
$c_4={K^3c_1^4}/{2^6}$
$c_5={K^4c_1^5}/{2^10}$
...
$c_h={K^{h-1}c_1^h}/{2^{h(h-1)/2}}$
...
记$u=Kc_1$,我们得出
$Kc_1=u/{2^0}$
$Kc_2={u^2}/{2^1}$
...
$Kc_h={u^h}/{2^{h(h-1)/2}}$
设$F(x)=\sum_{t=1}^{\infty} {x^t}/{2^{{t(t-1)}/2}}$
于是我们得出$F(u)=K$,也就是$u=F^{-1}(K),c_1=\frac{F^{-1}(K)}{K}$
记$F(u_K)=K$, 计算可以得到
F(0.70429643015170568664151521240409450461)=1
F(1.1387784488450301441459504592076374742)=2
F(1.4621283383436886192212050014374301136)=3
F(1.7229731325984890107677515060272406560)=4
F(1.9432105872246036715124959593628235694)=5
F(2.1347223444048168272325390684981579656)=6
F(2.3047295987848467065035072659250728822)=7
F(2.4579726676867964690054944460553130469)=8
F(2.5977426130652592171857543827813782292)=9
F(2.7264239229633503813947177417366894745)=10
F(2.8458033238518945583112998642123668052)=11
F(2.9572565575821784706132662264621824797)=12
....
另外我们知道，在初始有$Kc_h$个$B_h$成员时，一次选择会有$1/{K+1}(1+\sum_{h=1}^{\infty}{Kc_h}/{2^h})$的概率添加一个成员
所以在上面的模型下，一次选择会有
$1/{K+1}(1+\sum_{h=1}^{\infty}{u_K^h}/{2^{h(h+1)/2}})$
的概率添加一个成员
上面结果即$ {F(u_K)}/{(K+1)u_K}={K}/{(K+1)u_K}$
所以平均需要${(K+1)u_K}/K$次变成K+1个成员。
所以平均来说，增加到K个成员应该近似需要$\sum_{h=1}^{K-1} {(h+1)u_h}/h$次,
但是这样计算下来44218个成员就需要1000000左右次，和Fans的模拟偏差有点太大了，看来估计的不行
数值计算结果
2 2.75
3 3.416667
4 4.030599
5 4.607422
6 5.156198
7 5.682718
8 6.190956
9 6.683789
10 7.16338
11 7.63141
12 8.089216
13 8.537887
14 8.97832
15 9.411268
16 9.837371
17 10.257177
18 10.671163
19 11.079743
20 11.483283
21 11.882107
22 12.276504
23 12.666732
24 13.053026
25 13.435595
26 13.814632
27 14.190311
28 14.562792
29 14.932223
30 15.298738
31 15.662463
32 16.023513
33 16.381997
34 16.738013
35 17.091656
36 17.443013
37 17.792164
38 18.139188
39 18.484155
40 18.827134
41 19.168189
42 19.507379
43 19.844762
44 20.180392
45 20.51432
46 20.846594
47 21.177261
48 21.506365
49 21.833947
50 22.160047
51 22.484703
52 22.807952
53 23.129828
54 23.450365
55 23.769594
56 24.087546
57 24.40425
58 24.719734
59 25.034024
60 25.347148
61 25.65913
62 25.969993
63 26.279761
64 26.588456
65 26.8961
66 27.202714
67 27.508316
68 27.812927
69 28.116565
70 28.419249
71 28.720995
72 29.021821
73 29.321743
74 29.620776
75 29.918936
76 30.216239
77 30.512698
78 30.808327
79 31.10314
80 31.39715
81 31.69037
82 31.982813
83 32.27449
84 32.565414
85 32.855595
86 33.145045
87 33.433775
88 33.721795
89 34.009115
90 34.295746
91 34.581698
92 34.866979
93 35.1516
94 35.435569
95 35.718895
96 36.001586
97 36.283652
98 36.5651
99 36.845938
100 37.126174
对应的c++代码，会把概率太小的模式抛弃，所以输出结果会有三列，最后一列代表抛弃的误差。可以增加变量MINV调节速度，内存等开销和精度的关系。
我的机器配置不行，有性能好内存大可以长时间运行的机器可以帮忙运行一下看看能得出多少项
200次平均人数大概62.97 mathe 发表于 2021-10-20 22:06
计算机计算结果:
Step 2
set{ B1 } 1/4
这个平均值偏小，和我模拟的数据对不上。
我猜测，可能是过度合并的缘故。
比如，
set { B1(B2) B1(B2) } 和 set { B1(2B2) B1 }
是不能合并成
set { 2B1 2B2 }
的，前者表示两个 B2 来自不同的 B1，后者表示两个 B2 来自同一个 B1。 有一个现象，当n趋向于无穷大时，这些成员的能力值的平均数是趋向于1的，也就是越来越大，所以即使n趋向于无穷大，能力分布函数也是依赖于n的。 定义\(H_u(x)=\begin{cases}\frac1{1-u}&,u\le x\le 1\\0&,otherwise \end{cases}\)
\(U_u(x)=(1-u)H_u(x)=\begin{cases}1&,u\le x\le 1\\0&,otherwise \end{cases}\)
于是在给定前k个成员（不包含初始成员）的体力值$x_h$的前提下，(并且记$x_0=0$)
第k+1个人的体力值分布的密度函数为\(f_{k+1}(x_1,x_2,...,x_k,x_{k+1})=\frac{\sum_{h=0}^k (1-x_h) H_{x_h}(x_{k+1})}{\sum_{h=0}^k (1-x_h)}=\frac{\sum_{h=0}^k U_{x_h}(x_{k+1})}{\sum_{h=0}^k (1-x_h)}\)
于是k个成员的联合密度分布为\(\prod_{h=1}^k f_h(x_1,x_2,...,x_h)\)
添加第k+1个成员平均需要\(\frac{k+1}{k+1-x_1-...-x_k}\)多次，所以达到k个成员需要的次数n的期望值为
\(\int_0^1\int_0^1...\int_0^1\left(\sum_{h=1}^k \frac{h}{h-x_1-...-x_{h-1}}\right)\left(\prod_{h=1}^k f_h(x_1,x_2,...,x_h)\right)dx_1dx_2...dx_k\)
即
\(\sum_{h=1}^k\int_0^1\int_0^1...\int_0^1 \frac{h}{h-x_1-...-x_{h-1}} \left(\prod_{t=1}^{h-1} f_h(x_1,x_2,...,x_t)\right)dx_1dx_2...dx_{h-1}\)