抛的硬币直到连续出现两次正面为止,平均要扔多少次

  数学 概率论 随机过程    浏览次数: 743
1

题库里的一道面试题:

“连续抛一枚公平的硬币,直到连续出现两次正面为止,平均要扔多少次硬币?”


答案是6,解答不详细,是这么说的“马尔可夫链,可做图求解递归方程。”


管理员手下留情,不要删帖,谢谢!


 

Gakki   2018-03-22 11:13



   3个回答 
11

答案里提到“马尔可夫链,可做图求解递归方程”。这应该是靠谱的思路。

假定扔出正面(H)的概率为p,扔出反面(T)的概率为1-p。

我们需要扔出连续2个H。在整个过程有这么几种状态

1)当前连续0个正面(0H);2)当前连续1个正面(1H);当前连续2个正面(2H)。

           

状态转换图如上。

如果当前是0H,那么p的概率,下一个状态是1H;1-p的概率维持在0H。

如果当前是1H,那么p的概率,下一个状态为2H(达到条件,任务完成);1-p的概率回到0H。

假设期望$x$次后,得到2H。

那么$$x=(1-p)(1+x)+p^2 \times 2 + p (1-p)(2+x)$$

第一个部分$(1-p)(1+x)$的意思是说,如果先扔出一个T,然后状态保持在0H,所以人仍然需要$x$次来完成任务。第二部分是说,先扔出H,再扔出H,两步完成任务,这种情况的概率为$p^2$。第三部分是先扔出一个H,此时状态为1H,然后又扔出一个T,状态回到0H,这种情况的概率为$p(1-p)$,用了两次回到0H,所以需要$2+x$次。

根据上面的式子,可以解得$$x=\frac{1+p}{p^2}.$$

这个硬币是无偏差的,所以$p=0.5$,所以$x=6$。


kidd23   2018-03-25 11:50

4

Markov Chain hitting time公式http://www.statslab.cam.ac.uk/~james/Markov/s13.pdf

相关网页:https://www.quora.com/What-is-the-expected-number-of-coin-flips-until-you-get-two-heads-in-a-row

假设有三个状态,S1是开始或抛出反面,S2是抛出一个正面,S3是连续抛出两个正面并且游戏结束。

初始状态$x_0=[1, 0 ,0]$,状态转移矩阵是

$P=[0.5, 0.5 ,0;$

$    0.5, 0, 0.5;$

$0, 0 ,1]$

根据第一个链接里定理1.3.5


$K_i^A $是状态i到状态A的步数的期望

$K_1^3 = 1 + \sum\limits_{j = 1}^2 {{P_{1j}}K_j^3}$

$K_2^3 = 1 + \sum\limits_{j = 1}^2 {{P_{2j}}K_j^3}$ 

最后从起始S1到S3的步数的期望

$K_1^3 = {{1+0.5} \over {{0.5}^2}}=6$

Zealing   2018-03-22 23:52

3

可以通过矩阵计算得出每一个状态的期望,首先状态转移矩阵transition matrix是$P=[[0.5,0.5,0],[0.5,0,0.5],[0,0,1]]$,然后我们计算fundamental matrix,$N=(I-Q)^{-1}$,其中$Q=[[0.5,0.5],[0.5,0]]$,得到$N=[[4,2],[2,2]]$,然后得到S1,和S2状态分别的期望:$t=NI$其中$I=[[1],[1]]$,result:$[6,4]$说明从最初的状态开始需要6次,从第二个状态开始只需要4次。

tomoku   2018-04-23 04:47



  相关主题

伯努利过程和泊松过程   1回答

一个关于病毒分裂的概率题   1回答

概率论中的鞅是什么?   1回答

已知概率转移矩阵,怎么求平稳概率分布?   1回答

布朗桥brownian bridge是什么?   1回答

贝叶斯网络中的markov blanket是什么意思?   2回答

[0, 1]内随机抽取n个不重叠闭区间的概率   1回答

对于独立正态变量X, Y ~ N(0,1),X+Y和X-Y是否独立?   1回答

柯西分布没有数学期望   1回答

扑克牌中的一个概率题   1回答

用一个骰子生成1到7的随机数?   4回答

证明马尔可夫不等式   1回答



回答问题时需要注意什么?

我们谢绝在回答前讲“生动”的故事。

我们谢绝“这么简单,你自己想”、“书上有的,你认真看”这类的回答;如果你认为对方的提问方式或者内容不妥,你可以直接忽略该问题,不用进行任何作答,甚至可以对该问题投反对票。

我们谢绝答非所问。

我们谢绝自己不会、硬要回答。

我们感激每一个用户在编写答案时的努力与付出!