技术头条 - 一个快速在微博传播文章的方式     搜索本站
您现在的位置首页 --> 算法 --> 生成函数的妙用:平均抛掷多少次硬币才会出现连续两个正面?

生成函数的妙用:平均抛掷多少次硬币才会出现连续两个正面?

浏览:1476次  出处信息

     在一篇老日志中,我提到了一个经典的概率问题:平均需要抛掷多少次硬币,才会首次出现连续两个正面?它的答案是 6 次。它的计算方法大致如下。

     首先,让我们来考虑这样一个问题: k 枚硬币摆成一排,其中每一枚硬币都可正可反;如果里面没有相邻的正面,则一共有多少种可能的情况?这可以用递推的思想来解决。不妨用 f(k) 来表示摆放 k 枚硬币的方案数。我们可以把这些方案分成两类:最后一枚硬币是反面,或者最后一枚硬币是正面。如果是前一种情形,则我们只需要看前 k - 1 枚硬币有多少摆法就可以了;如果是后一种情形,那么倒数第二枚硬币必须是反面,因而这种情形下的方案数就取决于前 k - 2 枚硬币的摆放方案数。因此我们得到, f(k) = f(k - 1) + f(k - 2) 。由于摆放一枚硬币有两种方案,摆放两枚硬币有三种方案,因而事实上 f(k) 就等于 Fk+2 ,其中 Fi 表示 Fibonacci 数列 1, 1, 2, 3, 5, 8, …的第 i 项。

     而“抛掷第 k 次才出现连续两个正面”的意思就是,最后三枚硬币是反、正、正,并且前面 k - 3 枚硬币中正面都不相邻。因此,在所有 2k 种可能的硬币正反序列中,只有 Fk-1 个是满足要求的。也就是说,我们有 F1 / 4 的概率在第二次抛币就得到了连续两个正面,有 F2 / 8 的概率在第三次得到连续两个正面,有 F3 / 16 的概率在第四次得到连续两个正面・・・・・・因此,我们要求的期望值就等于:

    

         这个无穷级数就等于 6:

    

     不过,最后这一步来得也太假了,因为我们借助了强大的 Mathematica 。今天重新翻到这篇旧日志时,我就在想,究竟怎样求出这个无穷级数呢?这个数列的某些特征让我联想到了生成函数这一数学工具,用生成函数处理这样的数列非常合适。我在很早很早以前就写过介绍生成函数的文章,但遗憾的是,我对生成函数运用的了解,仅仅局限于教材和网络上给出的各种经典例子,从没有亲自用到过生成函数。今天算是我第一次真正使用生成函数,深感生成函数之妙。如果你是第一次看到生成函数的应用,想必你会大吃一惊,这种诡异的方法竟然能把答案搞出来!整个过程用到了很多生成函数的经典处理手段,这让它足以打败教材上的各种经典例子,成为了我最爱的生成函数应用例题之一。

      

         让我们先来说说什么是生成函数吧。生成函数就是对数列进行编码的一种方式。我们可以用一个含有无限多项的整系数多项式(注:这个说法是不准确的,有无限多项的不能叫多项式) a1 ・ x1 + a2 ・ x2 + a3 ・ x3 + … 把整个数列的全部信息装进去,其中第 i 次项系数就表示数列的第 i 项。因此,Fibonacci 数列的生成函数就可以写成:

    

     厉害就厉害在,我们可以把生成函数表示成一个更简单的形式。先来看看 g(x)・x 的结果:

    

     再看看 g(x) + g(x)・x 的结果:

    

     你会发现, Fibonacci 数列的递推性质,使得上面这行式子与 g(x) 本身非常相像。事实上,如果把 g(x) 的每一项都除以 x ,再减去最前面多出来的 1 ,就能得到上面的这行式子了。因此,我们有:

    

     我们甚至可以就此解出 g(x) 来:

    

     于是,整个无穷级数 g(x) 被我们化简为了一个关于 x 的代数式!注意,虽然这个等式只在 x 充分小(小到级数 g(x) 收敛)的时候才有意义,不过这并不妨碍我们用这个代数式来代表 Fibonacci 数列的生成函数。我们可以把 Fibonacci 数列看作是生成函数的一个“展开”:

    

     也就是说,这么一个小小的代数式就容纳了 Fibonacci 数列的全部信息!

      

         生成函数是如此地具有代表性,以至于在研究数列时,我们常常会给出它的生成函数。在数列百科全书 OEIS 中,生成函数几乎是必不可少的一项。例如,在 Fibonacci 数列 的描述中,FORMULA 一栏的第一行就是 G.f.: x/(1-x-x^2) ,说的就是 Fibonacci 数列的生成函数(generating function)。

     更绝的是,我们还可以直接对数列的生成函数进行变换,从而得到新的数列。比方说,在生成函数上再乘以一个 x ,我们就会让每一项的 x 的指数加 1 ,从而让整个数列右移一位,得到了一个新的数列 Fi-1,即 0, 1, 1, 2, 3, 5, …

    

     现在,我们需要用各种代数运算手段,对等式左边的生成函数进行变换,让等式右边的展开式变成本文开头的那个数列。什么操作能够同时让数列第 1 项除以 2 ,第 2 项除以 4 ,第 3 项除以 8 ,以此类推,让所有的第 i 项都除以 2i 呢?我们可以把所有的 x 都用 x / 2 来替代:

    

     化简一下:

    

     这就是数列 Fi-1 / 2i 的生成函数了。接下来,我们想要让第 i 项系数乘以一个 i ,也就是想要让每一项的系数都乘以该项的次数,这该怎么办呢?最神奇的地方出现了――我们对生成函数进行求导:

    

     也就是:

    

     不过,求导的同时,x 的次数也移动了一位。我们在生成函数上再乘以 x ,把 x 的次数纠正回来:

    

     这就是本文最初的那个数列的生成函数了。令 x = 1 ,便有:

    

QQ技术交流群:445447336,欢迎加入!
扫一扫订阅我的微信号:IT技术博客大学习
© 2009 - 2024 by blogread.cn 微博:@IT技术博客大学习

京ICP备15002552号-1