一个概率问题

[Zhimin]

有N个灯泡，用枪去打这些灯泡。灯泡有亮和灭两种状态。开始的时候，这N个灯泡都亮着，用枪去打它们，每一枪都能打到一个灯泡且只打到一个灯泡，亮着的
灯泡打到的话就被打灭，灭着的灯泡被打到的话仍然是灭的。问打M枪后，所有灯泡被打灭的概率是多少?怎样思考解析式？

[R.C]

我得想法是，首先这个一个马氏过程，转移概率矩阵可以容易求出，那么，现在的问题就转换成了求Pn0(M)了~~剩下的就是运算~~~

--------------------------------------------------
From: "Zhimin" <zhimin...@gmail.com>
Sent: Friday, June 13, 2008 10:45 AM
To: "TopLanguage" <pon...@googlegroups.com>
Subject: [TopLanguage] 一个概率问题

[翁翊成]

额。。。。
这个问题无趣，不如问，树上一堆麻雀，打一枪剩几只？

2008/6/13 R.C <col...@gmail.com>:

[Zhimin]

不理解马氏过程，能否请详细点介绍一下。谢谢！

刚才想不出来，就写了个程序模拟了一下。比如N=50,100,200。对应每个N值，取一系列的M值多次计算，得到约化的概率曲线很圆滑，都能重叠在
一起。这个过程不知道和上面说的马氏过程是否相关。当M=0.5N时，概率为39%左右。M=1.0N的时候，概率为63%左右，M=2.0N的时候概
率为86%左右，当M=4N就差不多完全可以打灭。

On 6月13日, 上午11时04分, "R.C" <colp...@gmail.com> wrote:
> 我得想法是，首先这个一个马氏过程，转移概率矩阵可以容易求出，那么，现在的问题就转换成了求Pn0(M)了~~剩下的就是运算~~~
>
> --------------------------------------------------

> From: "Zhimin" <zhimin.xi...@gmail.com>

[Zhimin]

这个问题也不是那么无趣，好像有人用这个玩意做娱乐游戏。能理解一下很不错的，呵呵，我还想学学马氏过程。

On 6月13日, 上午11时07分, "翁翊成" <weng...@gmail.com> wrote:
> 额。。。。
> 这个问题无趣，不如问，树上一堆麻雀，打一枪剩几只？
>

> 2008/6/13 R.C <colp...@gmail.com>:

>
> > 我得想法是，首先这个一个马氏过程，转移概率矩阵可以容易求出，那么，现在的问题就转换成了求Pn0(M)了~~剩下的就是运算~~~
>
> > --------------------------------------------------

> > From: "Zhimin" <zhimin.xi...@gmail.com>

[pongba]

2008/6/13 Zhimin <zhimin...@gmail.com>:

不理解马氏过程，能否请详细点介绍一下。谢谢！

http://en.wikipedia.org/wiki/Markov_chain

--
刘未鹏(pongba)|C++的罗浮宫
http://blog.csdn.net/pongba
TopLanguage
http://groups.google.com/group/pongba

[rmq]

p[x][y]表示还有y个灯泡还亮着，还能再打x枪，最终所有灯泡都灭的概率

那么p[M][N]为所求。
p[x][y]=(y/N)*p[x-1][y-1] +(1-y/N)*p[x-1][y]

其中p[0][0]=1, p[0][z]=0 (z>0)

[LS]

我给个数学的分析，大家看对不对。
首先，M>=N，这点毋庸置疑。
其次，M枪打N个灯泡，一共有N^M种可能。
再次，思考M枪没有全部打灭的情况：
1 全部打到除了1号灯泡之外的灯泡，则有(N-1)^M可能，N个灯泡，因此有C(N,1)*(N-1)^M可能。
2 全部打到除了1，2号灯泡之外的灯泡，则有(N-2)^M可能，N灯泡取两个，因此有C(N,2)*(N-2)^M可能。
3 。。。
N-1 全部打到一个灯泡上，则有C(N,N-1)*1^M=C(N,N-1)种可能。
最后，所有灯泡被打灭的概率为：
1 - ( (C(N,1)*(N-1)^M + C(N,2)*(N-2)^M + ... + C(N,N-1)) / N^M )

On 6月13日, 上午10时45分, Zhimin <zhimin.xi...@gmail.com> wrote:

[gzc9047]

如果不考虑每枪打掉灯泡的次序而只考虑结果，那么M枪打在N个灯泡上的总计数是C(M+N-1,N-1)，每个灯泡都被打到的计数是C(M,N-1)，
概率就是这两个数相除。

[alai]

2枪打2个灯，全灭的概率为1/2。而C(2,1)/C(3,1)=2/3，不对。

在 08-6-14，gzc9047<gzc...@gmail.com> 写道：

[gzc9047]

恩，如果考虑打破灯泡的次序需要算一堆概率，比如M枪打掉N-1个灯泡的概率、打掉N-2个灯泡的概率，靠这些概率推导打掉N个灯泡的概率，就是一个马
尔科夫过程。

On Jun 14, 10:38 am, alai <ala...@gmail.com> wrote:
> 2枪打2个灯，全灭的概率为1/2。而C(2,1)/C(3,1)=2/3，不对。

[alai]

是不用考虑次序啊。转个说法，M个人一起开枪打N个灯，每个人都肯定打中一个灯，至于打中哪个灯则是等概率的。2个人打2个灯，2人打中同一盏灯的概率是1/2，各打一盏的概率是1/2，所以全灭的概率是1/2。

2008/6/14 gzc9047 <gzc...@gmail.com>:

[Patrick]

样本空间 n^m
最后一枪干掉 最后一个亮着的灯泡 n 种可能 ，剩下 n-1个位置和 m-1枪
n-1个位置必填满，P(m-1,n-1)，顺序无所谓，全排
剩下(m-1)-(n-1)=m-n枪，这m-n枪在n-1的位置上随意填 (n-1)^(m-n)

n * P(m-1,n-1) * (n-1)^(m-n) / n^m

但感觉不对,P(m-1,n-1) * (n-1)^(m-n)里面貌似有重复的

On 6月13日, 上午10时45分, Zhimin <zhimin.xi...@gmail.com> wrote:

[gzc9047]

我指的不考虑次序是如果两种击打次序造成的结果一样并且这两种击打次序击打每盏灯的数量相同，则认为这两个击打次序是一个。主要考虑灯的互异和次序的无
关。这是一种建模方式，你说的应该是另一种模型。