赌徒破产问题

2019-10-09 本文已影响0人 yangzming

1. 概述

比特币白皮书中使用了该理论去证明作恶者的攻击难度，但是阅读白皮书的过程中对相应的概率存有疑问，因此又阅读了一些赌徒破产问题的文章，对相应过程做了推导。

2. 问题和求解

2.1. 问题描述

一个赌徒有h枚金币，每次有概率a赢得一枚金币或者概率b输掉一枚金币，直到其所有的金币总数达到N或者0，则游戏结束，求赌徒最终赢得N枚金币的概率P(N|h)。

2.2. 问题求解

我们很容易确定P(N|N) = 1、P(N|0) = 0。同时有以下状态转移公式：
$P(N|h) = a*P(N|h+1) + b*P(N|h-1)$
根据 a+b = 1 可得：
$aP(N|h) + bP(N|h) = aP(N|h+1) + bP(N|h-1)\\ aP(N|h+1) - aP(N|h) = bP(N|h) - bP(N|h-1)\\ P(N|h+1) - P(N|h) = \frac{b}{a}[P(N|h) - P(N|h-1)]$
从而，我们继续推导可得：
$P(N|h) - P(N|h-1) = \frac{b}{a}[P(N|h-1) - P(N|h-2)] \\ P(N|h-1) - P(N|h-2) = \frac{b}{a}[P(N|h-2) - P(N|h-3)] \\ . \\ . \\ . \\ P(N|3) - P(N|2) = \frac{b}{a}[P(N|2) - P(N|1)] \\ P(N|2) - P(N|1) = \frac{b}{a}[P(N|1) - P(N|0)] \\$
由以上公式，以及P(N|0) = 0，可得：
$P(N|h) - P(N|h-1) = (\frac{b}{a})^{h-1}P(N|1) \\ P(N|h-1) - P(N|h-2) = (\frac{b}{a})^{h-2}P(N|1) \\ .\\ .\\ .\\ p(N|3) - P(N|2) = (\frac{b}{a})^{2}P(N|1) \\ p(N|2) - P(N|1) = \frac{b}{a}P(N|1)$
将上述式子左右相加可得到：
$P(N|h) = P(N|1)[1 + \frac{b}{a} + (\frac{b}{a})^{2} + ... + (\frac{b}{a})^{h-2} + (\frac{b}{a})^{h-1}] \\ P(N|h) = \begin{cases} \frac{1 - (\frac{b}{a})^{h}}{1 - \frac{b}{a}}P(N|1) \quad 如果 \frac{b}{a} \neq 1 \\ hP(N|1) \quad 如果 \frac{b}{a} = 1 \\ \end{cases}$
由P(N|N) = 1，可得：
$P(N|1) = \begin{cases} \frac{1 - \frac{b}{a}}{1 - (\frac{b}{a})^{N}} \quad 如果 \frac{b}{a} \neq 1 \\ \frac{1}{N} \quad 如果 \frac{b}{a} = 1 \\ \end{cases}$
所以得：
$P(N|h) = \begin{cases} \frac{1 - (\frac{b}{a})^{h}}{1 - (\frac{b}{a})^{N}} \quad 如果 \frac{b}{a} \neq 1 \\ \frac{h}{N} \quad 如果 \frac{b}{a} = 1 \\ \end{cases}$
当N趋于无穷大时，如果 $a>b$ ，有 $(\frac{b}{a})^N\rightarrow0$ ， $\frac{1}{N}\rightarrow0$ ，如果如果 $a\leq b$ ，那么有P(N|h) = 0,综合可得：
$P(N|h) = \begin{cases} 1 - (\frac{b}{a})^{h} \quad 如果 a > b \\ 0 \quad 如果 a \leq b \\ \end{cases}$