一个抛硬币的问题

网上看到的一个抛硬币问题,想了我一晚上,仍没有最终解决:
一个面朝上概率为1/2的硬币,抛2^k次,统计其中连续k个面出现的次数T_k。注意,我们允许重叠,如k=3时,”HHHHHTHH”的T_k=3。求k->infinity时,T_k的极限分布。
 
以下将连续抛n次硬币的结果看成长度为n的一个字符串。出现连续k个H称为一个“k连串”。
 
首先想到的是直接求分布。由于事件{字符串不含k连串}或{字符串含t个k连串}都不容易描述,所以试图用递归的方法。对于不含k连串的概率倒是能弄出一个递推公式来:
 
P(长度为n的字符串不含k连串) = (1/2)^2*[3+n-k-1 – \sum_{i=1}^{n-k-1}  P(长度为i的字符串不含k连串)]
 
但无法从上述递推公式推导出通项。似乎能证明P(T_k=0)的极限比1/2小。用matlab算了k=1,2,…,15时的P(T_k=0),似乎趋向于0.4。但更大的k就算不了了。
 
然后想到转换成一个马尔可夫链。令Xt={从t到t+k-1的子串}。譬如说对于k=2, “HHHTH”对应于X1=HH, X2=HH, X3=HT, X4=TH,或用二进制表示是11,11,10,01。可以证明{Xi}是马尔可夫链,状态空间是所有的k位二进制数,其转移矩阵是P(i -> (2i mod 2^k)) = P( i -> (2i mod 2^k) +1 ) = 1/2,P(其他)=0,或者说是长得像以下这个样子(记p=1/2):
 
  0
0
0
0
0
1
0
1
0
0
1
1
1
0
0
1
0
1
1
1
0
1
1
1
000            
001            
010            
011            
100            
101            
110            
111            
 
则T_k就是在2^k步内访问”111″的次数。由于题目要求极限分布,所以在想能不能用马氏链的极限性质来解决。这是个有限状态不可约链,所以是正常返的,其唯一的稳态分布是pi = (2^k, 2^k, …, 2^k),根据Ergodic Theorem,当步数趋向无限时,访问”111″的次数占总步数的比例almost surely趋向于1/2^k。这一结论让我猜测2^k步内访问”111″的次数(即T_k)也趋向于1,即P(T_k = 1) = 1 as k->infinity,但这与之前P(T_k = 0)<1/2的观察矛盾。仔细分析发现原因是Ergodic Thm的极限过程与原题的不一样。
 
于是试图直接求2^k步内访问”111″的次数。这个马氏链的状态空间大小是2^k,所以先来压缩一下它。
 
 
我们重新定义状态。Yt={从t+k-1往回数,连续H的个数}(若连续H的个数超过k,则Yt=k)。譬如k=3时,“KKHHH”对应于Y1=1,Y2=2,Y3=4。我们注意到Yt与Xt的关系是Yt={Xt从右边数起连续1的个数}。换句话说,k=3时,当X1=000或010或100或110时,Y1=0;当X1=001或101时,Y1=1;当X1=011时,Y1=2;当X1=111时,Y1=3。
 
至此状态空间大小从原来的2^k缩小到k。这个仍然是转移概率矩阵已知,不可约正常返的离散时间马尔可夫链。现在要求其在2^k步内访问状态k的次数的分布的极限。
 
如何求这个次数的分布呢?

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: