从 \(0,1,··· ,2^n −1\) 中随机取一个数, 取完后放回. 独立重复这个过程 k 次, 事件 \(A_m\):“此 k 个数中最大的数是 m”的概率\(P_m\)。(\(m≤2^n-1\))

• 设\(P_A\)为k次试验取得的数均小于等于m的概率，显然\(P_A\)中包含k次试验均取出小于m值的事件，则\(P_A = (\frac{m+1}{2^n})^k\)

  设\(P_B\)为k次试验取得的数均小于m的概率，则\(P_B = (\frac{m}{2^n})^k\)

  则\(P_m = P_A -P_B = (\frac{m+1}{2^n})^k-(\frac{m}{2^n})^k = \frac{(m+1)^k-m^k}{(2^n)^k}\)

• 1）取n=3，k=3

  则P(0) = 1/512，P(1) = 7/512，P(2) = 19/512，

  P(3) = 37/512，P(4) = 61/512，P(5) = 91/512，

  P(6) = 127/512，P(7) = 169/512

  2）将试验结果分为以下四类：

  \(e_1\):取出来的数小于等于4 ，\(P_1 = \frac{125}{512}\)

  \(e_2\):取出来的数最大为5，\(P_2 = \frac{91}{512}\)

  \(e_3\):取出来的数最大为6，\(P_3 = \frac{127}{512}\)

  \(e_4\):取出来的数最大为7，\(P_4 = \frac{169}{512}\)

  3） 算法如下：

  独立重复n次试验后可得\(e_1,e_2,e_3,e_4\)出现的次数为$ η_1,η_2,η_3,η_4$

  四项分布理论$ ξ = \sum_{i=1}^{4}{\frac{(η_i-nP_i)^2}{nP_i}}$ ~ $ χ^2(3)$

  则观察值为$ ξ_{obs}= \sum_{i=1}^{4}{\frac{(η_i-nP_i)^2}{nP_i}}$

  \(P_{val} = Q(\frac{3}{2},\frac{ξ_{obs}}{2})\)

  4）举例该算法检验过程如下:

  例如100010111101001010分为两组，一组为100（4）010（2）111（7），另一组为101（5）001（1）010（2）

  第一组属于\(e_4\)，第一组属于\(e_2\)，即对于这一组数据来说，\(，e_1，e_3\)出现了0次，\(，e_2，e_4\)

  出现了1次。

  则观察值$ ξ_{obs}=2P_1 + 2P_3 + \frac{(1-2P_2)^2}{2P_2} + \frac{(1-2P_4)^2}{2P_4} = 2.328$

  借助MATLAB平台算出P值为0.7232