一道抛硬币的概率题
Shuo Chen
现在做一个游戏，连续地抛这个硬币，直到连续出现两次字为止，问平均要抛多少次才能结束游戏？
注意，一旦连续抛出两个“字”向上游戏就结束了，不用继续抛。
这是某公司的笔试题，大家有空可以做做看。
另外一个变形是，硬币铸造时有差错，抛出字和花的概率分别是p和1-p （0<=p<=1），问平均要抛多少次才能结束这个游戏。
sagasw
不知道算的对不对，
字为1，花为0，组合为00，01，10，11，
出现11的可能性为1/4，
出现01后面跟着10的情况为1/4 * 1/4 * 1/2
Shuo Chen
答案至少要大于 2 吧。
On May 13, 9:49 am, sagasw <sag...@gmail.com> wrote:
> 1/4 + 1/4 * 1/4 * 1/2
> 不知道算的对不对，
> 字为1，花为0，组合为00，01，10，11，
> 出现11的可能性为1/4，
> 出现01后面跟着10的情况为1/4 * 1/4 * 1/2
>
> 2009/5/13 Shuo Chen <giantc...@gmail.com>
sagasw
supern lee
iampeipei
000
001
010
011
100
101
110
111
所以连续为1的概率为3/8
吴彧文
Shuo Chen
设抛出字为1，抛出花为0。
抛2次得到'11'的概率是1/4
抛3次得到'011'的概率是1/8
假设刚好抛n次就结束游戏的概率为p(n)，那么p(1) = 0, p(2) = 1/4, p(3) = 1/8, p(4) = 1/8, p
(5) = 3/32
刚好抛3次结束游戏，那么抛法只有一种：'011'，所以p(3) = 1/8
刚好抛4次结束游戏，那么抛法有2种：'0011'和'1011'，所以p(4) = 2/16 = 1/8
刚好抛5次结束游戏，抛法有3种：'00011', '01011', '10011'，所以p(5) = 3/32
那么平均抛的次数x = 2*p(2) + 3*p(3) + 4*p(4) + 5*p(5) + ... + n*p(n)，n 趋近无穷
问题转换为怎么求p(n)，先歇口气，待会儿说。可以看出，如果刚好抛n次结束（n > 3），那么最后三次一定是'011'，而且前面n-3次里没有
包含'11'，否则就提前结束了。
On May 13, 10:10 am, supern lee <supern....@gmail.com> wrote:
> 任意连续两个出现的概率是1/4,
> 那么n次中的连续两次有(n-1)，
> 则1/4*(n-1)=1
> 所以需要5次
>
> 2009/5/13 sagasw <sag...@gmail.com>
>
> > 概率是0.28
> > 相当于抛四次吧。
>
> > 2009/5/13 Shuo Chen <giantc...@gmail.com>
Shuo Chen
如果第一次抛的是'0'，那么再抛x次就能结束游戏（因为第一个'0'对后面抛的没有影响），一共抛x+1次；
如果第一次抛的是'1'，那么头两次抛有两种情况，'11'和'10'：
抛出'11'已经结束游戏，一共抛2次；
抛出'10'则还需要抛x次才能结束（因为第2次抛出'0'相当于把前面的结果清空了），一共抛x+2次。
这样可以列出：
x = 0.5(x+1) + 0.25*2 + 0.25*(x+2)
解出 x = 6.
On May 13, 10:57 am, 吴彧文 <atyu...@gmail.com> wrote:
> 像这种硬币游戏求概率或者平均投掷次数一般都可以用递归的。
> T = 1 + 0.5T + 0.5( 1 + 0.5 * 0 + 0.5T)
> T = 6.
> 很容易推广到出字概率为p的情况。
> 2009/5/13 Shuo Chen <giantc...@gmail.com>
吴彧文
chaoyan ma
chaoyan ma
离你越近的地方，路途越远；最简单的音调，需要最艰苦的练习
zytju1983
1. n = 1时，p = 0,因为至少需要两次;
2. n = 2时, p = 1/2^2;
3. n = 3时, p = 1/2^3;
...
依次类推可得出平均次数期望为：
2*(1/2^2) + 3*(1/2^3)+...+n*(1/2^n)+...
具体级数计算公式不记得了，哈哈。
zytju1983
2*(1/2^2) + 3*(1/2^3) + ... + n*(1/2^n) + ...
traveler
Alecs King
解方程.
设所求期望为 e, 在上次是字/花的情况下期望分别是 h, t:
e = p(1+h) + (1-p)(1+t)
h = p + (1-p)(1+t)
t = p(1+h) + (1-p)(1+t)
易得 h = 1/p^2, e = t = (p+1)/p^2
p = 0.5 时, h = 1/0.25 = 4, e = t = (0.5+1)/0.25 = 6
--
Alecs King
Denny
1)} / 2^n (n趋向于无穷大)
Denny
hyifeng
现在求 *不连续* 构成两个A 的字符串组合数。
用向量 [A B] 表示 [尾为A的组合数 尾为B的组合数]，
因为A后面只能接B，而B后面可以接A或B，所以状态转移矩阵 M 是
0 1
1 1
一次结果：A、B
[A1 B1] = [1 1]
两次结果：AB、BA、 BB
[A2 B2] = M*[A1 B1] = = [1 2]
三次结果：
[A3 B3] = M*[A2 B2] = = [2 3]
四次结果：
[A4 B4] = M*[A3 B3] = [3 5]
A1，A2，A3....An 这个数列的意义是，抛n 次，得到*非终止*序列的 而且最后一次为 A 的组合数。
只要在这些组合后面再抛一次 A 即可得到终止序列。
从上面可以看出 An 正是斐波那契数 F(n)，可以直接代入通项公式。
所以抛 n 次得到终止序列的概率为 F(n-1)/2^n
得到终止序列的抛硬币次数期望为：2*F(1)/2^2 + 3*F(2)/2^3 + 4*F(3)/2^4 + ....
Shuo Chen
James Z.M. GAO
后面构成A_(n-1)结构, 如果第一次是A, 则第二次必须是B,
于是后面构成A_(n-2)结构, 于是在考察一下A_1和A_2就可以了.
对于期望的计算, 可以考虑生成函数.
设
G(x) = F(1)/2^2 * x^2 + F(2)/2^3 * x^3 + F(3)/2^4 * x^4 + ...
将递归关系带入得到
G(x) = x/(4-2x-x^2)
于是那个无限求和的期望就等于 G'(1)=4.
注意这个期望是最后两次A之前的试验次数, 故加上最后两次A就是期望6了.
chaoyan ma
millky
例如，当p=0.5的时候，则为4次。
推导过程：
E=2*p^2 + 3*p*2p*(1-p) + 4*p*3p*(1-p)^2 +...+ t*p*(t-1)*p*(1-p)^(t-2)
+ ...
最后一项表示，需要抛t次的概率是，最后一次必须为字，概率是p，而前面t-1次任选一次为字，概率是(t-1)*p，其它的t-2次均不为字，概率为
(1-p)^(t-2)。
对无穷级数求和，通过两次求导的方法很容易得到，E=2/p
On 5月14日, 上午9时50分, chaoyan ma <chaoyan...@gmail.com> wrote:
> 好像状态转移图也可以哦，在0101......序列中匹配11字符串
> A B C Z状态分别代表匹配了0个1 1个1 和2个1的状态
> 初始化进入A或B状态 A匹配到1转移到B A匹配到0转移到A B匹配到1转移到C B匹配到0转移到A
> 是不是能这样说？在图中转移次数总共是6次 转移到A的次数是3次 占1/2 转移到B的次数是2次 占1/3 转移到C的次数是1次
> 占1/6
> 所以 平均抛6次能到11状态？？
> 2009/5/13 Shuo Chen <giantc...@gmail.com>
> 离你越近的地方，路途越远；最简单的音调，需要最艰苦的练习- 隐藏被引用文字 -
>
> - 显示引用的文字 -
Lambda
我觉得应该是：
E[X] = 2p^2 + 3p^2(1-p) + 4p^2(1-p)^2 + ... + np^2(1-p)^(n-2)
就是求级数忘记了 :(
李平新
当然，我没有抛 10000次硬币
而是for了10000次
-----------------------------------------------------------------
//CoinTest.java
import java.util.Random;
public class CoinTest {
public static void main(String[] args) {
// TODO Auto-generated method stub
Random r = new Random();
int sum = 0;
for(int j=0;j<10000;j++){
int count=1;
int first =0,tmp;
do{
tmp = r.nextInt(2);
System.out.print(tmp);
if(first==1 && tmp ==first)break;
first=tmp;
count++;
}while(true);
System.out.println("\nCount"+count);
System.out.println("-----------------------------");
sum+=count;
}
System.out.println("average "+sum/10000);
}
}
----------------------
......
-----------------------------
0010101001011
Count13
-----------------------------
011
Count3
-----------------------------
1010011
Count7
-----------------------------
average 6
李平新
chaoyan ma
其实 哪个状态转移的 我也不知道对不对 觉得边界条件有点怪怪的 初始进入A或B状态 这个不知道怎么处理才比较合适
显示详细信息 5月13日 (2 天前) 回复
如果第一次抛的是'0'，那么再抛x次就能结束游戏（因为第一个'0'对后面抛的没有影响），一共抛x+1次；
如果第一次抛的是'1'，那么头两次抛有两种情况，'11'和'10'：
抛出'11'已经结束游戏，一共抛2次；
抛出'10'则还需要抛x次才能结束（因为第2次抛出'0'相当于把前面的结果清空了），一共抛x+2次。
这样可以列出：
x = 0.5(x+1) + 0.25*2 + 0.25*(x+2)
解出 x = 6.