d**z 发帖数: 183 | 1 一个random walk
从 0出发,在n步之内先于-b到达a的概率是多少?
谢谢各位大牛了~~~ |
d********t 发帖数: 9628 | 2
b/(a+b)
【在 d**z 的大作中提到】 : 一个random walk : 从 0出发,在n步之内先于-b到达a的概率是多少? : 谢谢各位大牛了~~~
|
l******i 发帖数: 1404 | 3 It reminds me of the famous interview question called "Drunk Man" on Chapter
5 of Xinfeng Zhou's book. |
d**z 发帖数: 183 | 4 这个是先于-b到达a的概率。
如果限制在n步之内呢?如果n步内没到a就算失败了
【在 d********t 的大作中提到】 : : b/(a+b)
|
d********t 发帖数: 9628 | 5 just a gambler's ruin prob.
Chapter
【在 l******i 的大作中提到】 : It reminds me of the famous interview question called "Drunk Man" on Chapter : 5 of Xinfeng Zhou's book.
|
d********t 发帖数: 9628 | 6
same.
【在 d**z 的大作中提到】 : 这个是先于-b到达a的概率。 : 如果限制在n步之内呢?如果n步内没到a就算失败了
|
x******a 发帖数: 6336 | 7 why?
【在 d********t 的大作中提到】 : : same.
|
d********t 发帖数: 9628 | 8
Let k denote the no. of steps to reach either end,
P(a) = P(a|kn)
= P(a|k
【在 x******a 的大作中提到】 : why?
|
A**u 发帖数: 2458 | 9 re 有道理
【在 d********t 的大作中提到】 : : Let k denote the no. of steps to reach either end, : P(a) = P(a|kn) : = P(a|k
|
k*****y 发帖数: 744 | 10 貌似很复杂。
na+1时会咋样?
【在 d**z 的大作中提到】 : 一个random walk : 从 0出发,在n步之内先于-b到达a的概率是多少? : 谢谢各位大牛了~~~
|
|
|
x******a 发帖数: 6336 | 11 why P(a) = P(a|kn)?
【在 d********t 的大作中提到】 : : Let k denote the no. of steps to reach either end, : P(a) = P(a|kn) : = P(a|k
|
a**T 发帖数: 168 | 12 借人气问一题,两维standard BM,从(1,1)开始,问它在hit负x轴之前hit正x轴的
prob.对于这种hit问题基本没辙。。 |
d**z 发帖数: 183 | 13 为什么 P(a) = P(a|kn)? 而且 P(a|k>n)=0?
【在 d********t 的大作中提到】 : : Let k denote the no. of steps to reach either end, : P(a) = P(a|kn) : = P(a|k
|
d**z 发帖数: 183 | 14 关键两个边界的时候 不知道怎么求 p(tau <= n).
【在 k*****y 的大作中提到】 : 貌似很复杂。 : na+1时会咋样?
|
k*****y 发帖数: 744 | 15 uncorrelated的时候,稍微算了一下。
X,Y搞反了...
【在 a**T 的大作中提到】 : 借人气问一题,两维standard BM,从(1,1)开始,问它在hit负x轴之前hit正x轴的 : prob.对于这种hit问题基本没辙。。
|
n****e 发帖数: 629 | 16 Nice deduction.
A simpler solution:
The path will either hit X+ or Y+ first, with equal prob.
If hit Y+ first, the prob of hitting X- first is 1/2.
Therefore the total prob of hitting X- first is 1/2 * 1/2 = 1/4.
【在 k*****y 的大作中提到】 : uncorrelated的时候,稍微算了一下。 : X,Y搞反了...
|
k*****y 发帖数: 744 | 17 good trick
【在 n****e 的大作中提到】 : Nice deduction. : A simpler solution: : The path will either hit X+ or Y+ first, with equal prob. : If hit Y+ first, the prob of hitting X- first is 1/2. : Therefore the total prob of hitting X- first is 1/2 * 1/2 = 1/4.
|
A**u 发帖数: 2458 | 18 good method
【在 n****e 的大作中提到】 : Nice deduction. : A simpler solution: : The path will either hit X+ or Y+ first, with equal prob. : If hit Y+ first, the prob of hitting X- first is 1/2. : Therefore the total prob of hitting X- first is 1/2 * 1/2 = 1/4.
|
l******i 发帖数: 1404 | 19 首先感谢楼主贡献,
如果可以的话,希望楼主最好能在帖子标题里加上问题的类别和关键词,
例如该帖名字可为:【Random Walk】请教一道题
这样方便我们工作人员整理,谢谢啦。
我已经把标题改了。 |
A**u 发帖数: 2458 | 20 请教一下
P(Tx = t) 给出的是 hit x轴概率密度,包括-x, +x
【在 k*****y 的大作中提到】 : uncorrelated的时候,稍微算了一下。 : X,Y搞反了...
|
|
|
k*****y 发帖数: 744 | 21 我写的时候把X,Y搞反了。
\tau_X是第一次hit X=0的时间,也就是第一次hit Y轴的时间。p(\tau_X = t)是第一次hit Y轴时间等于t时的pdf。
当在时间t第一次hit Y轴时,算出P(Y_\tau > 0 | \tau = t) = P(Y_t > 0),再算个
积分就得到所有了。
【在 A**u 的大作中提到】 : 请教一下 : P(Tx = t) 给出的是 hit x轴概率密度,包括-x, +x
|
A**u 发帖数: 2458 | 22 You are right.
一次hit Y轴时间等于t时的pdf。
【在 k*****y 的大作中提到】 : 我写的时候把X,Y搞反了。 : \tau_X是第一次hit X=0的时间,也就是第一次hit Y轴的时间。p(\tau_X = t)是第一次hit Y轴时间等于t时的pdf。 : 当在时间t第一次hit Y轴时,算出P(Y_\tau > 0 | \tau = t) = P(Y_t > 0),再算个 : 积分就得到所有了。
|
d*****o 发帖数: 34 | 23
我是这么想的:
对称的随机徘徊
P(Xi=+1)=P(Xi=-1)=1/2
Yi=(Xi+1)/2
P(Yi=1)=P(Xi=+1)=1/2
P(Yi=0)=P(Xi=-1)=1/2
Yi 是 Bernoulli
Y1+...+Yk 是 Binomial
k步到达a(先于-b)的概率:
当k
P(X1+...+Xk=a)=0
当k>=a时
P(X1+...+Xk=a)=P(Y1+...+Yk=(a+k)/2)=(k,(a+k)/2)*1/2^k, 当a+k是偶数
P(X1+...+Xk=a)=0 当a+k是奇数
n步之内到达a(先于-b)的概率:
(a,(a+a)/2)*1/2^a+(a+1,(a+(a+1))/2)*1/2^(a+1)+...+(n,(a+n)/2)*1/2^n
这个和的close form solution还没搞出来。
【在 d**z 的大作中提到】 : 一个random walk : 从 0出发,在n步之内先于-b到达a的概率是多少? : 谢谢各位大牛了~~~
|
r*******y 发帖数: 1081 | 24 it is
P(a) = P(a|k < n) P(k < n) + P(a|k>n) P(k > n) ?
【在 d********t 的大作中提到】 : : Let k denote the no. of steps to reach either end, : P(a) = P(a|kn) : = P(a|k
|
l******i 发帖数: 1404 | 25 大牛 is really smart.
Could you give some idea for a general case
if the initial position in the original problem has been changed
from (1,1) to (a,b) for any (a,b) value? (with a, b != 0)
【在 n****e 的大作中提到】 : Nice deduction. : A simpler solution: : The path will either hit X+ or Y+ first, with equal prob. : If hit Y+ first, the prob of hitting X- first is 1/2. : Therefore the total prob of hitting X- first is 1/2 * 1/2 = 1/4.
|
k*****y 发帖数: 744 | 26 我的方法好像可以推广到从(a,b)出发。
【在 l******i 的大作中提到】 : 大牛 is really smart. : Could you give some idea for a general case : if the initial position in the original problem has been changed : from (1,1) to (a,b) for any (a,b) value? (with a, b != 0)
|
l******i 发帖数: 1404 | 27 yeah, you are right.
Could you please let me know which page of Shreve
introduce the pdf for the hitting time of a Wiener process?
Thx.
【在 k*****y 的大作中提到】 : 我的方法好像可以推广到从(a,b)出发。
|
k*****y 发帖数: 744 | 28 p.151
【在 l******i 的大作中提到】 : yeah, you are right. : Could you please let me know which page of Shreve : introduce the pdf for the hitting time of a Wiener process? : Thx.
|
n****e 发帖数: 629 | 29 不是大牛,谢谢。
其实也是能做的。和原点连根线,显然角度是martingale. 所以先hit Y+的概率是
arctan(y/x)/[arctan(y/x)+arctan(x/y)]。接下来做法类似。
【在 l******i 的大作中提到】 : 大牛 is really smart. : Could you give some idea for a general case : if the initial position in the original problem has been changed : from (1,1) to (a,b) for any (a,b) value? (with a, b != 0)
|
A**u 发帖数: 2458 | 30 大牛 解释解释 看不懂
【在 n****e 的大作中提到】 : 不是大牛,谢谢。 : 其实也是能做的。和原点连根线,显然角度是martingale. 所以先hit Y+的概率是 : arctan(y/x)/[arctan(y/x)+arctan(x/y)]。接下来做法类似。
|
|
|
n****e 发帖数: 629 | 31 Apparently I was stupid. The answer is just arctan(a/b)/pi. Sorry for the
messy math.
【在 n****e 的大作中提到】 : 不是大牛,谢谢。 : 其实也是能做的。和原点连根线,显然角度是martingale. 所以先hit Y+的概率是 : arctan(y/x)/[arctan(y/x)+arctan(x/y)]。接下来做法类似。
|
l******i 发帖数: 1404 | 32 恕我愚钝,
角度是martingale,但为啥hit Y+的概率是arctan(y/x)/[arctan(y/x)+arctan(x/y)]。
能具体证明一下不?
谢谢哈。
【在 n****e 的大作中提到】 : 不是大牛,谢谢。 : 其实也是能做的。和原点连根线,显然角度是martingale. 所以先hit Y+的概率是 : arctan(y/x)/[arctan(y/x)+arctan(x/y)]。接下来做法类似。
|
k*****y 发帖数: 744 | 33 跟Wienner Process从0出发先在-b之前先hit a的martigale算法一样。前提只要知道以1的概率会hit到boundary。
总结一下native的结果:
设(a,b)到X+的夹角是A(取小于\pi的那个),那么(a,b)到X-的夹角是\pi - A。由于(a,b)的角度是martigale,我们就得到
P(hit X+) = (\pi - A) / ((\pi - A) + A) = (\pi - A) /\pi
P(hit X-) = A/ ((\pi-A) + A) = A/pi.
admire native大牛! 现在很清楚了。
]。
【在 l******i 的大作中提到】 : 恕我愚钝, : 角度是martingale,但为啥hit Y+的概率是arctan(y/x)/[arctan(y/x)+arctan(x/y)]。 : 能具体证明一下不? : 谢谢哈。
|
R**T 发帖数: 784 | 34 恩,关键要能看到角度是martingale
赞各位大牛的讨论,还有版三的辛勤工作
现在版上好有营养,以前每天就五分钟批阅下,这几天都看好久
道以1的概率会hit到boundary。
于(a,b)的角度是martigale,我们就得到
【在 k*****y 的大作中提到】 : 跟Wienner Process从0出发先在-b之前先hit a的martigale算法一样。前提只要知道以1的概率会hit到boundary。 : 总结一下native的结果: : 设(a,b)到X+的夹角是A(取小于\pi的那个),那么(a,b)到X-的夹角是\pi - A。由于(a,b)的角度是martigale,我们就得到 : P(hit X+) = (\pi - A) / ((\pi - A) + A) = (\pi - A) /\pi : P(hit X-) = A/ ((\pi-A) + A) = A/pi. : admire native大牛! 现在很清楚了。 : : ]。
|
A**u 发帖数: 2458 | 35 为啥 角度是martingale
道以1的概率会hit到boundary。
于(a,b)的角度是martigale,我们就得到
【在 k*****y 的大作中提到】 : 跟Wienner Process从0出发先在-b之前先hit a的martigale算法一样。前提只要知道以1的概率会hit到boundary。 : 总结一下native的结果: : 设(a,b)到X+的夹角是A(取小于\pi的那个),那么(a,b)到X-的夹角是\pi - A。由于(a,b)的角度是martigale,我们就得到 : P(hit X+) = (\pi - A) / ((\pi - A) + A) = (\pi - A) /\pi : P(hit X-) = A/ ((\pi-A) + A) = A/pi. : admire native大牛! 现在很清楚了。 : : ]。
|
R**T 发帖数: 784 | 36 对称性啊,角度是A的话,增加dphi和减小dphi的概率一样吧?
【在 A**u 的大作中提到】 : 为啥 角度是martingale : : 道以1的概率会hit到boundary。 : 于(a,b)的角度是martigale,我们就得到
|
A**u 发帖数: 2458 | 37 大牛啊 明白了
【在 R**T 的大作中提到】 : 对称性啊,角度是A的话,增加dphi和减小dphi的概率一样吧?
|
k*****y 发帖数: 744 | 38 不信的话,可以用Ito lemma来算d( arctan(Y_T/X_T) ),(dY_T)^2跟(dX_T)^2两项刚
好抵消。
【在 A**u 的大作中提到】 : 为啥 角度是martingale : : 道以1的概率会hit到boundary。 : 于(a,b)的角度是martigale,我们就得到
|
l******i 发帖数: 1404 | 39 kinecty大牛方法虽然不是简便的,但也无疑是正确的,普适的。
我有个蠢问题:
\tau_X=第一次hit Y 轴的时间,
Y是第一次hit的位置。
为啥\tau_X和Y是independent的?
【在 k*****y 的大作中提到】 : uncorrelated的时候,稍微算了一下。 : X,Y搞反了...
|
k*****y 发帖数: 744 | 40 我假定X,Y是independent的,所以\tau_X只依赖X跟Y是独立的。
【在 l******i 的大作中提到】 : kinecty大牛方法虽然不是简便的,但也无疑是正确的,普适的。 : 我有个蠢问题: : \tau_X=第一次hit Y 轴的时间, : Y是第一次hit的位置。 : 为啥\tau_X和Y是independent的?
|
|
|
l******i 发帖数: 1404 | 41 我按我的理解解释一下:
\tau_X是第一次hit X=0的时间,也就是第一次hit Y轴的时间。
Y_t是第一次hit Y轴时的Y位置。
那么那个关于p(Y_t > 0 | \tau = t)*p(\tau = t)的积分应该算的是
第一次hit Y轴时hit到Y正轴的概率。
kinecty大牛是这个意思不?
您后来把积分里面写成p(Y_t > 0 | \tau = t)*p(\tau = t)我就明白了,
对于一开始的p(Y_t > 0 , \tau = t)=p(Y_t > 0)*p(\tau = t)我愣了一下下。
【在 k*****y 的大作中提到】 : 我假定X,Y是independent的,所以\tau_X只依赖X跟Y是独立的。
|
k*****y 发帖数: 744 | 42 (X_t, Y_t)是在t时刻(X,Y)的值。所以Y_\tau是在\tau时刻Y的值,也就是当X第一次等
于 0,hit到Y轴时候Y的值。(不知道说清楚了没...)
准确点应该写成p(Y_\tau > 0, \tau = t) = p(Y_t > 0, \tau = t),然后因为Y_t跟\
tau独立,所以可以拆成product。
【在 l******i 的大作中提到】 : 我按我的理解解释一下: : \tau_X是第一次hit X=0的时间,也就是第一次hit Y轴的时间。 : Y_t是第一次hit Y轴时的Y位置。 : 那么那个关于p(Y_t > 0 | \tau = t)*p(\tau = t)的积分应该算的是 : 第一次hit Y轴时hit到Y正轴的概率。 : kinecty大牛是这个意思不? : 您后来把积分里面写成p(Y_t > 0 | \tau = t)*p(\tau = t)我就明白了, : 对于一开始的p(Y_t > 0 , \tau = t)=p(Y_t > 0)*p(\tau = t)我愣了一下下。
|