智游城

标题: Random Walk [打印本页]

作者: Howard 时间: 2015-12-31 15:06
标题: Random Walk
今天帮一个朋友计算点东西，还没算出来，但是学到了一点新知识

先拿非人类语言来说：random walk with a boundary of -a and b. the expected steps is ab to reach either boundary.

半人类语言：随机漫步，往东a步跟往西b步，无论到那一个都停止，则预期步数为ab。

人类语言：假设赌场有一种不抽水的赌大小，我们去玩，每次押1元，输a元，或者赢b元就跑。则我们预期玩的把数为ab，输a元的概率为b/(a+b), 赢b元的概率为a/(a+b)

比如输1元或者赢1元就跑，那么预期把数为1。（这不废话吗）
输1元或者赢5元就跑，预期打5吧。
输1赢100，预期打100吧。（当然，大部分都远远小于100把，但有少部分非常非常大。99.01%的情况都以输一把结束。只有不到1%能赢100）
输100或者赢100，预期要打1万把。

作者: taiji18 时间: 2015-12-31 16:09
为什么是-a

作者: taiji18 时间: 2015-12-31 16:13
random walk 也不可能不是东就是西啊

my silly question

作者: bomb 时间: 2015-12-31 17:13

taiji18 发表于 2015-12-31 16:13
random walk 也不可能不是东就是西啊 my silly question

一维不懂二维的世界。

作者: taiji18 时间: 2015-12-31 17:34

bomb 发表于 2015-12-31 17:13
一维不懂二维的世界。

谁是二维，你？

作者: Howard 时间: 2015-12-31 22:46

taiji18 发表于 2015-12-31 02:13
random walk 也不可能不是东就是西啊 my silly question

用-a是为了保证a是正数，后面说起来方便。
东、西走是因为这里只研究一维的random walk

作者: Howard 时间: 2016-1-1 00:58
考虑这个赌大小。我们每次下注1，有p的概率赢1，有q=1-p的概率输1。

m，n均为正整数。
令f(m)表示我们能赢到m个单位的概率。（只要到了就算。无论怎么赢得，可以一路赢上来，也可以赢了m+1又输1。）

则有f(m+1) = f(m) * f(1)

这意思就是说，我们（在某时间点）赢了m+1的概率，可以从我们赢了m（在之前的某时间）的概率算起，再赢一个。

一直递推下去，就会得到：
f(m) = f(1) ^m

关键在于怎么得到f（1）
这个问题早有阐述，陈爷之前的帖子有记载。这里再推导一下。

从0开始，我们有p的概率第一步就赢到1，也可以有q的概率赢到-1。
因此f(1) = p+q*f(2)
又因为f(2) = f(1) ^2
所以 f(1) = p + q*f(1)^2
这是个关于f(1)的二元一次方程，解得：
f(1) = [1 ± (1-2p)] / 2(1-p)

当p<1/2时，取负号，得到f(1) = p/q
当p>1/2时，取正号，得到f(1) = 1

所以当p<1/2时我们能赢到m的概率是(p/q)^m
p>1/2时我们能赢到m的概率是1，一定能赢到。

作者: Howard 时间: 2016-1-1 01:47
接上贴。

上面光考虑了能不能赢到，不计其过程，言下之意，我们和庄家的bankroll都是无穷多，咸鱼总能翻身。
但现实是我们br有限，所以必须要考虑一类新的问题：
在输到-n之前就赢到m的概率是多大？
m、n均为正整数。

g(m,n) 定义为在我们输掉-n之前就赢到+m的概率。
也可以用random walk的语言来说：以p的概率走+1步，以q的概率走-1步，g(m,n)代表在达到-n之前先到达+m

根据上贴的f (m) 的概念（到达m就算，无论经过还是没经过-n）
到达m的路可分两类。一类是没经过-n，第二类是经过了。
没经过-n，那就是g(m,n)
经过-n，那就还得从-n到m，也就是f(m+n)

f(m) = g(m,n) + [1-g(m,n)] * f(m+n)

上贴已经知道f(m) = f(1) 的m次方，所以

f(1)^m = g(m,n) + [1- g(m,n)] * f(1)^(m+n)

当p>1/2，坏事儿了，上式等于
1 = g(m,n) + [1-g(m,n)]
0=0
这个解法就废了

好在p<1/2时可以解出来

(p/q)^m - (p/q)^(m+n)
g(m,n) = ------------------------------------------------
1 - (p/q)^(m+n)

举例：某人赌大小，每次下注1，丫有40%的可能性猜对，总资金10。问丫赢到18的概率多大？
p = 40%
q=60%
m=8 （从10到18，需要赢8）
n=10 （10输光）

直接套公式：
g(m,n) = g(8,10) = (0.667^8 - 0.667^18) / (1 - 0.667^18) = 3.85%

