概率生成函数详解

一、初识概率生成函数

概率生成函数是概率论和离散数学中经常用到的工具，它可以将离散的随机变量用一个生成函数的形式表示出来。对于一个随机变量 $X$，它的概率生成函数可以用下面这个公式来表示：

  $$ G_X(s) = \sum_{x=0}^{\infty} P(X=x) s^x $$

其中 $P(X=x)$ 是随机变量 $X$ 取值为 $x$ 的概率。从公式中可以看出，如果我们知道了一个离散随机变量的概率生成函数，那么我们就可以通过求导、积分等运算来获取它的各种统计量，比如期望、方差等。

二、概率生成函数的特性

概率生成函数有许多有用的特性，下面我们分别来介绍几个常用的特性。

1、独立随机变量的生成函数的乘积

如果有两个独立的离散随机变量 $X$ 和 $Y$，那么它们的概率生成函数的乘积就等于它们对应的概率生成函数的积，即 $G_{XY}(s) = G_X(s) G_Y(s)$。

  // 代码示例：计算两个独立随机变量的生成函数的积
  void multiply_generating_function(vector& g1, vector& g2, vector& g3) {
      int n = min(g1.size(), g2.size()) - 1;
      g3.resize(n + 1);
      for (int i = 0; i <= n; i++) {
          g3[i] = 0;
          for (int j = 0; j <= i; j++) {
              g3[i] += g1[j] * g2[i - j];
          }
      }
  }

2、多个随机变量的加权生成函数的和

假设有 $n$ 个离散随机变量 $X_1, X_2, …, X_n$，它们分别有不同的概率生成函数 $G_1(s), G_2(s), …, G_n(s)$，以及对应的概率 $p_1, p_2, …, p_n$。那么它们的加权生成函数的和就可以表示为：$G(s) = \sum_{i=1}^n p_i G_i(s)$。

  // 代码示例：计算多个随机变量的加权生成函数的和
  void sum_generating_function(vector& g_list, vector& p_list, vector& g_sum) {
      int n = g_list.size();
      int m = g_list[0].size() - 1;
      g_sum.resize(m + 1);
      for (int i = 0; i <= m; i++) {
          g_sum[i] = 0;
          for (int j = 0; j < n; j++) {
              g_sum[i] += g_list[j][i] * p_list[j];
          }
      }
  }

3、泊松分布的概率生成函数

泊松分布是一种常见的离散概率分布，它的概率生成函数可以用以下公式表示：$G(s) = e^{\lambda(s-1)}$，其中 $\lambda$ 是泊松分布的参数。

  // 代码示例：计算泊松分布的生成函数
  void poisson_generating_function(double lambda, vector& pgf) {
      int m = 1000; // 假设只计算前 1000 项
      pgf.resize(m + 1);
      for (int i = 0; i <= m; i++) {
          pgf[i] = exp(lambda * (i - m) / m);
      }
  }

三、应用举例

概率生成函数在概率论、组合数学等领域有着广泛的应用，下面我们分别介绍几个例子。

1、随机游走的期望值

随机游走是一种经典的概率问题，它的概率生成函数可以表示为：$G(s) = \frac{1}{2} (s + \sqrt{s^2-4p(1-p)}) + \frac{1}{2} (s – \sqrt{s^2-4p(1-p)})$，其中 $p$ 是随机游走向右的概率。

我们可以通过对概率生成函数求导来计算随机游走的期望值。具体地，设概率生成函数为 $G(s)$，那么随机游走的期望值等于：$E[X] = G'(1)$。

  // 代码示例：计算随机游走的期望值
  double random_walk_expectation(double p) {
      double t = sqrt(1 - 4 * p * (1 - p));
      double s1 = 0.5 * (1 + t) / p;
      double s2 = 0.5 * (1 - t) / p;
      return s1 * s1 + s2 * s2;
  }

2、组合恒等式的证明

组合恒等式是组合数学中重要的恒等式之一，它的概率生成函数可以表示为：$(1+s)^n = \sum_{k=0}^n {n \choose k} s^k$。

我们可以通过对概率生成函数进行求导来证明这个恒等式。具体地，设概率生成函数为 $G(s)$，那么我们可以使用二项式定理来展开 $(1+s)^n$，然后对其求导即可得到 $\sum_{k=0}^n k{n \choose k} s^{k-1}$。同时，我们也可以对 $\sum_{k=0}^n {n \choose k} s^k$ 求导，然后做一些简单的变形就可以得到相同的结果。

3、组合游戏的胜率

组合游戏是一种常见的博弈论问题，它的玩法是两个人轮流从 $n$ 个数字中取数，取的时候不能取已经被取过的数字，最后无法取数的人输。我们假设先手能够取走 $m$ 个数字，那么胜率可以根据 $m$ 和 $n$ 来计算，具体公式如下所示：$P = \frac{1}{2} (1 + G_{(n-m)/n}(P)^m)$。

其中 $G_{(n-m)/n}(P)$ 是取到第 $m$ 个数字的时候，还有 $(n-m)$ 个数字的概率生成函数。我们可以通过一些数学推导来得到这个公式，具体的计算方法可以使用二分法等数值方法。

结语

概率生成函数是一种非常有用的工具，在许多应用领域都能够发挥出重要的作用。希望本文介绍的内容对读者有所启发，让大家能够更好地应用概率生成函数来求解各种概率问题。

原创文章，作者：ZCNZJ，如若转载，请注明出处：https://www.506064.com/n/372418.html