今年的面试题中，涉及到随机过程(Stochastic Process)和马尔可夫链(Markov Chain)的题目很多也大多属于相对较难和较有意思的一类。下面从一条题目引开来:
Morgan Stanley的口算题：
抛硬币，第一次遇到连续两次正面朝上的时候停下来，问：抛的次数的期望N
解：
假设期望N次后终止，
那么第一次如果抛出反面(T)那么就回到了前面的情况，即N+1，这个$latex P_1$是1/2
如果前两次抛出了正反(HT)那么又回到开始的情况，即N+2，这个$latex P_{2_1}$是1/4
如果前两次抛出了正正(HH)那么就已经停止了，即2，这个$latex P_{2_2}$也是1/4
那么综合上述：
$latex N=\frac{(N+1)}{2}+\frac{(N+2)}{4}+\frac{2}{4}$
解上面的方程得到：N=6，那么这个问题就解决了。
很容易想到的一个推广：
SinRain的笔算题：
抛硬币，第一次遇到连续n次正面朝上的时候停下来，问：抛的次数的期望N=f(n)
先用前面类似的方法：
那么第一次如果抛出反面(T)那么就回到了前面的情况，即N+1，这个$latex P_1$是1/2
如果前两次抛出了正反(HT)那么又回到开始的情况，即N+2，这个$latex P_2$是1/4
如果前三次抛出了正正反(HHT)那么又回到开始的情况，即N+3，这个$latex P_3$是1/8
..
如果前n次抛出了正...正反(H...HT)那么又回到开始的情况，即N+n，这个$latex P_{n_1}=\frac{1}{2^n}$
如果前n次抛出了正...正正(H...HH)那么就停止了，即此时n，这个$latex P_{n_2}$是$latex \frac{1}{2^n}$
那么综上所述：
$latex N=\frac{(N+1)}{2}+\frac{(N+2)}{4}+..\frac{(N+n)}{2^n}+\frac{n}{2^n}$
解这个方程，得到$latex N=f(n)=2(2^n-1)$
特别的，n=2时，N=6回到上面的答案。
---------------------------------------------------
这个题目说到底是个Markov Chain上的首达问题，下面开始简单介绍下MC. 然后给出一个我猜想的首达问题和物理中电路分析中的电势还有电流电阻的一个比较，我甚至觉得电路中的电子的流动就是Kind of MC. 很有趣的想法，我在床上想了很久，觉得很有意思。
Definition：
Markov Chain
$latex Pr( X_{n+1}=x \mid X_n=x_n, X_{n-1}=x_{n-1}, ...X_1=x_1)=Pr( X_{n+1}=x \mid X_n=x_n)$
说白了就是下一步的概率只和当前状态有关，而和如何到达这个状态无关。下面重点讨论使用比较多的MC，已知$latex X_n$为状态i，$latex X_{n+1}$到达状态j的概率(单步转移概率)，用
$latex P_{ij}^{n,n+1}=P(X_{n+1}=j|X_n=i)$来表示。
$latex P_{ij}^{n,n+1}$是一个与n无关的变量，通常我们把所有的$latex \mathbb{P}=||P_{ij}||_{nn}$写成一个方阵，称之为“单步状态转移矩阵”
P=|P_00,P_01,P_02...|
|P_10,P_11,P_12...|
|P_20,P_21,P_22...|
|....,....,.......|
|P_i0,P_i1,P_i2...|
|....,....,.......|
---------------------------------------------------
自然的，P矩阵n次方后就是n步状态转移矩阵了。一个显然的式子是：
$latex P_{ij}^n=\sum_{k=0}^{\infty}P_{ik}^rP_{kj}^s, \forall r+s=n$
如果$latex P^n$很容易求出来一般式子，那么首达问题就可以由定义求出来
$latex E(N(i,j))=\sum_{k=1}^{\infty}kP_{ij}^k\prod_{t=1}^{k-1}(1-P_{ij}^t)$
当然这个是个非常奔放的想法，偶尔题目很简单的时候可以用用：
比如这个：
抛硬币，第一次遇到连续两次抛的一样的时候停下来，问：抛的次数的期望N (答案为3)
一般情况下上上面的方法有些过于奔放了而做不出答案。假设有{X1,X2..Xn}个不同的状态，不妨假设Xn为终止态，从X1出发，这是个单入口单出口的首达问题。假设从Xi出发首达Xn的期望是Yi步，那么可以由下面的方程组来解决问题:),其中Y是一组列向量，且Yn=0;
Y=P'(Y+1),其中P'为将原单步转移矩阵的第n行替换为(0,0,0,...0) (亦即终点态)
继续用最开始的抛硬币的例子做个说明，所有可能的状态是：
X0: NULL;
X1: H; X2: T;
X3: HT; X4: TH; X5: HH; X6: TT;
X0->|X1->X3 |
| ->X5 | <--终点
| |
|X2->X4 |
| ->X6 |
我们不妨只研究X3-X6的状态就可以了
转移矩阵P为
3 4 5 6
3| 0 0.5 0 0.5 |
4| 0.5 0 0.5 0 |
5| 0.5 0 0.5 0 |
6| 0 0.5 0 0.5 |
| 0 0.5 0 0.5 | |Y3+1| |Y3|
| 0.5 0 0.5 0 | |Y4+1|= |Y4|
| 0 0 0 0 | |Y5+1| |Y5|
| 0 0.5 0 0.5 | |Y6+1| |Y6|
注意到Y5=0解得:
|Y3|=|6|
|Y4|=|4|
|Y5|=|0|
|Y6|=|6|
--------------------
故总的次数为：2+1/4(6+4+0+6)=6 (到达X3-X6的概率都一样都是1/4，前面都用了2步所以要加2)
那么一般的情况也解决了:
都是转化为一个多元的线性方程组来解. 更进一步的，还可以推广到多出口的问题:Xi,Xi+1..Xj都是终点。此外这个题目和电路分析中的电势分析很类似，所谓终止就是接地(V=0),然后已知了上部的电阻的分布，要求的是各个部分的电势。
电子在遇到分叉口时依照一定的概率选择跳到下一个路口，如果是有可能转移的，那么中间以导线相连，转移的概率越大，电阻越小。当源源不断的数以亿万计的电子流过电路时，就好比是Monte Carlo 中的随机simulation，从宏观上表现出来就是各个电路部分的电流大小不一样，并且并联电路上的电势差是一样的。
给个算例：
C
A┏━R━┳━R━┳━R━┳━R━┳━R━...
┃ ┃ ┃ ┃ ┃
R R R R R
┃ ┃ ┃ ┃ ┃
B┗━R━┻━R━┻━R━┻━R━┻━R━...
D
求A-B的电阻，每一段电阻都是R，这个是个无限的问题，可以用类似前面的技巧来做：
设B为0态，那么A-B的电阻为X那么 C-D两点向右看也是个X，
那么X=R(R+X+R)/(R+R+X+R) 得到$latex X=(\sqrt{3}-1)R$
总结下：1. 不用技巧的话，首达问题就转化为一个解线性方程组的问题
2. 用点技巧的话，无限的问题可以转化为一个“无限的旅馆”问题
3. 我觉得电子在导体内部各个节点的随机游动也好比是个MC问题，平稳后宏观表现就是使得电势差和路径无关（基尔霍夫定律）下次写点Brownian motion 貌似这个在真实环境用的比较多。
顺便留道思考题，也是某知名公司的面试题：
有一个袋子里有4个不同颜色的球(更一般的有n个)，每次操作取两个球，并且把后取出来的球染成前一个的颜色再把两个球放回袋子里。试问球的颜色将变成一种颜色的期望操作次数。