几率实在不高

那位说了，p>1/2无解，咋办。其实也好办。咱就反过来，p做q，q做p，同时m和n也反一下，不就行了吗。

继续

作者: Howard 时间: 2016-1-1 02:12

上贴说道，p>1/2咋办。比如一个人猜对的能力高达60%，他带bankroll 3块钱去赌大小，每次下1。庄家金钱无限。问：他把庄家赢光（或者无休止玩下去）的概率多大？

这里p = 0.6，g(m,n)的公式不能直接用。

可以从庄家的角度去看。这问题等价于庄家（p=0.4）在输光之前不能赢到3块钱的概率，也就是说在赢到3块钱之前就输光的概率，或者说，1 - （输光之前赢到3块钱的概率）
p = 0.4
q = 0.6
m = 3
n = 无穷

g(3,无穷） = （0.667^3 - 0.667^无穷） / （1 - 0.667^无穷） = 0.667^3 = 29.7%

这是庄家先赢到3的概率，也就是玩家破产的概率

那么，玩家有70.1%的把握，靠这3块钱就可以把庄家赢光

作者: taiji18 时间: 2016-1-1 02:14
回头看，头大

作者: Howard 时间: 2016-1-1 02:58
上面说了半天，都是相等步幅的random walk，无论p和q怎么变化，它往正向和反向的步子是一样大的。

赌博游戏的步幅是不一样大的。以百家乐为例，如果下庄家，

结果	盈利	概率	回报
出庄	0.95	0.458597	0.435668
出闲	-1	0.446247	-0.446247
打平	0	0.095156	0
总计：		1	-0.010579

所以押庄每次输1.06%的赌注

作者: Howard 时间: 2016-1-1 07:51
搞了半天还是没找到biased random walk with unequal step sized between boundaries的函数，只好使用最初级的模拟，给算了一下子。

作者: maomaobiao 时间: 2016-1-4 03:04

Howard 发表于 2016-1-1 09:51
搞了半天还是没找到biased random walk with unequal step sized between boundaries的函数，只好使用最初 ...

大概是要找一个赢了走人输了止损的点

然后根据自己的历史统计来调整？

问题是，调整以后呢？胜率p会影响步长么？

作者: shym 时间: 2016-1-4 06:12
从Howard的公式里看到好多个杨幂喔！

作者: monox0 时间: 2016-1-6 14:51
霍神的问题是什么？ random walk 就是对n 重概率为p 的白努力试验求和呗。

作者: Howard 时间: 2016-1-6 22:23

shym 发表于 2016-1-3 16:12
从Howard的公式里看到好多个杨幂喔！

杨幂明显不太喜欢搭理我，因为太难。

我发现加法和乘法组合在一起，经常出现很难的东西。数论的大多数关于猜想，都是加法跟乘法的组合。比如哥德巴赫猜想，孪生质数猜想，费马猜想（如今的费马大定理）。还有黎曼猜想，abc猜想。

作者: Howard 时间: 2016-1-6 22:27

monox0 发表于 2016-1-6 00:51
霍神的问题是什么？ random walk 就是对n 重概率为p 的白努力试验求和呗。

确实是说了半天没有提出真正的问题，发帖只不过是把自己的学习过程记录一下。

这个朋友要我算一个有边界的EV，比如赢到m或者输到n就走，他对该过程中所有赢的牌抽水20%，求这样一个session他的EV。

查了好几天也没有把公式搞出来，只好编程模拟搞定了。

作者: luckystar 时间: 2016-1-8 02:59
Howard的功力真让人配服！

作者: JCreeks11 时间: 2016-4-6 10:59

Howard 发表于 2016-1-6 22:27
确实是说了半天没有提出真正的问题，发帖只不过是把自己的学习过程记录一下。

这个朋友要我算一个有边界 ...

这里构造一个exponential martingale就可以了。

定义 X_i=-1, with probability q, =1-.2, with probability p=1-q. S_n=\sum_{i=1}^n X_i, where X_i's are i.i.d.

构造e^{cS_n},使得他是一个martingale。这里c 是超越方程 p*e^{.8c}+q*e^{-c}=1的解。

然后用optimal stoppoing theorem，可以算得赢到m 的概率为 (1-e^{-cn})/(e^{cm}-e^{-cn})。

EV就很好算了。

作者: Howard 时间: 2016-4-7 23:53

JCreeks11 发表于 2016-4-5 20:59
这里构造一个exponential martingale就可以了。

定义 X_i=-1, with probability q, =1-.2, with probabi ...

高人，高人！！

您说的这些概念我先古狗自学一遍，现在说不上话。。。。

欢迎光临智游城 (http://zhiyoucheng.co/)