Saturday, February 06, 2010

[数学]关于扔硬币得到的序列

现在有一枚硬币, 每次以概率p得到正面(下面以H代表),概率q=1-p得到反面(以T代表).反复投掷这枚硬币并记录出现的结果序列, 比如 T H H T T T H H T H...这样的一个序列. 针对这个序列我们可以说,在时间4我们完成了一个pattern THHT, 在时间6我们完成pattern TTT, 时间9又重复出现了pattern THHT.

下面是一些直观上容易理解的以及费解的:)结论: 

  1. 一个长度为k的给定pattern,在t时刻出现的概率为 p^i q^(k-i).这里i是pattern中T出现的次数. 这个很好理解.比如TTT在任意时刻出现的概率是p^3,  THHT是p^2 q^2, HTHT也是p^2 q^2
  2. 同一个pattern, 两次出现的时间间隔的期望是 1/[p^i q^(k-i)]. 这个结果也很直观. 可以根据Delayed Renewal Process得到. 所以THHT出现间隔是1/(p^2 q^2),HTHT出现间隔也是1/(p^2 q^2)
  3. 一个pattern, 从第一次扔硬币开始到第一次出现的时间期望

    E[time until HTHT] =  E[time until HT] + E[time between HTHT] = E[time between HT] + E[time between HTHT] = 1/(pq) + 1/(p^2 q^2)

    这里的一个trick是把pattern HT和HTHT之间的时间间隔等同于出现pattern HTHT 的间隔. 仔细想一下的话, 出现一次HTHT后这个pattern对下一次出现HTHT的贡献(或者影响)就是它的尾巴HT了. 同理我们还有

    E[time until THHT] =  E[time until T] + E[time between THHT] = E[time between T] + E[time between THHT] = 1/p + 1/(p^2 q^2)

    所以从第一次投硬币开始观察的话,  HTHT和THHT第一次出现的平均时间是不同的.
    同样我们也可以得到连续k个T出现的平均时间, 注意每一次连续出现i个T都对i+1个T有贡献

    E[time until k consecutive T] = 1/p + 1/p^2 + ... + 1/p^k

这个问题还有一个利用Martingale的方法来算,而且是Bob Li提出来的(A martingale approach to the study of occurrence of sequence
patterns in repeated experiments, Annals of Probability, 1980).比如我们要求E[time until HTHT].设在第i轮,一个赌徒下注1块钱.如果第i轮结果是H,赌徒就赢得1/p块钱,接下来第i+1轮结果是T,赌徒就赢得1/(pq)块钱,以此类推.不过如果一旦没有压准,所有钱就输了.请注意这是一个公平赌博.如果每一轮都有一个赌徒来下注.设Xn为第n轮下来赌场的收入:
Xn=(n-4) - [1/(p^2 q^2) -1] + 1 - [1/(pq) -1 ] + 1

因为Xn是Martingale,所以 0 = E[Xn] = (E[n]-4) - [1/(p^2 q^2) -1] + 1 - [1/(pq) -1 ] + 1
也就得出E[n] = 1/(pq) + 1/(p^2 q^2)

No comments: