智游城

 找回密码
 注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 6164|回复: 19
打印 上一主题 下一主题

Random Walk

[复制链接]
跳转到指定楼层
1#
Howard 发表于 2015-12-31 15:06:02 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
今天帮一个朋友计算点东西,还没算出来,但是学到了一点新知识

先拿非人类语言来说: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万把。
分享到:  QQ好友和群QQ好友和群 QQ空间QQ空间 腾讯微博腾讯微博 腾讯朋友腾讯朋友 微信微信
收藏收藏1
2#
taiji18 发表于 2015-12-31 16:09:45 | 只看该作者
为什么是-a
3#
taiji18 发表于 2015-12-31 16:13:23 | 只看该作者
random walk 也不可能不是东就是西啊 my silly question
4#
bomb 发表于 2015-12-31 17:13:53 | 只看该作者
taiji18 发表于 2015-12-31 16:13
random walk 也不可能不是东就是西啊 my silly question

一维不懂二维的世界。
5#
taiji18 发表于 2015-12-31 17:34:36 | 只看该作者
bomb 发表于 2015-12-31 17:13
一维不懂二维的世界。

谁是二维,你?
6#
 楼主| Howard 发表于 2015-12-31 22:46:30 | 只看该作者
taiji18 发表于 2015-12-31 02:13
random walk 也不可能不是东就是西啊 my silly question

用-a是为了保证a是正数,后面说起来方便。
东、西走是因为这里只研究一维的random walk
7#
 楼主| Howard 发表于 2016-1-1 00:58:52 | 只看该作者
考虑这个赌大小。我们每次下注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,一定能赢到。

8#
 楼主| Howard 发表于 2016-1-1 01:47:26 | 只看该作者
接上贴。

上面光考虑了能不能赢到,不计其过程,言下之意,我们和庄家的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也反一下,不就行了吗。

继续
9#
 楼主| Howard 发表于 2016-1-1 02:12:09 | 只看该作者

上贴说道,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块钱就可以把庄家赢光
10#
taiji18 发表于 2016-1-1 02:14:22 | 只看该作者
回头看,头大
您需要登录后才可以回帖 登录 | 注册

本版积分规则

手机版|Archiver|智游城论坛

GMT+8, 2024-11-13 06:01 , Processed in 0.045527 second(s), 7 queries , Redis On.

Powered by Discuz! X3.2

© 2001-2012 Comsenz Inc.

返回顶部