变量随机加1或加2

whymath

我正在试验一个程序：变量 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 的两倍？

whymath

我不会 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;

fenguoerbian

因为求和出现100之后，你就终止了。但是实际上求和100之后，下一次如果抽到1，求和就是101了。
所以这个累加的序列中，出现100和出现101的概率应该差不多，这个可以从转移概率矩阵里算出来。用 $$p_n$$ 表示这样一个求和序列里“出现过”n的概率，则 $$1-p_n$$ 表示这个求和序列里“从未出现过”n的概率。显然，累计的求和序列里出现过n，要么说明上一个累计和是n-1同时本次抽到了1，要么上一个累计和是$n-2$，同时本次抽到了2。累计求和序列里从未出现过n，则说明上一个累计和是n-1同时本次抽到了2。所以可以写出转移概率
$\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)$$ 。这里利用了一个事实：如果这个累计求和序列中没有出现n-1，则必然会出现n。

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

tctcab

fenguoerbian

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

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

whymath

fenguoerbian 太给力了，谢谢

fenguoerbian

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

$\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的话，那么累计求和序列中，每个数出现的概率会收敛到 $\frac{2}{1 + m}$ 。

tctcab

fenguoerbian

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

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

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

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

tctcab

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

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

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

所以有 $1-P_{n}=\frac{1}{2}(P_{n-m+1}+P_{n-m+2}+...+P_{n-1})$

当稳态时有

$P=P_{n}=P_{n-1}=...=P_{n-m+1}$

则有

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

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

fenguoerbian

tctcab

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

$p = p_n = p_{n - 1} = \cdots = p_{n-m+1}$

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