我正在试验一个程序:变量 X 的初始值是0,现在对其进行累加,每次累加有 50% 的概率加 1,另 50% 的概率加 2。当 X 的值大于或等于 100 时终止累加。
问:当累加终止时,累加执行次数的期望值是多少?

显然,累加终止时,变量 X 的值等于100或101。

我一开始认为,当累加终止时,假设累加执行次数为 n,应该有:
n * 0.5 + 2 * n * 0.5=100

n * 0.5 + 2 * n * 0.5=101
解得:n=200/3 或 n=202/3
此时,我认为获得两个解的概率是相等的,得到 n=201/3=67。

这个答案是错误的。
我尝试用 SAS 进行模拟,发现在1百万次累加测试中,约 66.67%次的累加终止时,X 的值为100,而另外 33.33% 次 X 的值为 101,也就是说,程序模拟的结果表明累加执行次数的期望值为 66.67%*200/3 + 33.33%*202/3 ≈ 66.89。请问为什么终止累加时,X 的值为 100 的概率是 101 的两倍?

我不会 R,这是我使用的 SAS 程序,供大家参考:

data test;
  do i=1 to 1e6;      *1百万次测试;
    x=0;
    do while(x<100);
      x+1+(rand('normal')<=0);    *累加1或2;
    end;
  end;
run;

因为求和出现100之后,你就终止了。但是实际上求和100之后,下一次如果抽到1,求和就是101了。
所以这个累加的序列中,出现100和出现101的概率应该差不多,这个可以从转移概率矩阵里算出来。用pnp_n表示这样一个求和序列里“出现过”n的概率,则1pn1-p_n表示这个求和序列里“从未出现过”n的概率。显然,累计的求和序列里出现过n,要么说明上一个累计和是n-1同时本次抽到了1,要么上一个累计和是$n-2$,同时本次抽到了2。累计求和序列里从未出现过n,则说明上一个累计和是n-1同时本次抽到了2。所以可以写出转移概率
(pn+11pn+1)=(0.510.50)(pn1pn)\begin{pmatrix}p_{n+1} \\ 1 - p_{n+1}\end{pmatrix}=\begin{pmatrix}0.5 & 1 \\ 0.5 & 0\end{pmatrix}\begin{pmatrix}p_{n} \\ 1 - p_{n}\end{pmatrix}
可以解出稳态的概率是(2/3,1/3)(2/3,1/3)。这里利用了一个事实:如果这个累计求和序列中没有出现n-1,则必然会出现n。

所以,对于“首次出现”而言,100的概率大概是2/3,101的概率大概是1/3。但还是提一下,这个仅仅是近似的概率,因为上述的稳态概率是在这个n(当前例子里是100)趋向于无穷的情况下得到的。不过从模拟结果来看,100的时候已经很接近了。

    fenguoerbian

    有意思,好奇问一下,如果把原题目的“随机加1或2”改成 “随机加1或者3”, 这个转移矩阵应该怎么处理,稳态会怎么分布…

    想了一下,没法利用 “如果这个累计求和序列中没有出现n-1,则必然会出现n”的条件一下给我整不会了

      tctcab
      说实话昨天我也不知道,所以没有往下写……今天的话,不妨考虑(1,2), (3, 4), (5, 6), .....这样的数组的出现情况和转移。用p1,np_{1, n} 表示n出现、n-1出现,p2,np_{2, n}表示n出现、n-1不出现,p3,np_{3, n}表示n不出现、n-1出现,p4,np_{4, n}表示n不出现、n-1不出现。那么就有

      (p1,n+2p2,n+2p3,n+2p4,n+2)=(0.250.2500.500100.250.2500.50.50.500)(p1,np2,np3,np4,n)\begin{pmatrix}p_{1, n+2} \\ p_{2, n+2} \\ p_{3, n+2} \\ p_{4, n+2}\end{pmatrix} =\begin{pmatrix}0.25 & 0.25 & 0 & 0.5 \\0 & 0 & 1 & 0 \\0.25 & 0.25 & 0 & 0.5 \\0.5 & 0.5 & 0 & 0\end{pmatrix} \begin{pmatrix}p_{1, n} \\ p_{2, n} \\ p_{3, n} \\ p_{4, n}\end{pmatrix}

      解出来的稳态下每个数出现的概率渐进到0.5。

      不过说实话,不如直接跑个模拟看看出现概率大概是收敛到哪里。通过模拟我大胆猜测,如果是每次等概率随机抽到1或者m的话,那么累计求和序列中,每个数出现的概率会收敛到21+m\frac{2}{1 + m}

        fenguoerbian

        我的模拟也观察到 pn>21+mp_{n}->\frac{2}{1+m} 这个收敛。

        以随机加1或者5为条件,生成累加次数100次的累加队列,模拟一万次, 统计各数出现频率,可以观察到30以下波动挺大,30~250收敛到~ 1/3

        000014.png

        为了深入理解稳态观察到N的概率为什么是 pn>21+mp_{n}->\frac{2}{1+m}, 尝试将只有数字91的队列提出来统计<91的数字的分布,可以看到漂亮的波形如下:

        000010.png

        emmm 感觉这个网络概率比较复杂,稳态分布还是难推

        今天盘通了为什么收敛到 Pn=21+mP_{n}=\frac{2}{1+m}

        假设有随机加 (1, m) 生成的累加数列,设 PnP_{n} 为 数列中出现数字n 的概率, 那么有:

        数列中不包含n的概率记为 1Pn1-P_{n},当且仅当n前面的m-1个数字加了m,直接跳过了n,一共m-1种情况。

        所以有 1Pn=12(Pnm+1+Pnm+2+...+Pn1)1-P_{n}=\frac{1}{2}(P_{n-m+1}+P_{n-m+2}+...+P_{n-1})

        当稳态时有

        P=Pn=Pn1=...=Pnm+1P=P_{n}=P_{n-1}=...=P_{n-m+1}

        则有

        1P=(m1)P121-P=(m-1)P*\frac{1}{2}

        解得 P=2m+1P=\frac{2}{m+1}

          tctcab

          是不是就差一步,说明一下稳态时数列中不包含n的概率其实对于不同的n而言是一样的,而不是类似于如果n是奇数则是p1,否则是p2。这样才有

          p=pn=pn1==pnm+1p = p_n = p_{n - 1} = \cdots = p_{n-m+1}

          这个可能是因为抽取的数字是1或者m,当中有可能抽到1吧。因为如果考虑抽取的是2或者4,那么其实就是奇数永远不会出现,偶数出现的概率稳定到2 /3.