Initialization: 首先当
m
=
0
,
n
=
n
0
m=0,n=n_0
m=0,n=n0时，我们有
∅
\varnothing
∅以概率
1
/
C
n
0
0
=
1
1/C_{n_0}^0=1
1/Cn00=1的概率成为
(
1
,
⋯
,
n
0
)
(1,\cdots,n_0)
(1,⋯,n0)的一个子集。
Maintenance: 接下来，每次迭代开始前我们假定有每种
(
1
,
⋯
,
n
)
(1,\cdots,n)
(1,⋯,n)的m-子集S都以为概率
1
/
C
n
m
1/C_{n}^m
1/Cnm出现。新的子集可以看作原来的子集新添一个元素。令新子集包含数n+1的事件为B，出现一种包括数n+1的新子集的事件为
X
i
X_i
Xi，取出的随机数
i
∈
S
i \in S
i∈S的事件为C。如果C发生，那么B肯定发生：
P
(
C
)
=
m
n
+
1
P
(
C
‾
)
=
1
−
m
n
+
1
P
(
B
C
)
=
P
(
B
∣
C
)
⋅
P
(
C
)
=
1
⋅
m
n
+
1
=
m
n
+
1
P(C) = \frac {m}{n+1} \qquad P(\overline{C}) = 1-\frac {m}{n+1} \\ P(BC) = P(B|C) \cdot P(C) = 1 \cdot \frac m{n+1} = \frac m {n+1}
P(C)=n+1mP(C)=1−n+1mP(BC)=P(B∣C)⋅P(C)=1⋅n+1m=n+1m 如果C不发生，那么数n+1有可能从剩下的n-m+1个数中选出，概率为：
P
(
B
C
‾
)
=
P
(
B
∣
C
‾
)
⋅
P
(
C
‾
)
=
1
n
−
m
+
1
⋅
(
1
−
m
n
+
1
)
=
1
n
+
1
P(B \overline{C}) = P(B|\overline{C}) \cdot P(\overline{C}) = \frac {1}{n-m+1} \cdot (1-\frac {m}{n+1})=\frac {1}{n+1}
P(BC)=P(B∣C)⋅P(C)=n−m+11⋅(1−n+1m)=n+11 这样就可知B的概率：
P
(
B
)
=
P
(
B
C
)
+
P
(
B
C
‾
)
=
m
+
1
n
+
1
P(B) = P(BC) + P(B \overline{C}) = \frac {m+1} {n+1}
P(B)=P(BC)+P(BC)=n+1m+1 由于新的集合包含了之前的子集S，所以：
P
(
X
i
∣
B
)
=
1
C
n
m
P
(
X
i
B
)
=
P
(
X
i
∣
B
)
⋅
P
(
B
)
=
m
!
(
n
−
m
)
!
(
m
+
1
)
n
!
(
n
+
1
)
=
(
m
+
1
)
!
(
n
+
1
−
m
−
1
)
!
(
n
+
1
)
!
=
1
C
n
+
1
m
+
1
P(X_i|B) = \frac {1}{C_{n}^m} \\ P(X_iB) = P(X_i|B) \cdot P(B) = \frac {m!(n-m)!(m+1)}{n!(n+1)} = \frac {(m+1)!(n+1-m-1)!}{(n+1)!} = \frac {1}{C_{n+1}^{m+1}}
P(Xi∣B)=Cnm1P(XiB)=P(Xi∣B)⋅P(B)=n!(n+1)m!(n−m)!(m+1)=(n+1)!(m+1)!(n+1−m−1)!=Cn+1m+11
P
(
X
i
)
=
P
(
X
i
B
)
+
P
(
X
i
B
‾
)
=
1
C
n
+
1
m
+
1
+
0
=
1
C
n
+
1
m
+
1
P(X_i) = P(X_iB) + P(X_i\overline{B}) = \frac 1{C_{n+1}^{m+1}} + 0 = \frac 1{C_{n+1}^{m+1}}
P(Xi)=P(XiB)+P(XiB)=Cn+1m+11+0=Cn+1m+11 可知当新的集合包含数n+1时，每种可能都以相同概率出现。如果取出的随机数
i
∉
S
i \not \in S
i∈S，增加的一个数能从剩下的n-m个数中取出，令出现不包括数n+1的新子集的事件为
Y
i
Y_i
Yi这时：
P
(
Y
i
∣
B
‾
)
=
1
C
n
m
⋅
1
n
−
m
P(Y_i|\overline{B}) = \frac {1}{C_n^m} \cdot \frac {1}{n-m}
P(Yi∣B)=Cnm1⋅n−m1 于是可以算出每种子集出现的概率： KaTeX parse error: Undefined control sequence: \eqalign at position 1: \̲e̲q̲a̲l̲i̲g̲n̲ ̲{P(Y_i\overline…
P
(
Y
i
)
=
P
(
Y
i
B
)
+
P
(
Y
i
B
‾
)
=
0
+
1
C
n
+
1
m
+
1
=
1
C
n
+
1
m
+
1
P(Y_i) = P(Y_iB) + P(Y_i\overline{B}) = 0 + \frac 1{C_{n+1}^{m+1}} = \frac 1{C_{n+1}^{m+1}}
P(Yi)=P(YiB)+P(YiB)=0+Cn+1m+11=Cn+1m+11 由于当新子集包含和不包含数n+1时每种情况出现的概率都相同为
1
/
C
n
+
1
m
+
1
1/C_{n+1}^{m+1}
1/Cn+1m+1，当m和n增1之后满足了下一次迭代的前提。
Termination: 最后当迭代结束时，得到的m-子集的每种可能都以
1
/
C
n
m
1/C_n^m
1/Cnm的概率出现。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
