训练营成员的能力值分布

KeyTo9_Fans

某个训练营起初只有 1 个人（能力值为0）。然后新成员一个个地加入进来。

假设所有新成员的能力值都是一个在(0,1)区间均匀分布的独立随机数。

训练营门口由一名已有成员担任守卫，后续新人只有能力值大于营门守卫才能入为成员。

每次有人闯营之后，不论成败，守卫都要在整个营内重新随机选派。


假定一共有n个人闯营

问：当n趋向于无穷大时，

(1) 训练营里的成员个数和 n 呈现什么样的函数关系？

(2) 这些成员的能力值分布有什么规律（是否可以用某个概率密度函数来表示）？

KeyTo9_Fans

写一个简单的matlab程序：



就可以模拟n=1000000的情况。

上述实验重复做了10次，结果大约有13~16万个成员加入了训练营。

以【训练营中成员的能力值】为y，【该成员的能力值是第几小的】为横轴x作图，结果如下：



可见10次实验得到的曲线形状基本上是一样的。

我想知道的是：

(1)若取更大的n，这些曲线最终是否都会稳定下来？

(2)若都能稳定下来，那么能否找到某个函数，准确地拟合稳定后的曲线？

lsr314

有点像气泡水，我愿称之为“气泡分布”。
成员个数有点像素数分布，大致是$c*n/log(n)，c≈2.$

mathe

我们可以先考虑下面一个简化的模型$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$
...

mathe

计算机计算结果:
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
enub.tgz (108.74 KB, 下载次数: 4)

2021-10-21 09:33 上传

点击文件名下载附件

mathe

准确分析很困难，我们看看假设成员分布情况能够达到比较稳定的状态是如何分布的。
假设某个稳定的状态共有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的模拟偏差有点太大了，看来估计的不行

mathe

数值计算结果
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调节速度，内存等开销和精度的关系。
我的机器配置不行，有性能好内存大可以长时间运行的机器可以帮忙运行一下看看能得出多少项
enud2.tgz (1.42 KB, 下载次数: 0)

2021-10-21 17:42 上传

点击文件名下载附件

200次平均人数大概62.97

KeyTo9_Fans

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。

lsr314

有一个现象，当n趋向于无穷大时，这些成员的能力值的平均数是趋向于1的，也就是越来越大，所以即使n趋向于无穷大，能力分布函数也是依赖于n的。

mathe

定义\(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}\)