God of gamblers

这题说来搁置好久了。

这题是2017年西安现场的一道题，记得当时现场大部分队伍直接猜答案都过了。我们队当时头铁一直推结论没推出来，浪费了大量的时间。本想着退役最后一年，随便打打应该也能混个铜，结果因为这题最后连铜都没打到，真是讽刺。

题意很简单，两人公平赌博，A下注，A赢了则赢取双倍赌注，否则下注的钱归B。 比较奇怪的是A会按照这样一种策略下注：第一次下注1，如果输了，则下注2、4、8……，直到某一局赢了为止。

问：最后A赢光B所有的钱的概率。

题解

我们不难发现：A按照这样的策略去下注，只要有一局赢了，都相当于A赢了1块钱。那么我们可以把这一整个过程看作一次赌博，这一次赌博要么输光所有的钱（全输）；要么赢B一次，赚1块。

由随机过程的知识，可以计算出A输光目前的钱的概率是 \[ P_{n,0}=(\frac{1}{2})^k \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ k=\log_2^{n+1} \] 同时可知 \[ P_{n,n+1}=1-(\frac{1}{2})^k \] 带入k \[ P_{n,0}=\frac{1}{n+1} \ \ \ \ \ \ \ \ \ \ \ \ \ P_{n,n+1}=\frac{n}{n+1} \] 容易看出A必须一直赢到最后为止： \[ ans=\prod_{i=n}^{n+m-1} \frac{i}{i+1} =\frac{n}{n+m} \]

当时这题有人赛后说是马尔可夫过程，其实这样算下来其实也没有用到什么马尔可夫链的性质，主要在于把赢一次的过程看成一个整体，就能得到结果。