Home

漫画里的数学：《欺诈游戏》第24话里的6% (Analysis of a Game Involving Bernoulli Trials)

2009, December 15 - 11:19pm — vyvy

在这帖子里我分析了《欺诈游戏》漫画里出现的某个机率。最近我朋友看这漫画时问了我另一问题：第24话里出现的6%。我研究了一下，这问题也蛮有趣的。先说明一下：

  • 以下的分析涉及到一点大学程度的数学，但高中程度的数学知识就应可读懂。
  • 我在高中用中文学数学，上了大学却用英文，所以不太懂得运用某些专有名词。为避免張冠李戴用错专有名词，我以英文作分析。

This is a mathematical problem from a Japanese manga Liar Game.

问题 Problem

The game involves two players (S and F) and consists of several rounds. Each round is essentially a Bernoulli trial with probability p of success. Player S scores a point if the trial is a success, otherwise Player F scores a point. The game ends when one player wins by first obtaining N points.

  1. Find out the probability P that Player S will win the game, in terms of p and N.
  2. Verify the claim in the comic that, if N=10 and p=1/3, Player S stands for a chance of only P≅6% to win the game.

解答 Solution

Let m be the number of rounds, which is also the number of Bernoulli trials, in a game. We have m ≧ N, since any player needs at least N rounds to score N points. We also have m ≦ 2N-1, since the game will be decided when the winner has scored N points, and the loser has scored no more than N-1 points. In short, N ≦ m ≦ 2N-1.

If Player S has won a game, then in this game,

  • there must be exactly N-1 successes in the first m-1 trials of the game; and
  • the m-th trial must be a success.

Thus, the probability P for Player S to win a game is given by:

By substituting N=10 and p=1/3 into the formula above, we get P = 0.064766... ≅ 6.48% ≅ 6%. This verifies the claim in the comic.

以上分析证明了漫画中那“6%”的正确性！

可算得更快吗？ Faster Way to Get the Answer?

以上的方程式可给出精确的答案，但算起却较耗时。我是写了以下附上的Python小程序来作计算的。（警告！这程序只是个 quick and dirty hack，別用得太认真或拿去卖！）可否简化成更简捷的方程式呢？我尝试了一下，但找不到一个滿意的算法。那么，可否找出一个近似但简捷的方程式？这我倒找到了好几个，但算出的答案误差不小。若有高手找到更好的方程式，欢迎交流！

While the formula above gives the exact answer, it is slow. I have written a Python program to do the job. (Caution! The program is actually a quick and dirty hack which violates tons of good programming practices! Use it at your own risk!) Can we simplify the formula further? I tried for a while but failed to get a satisfactory one. Can we have a fast formula that gives an approximate answer? I found several, but none of them produces answer that is 'approximate' enough. If you have found some good formulas, welcome to share them with me!

from math import *
binom = lambda n, k: factorial(n) // (factorial(k)*factorial(n-k))
prob = lambda p, N: p**N * sum(binom(m+N-1, m)*(1-p)**m for m in range(N))
p = 1/3
N = 10
print('=> {0}%'.format(100*prob(p, N)))