x********o
发帖数: 519 | 1 A person is one step from the cliff. He does a random walk with
probability 1/3 towards the cliff. What is
the probability that he will eventually fall off the cliff
is the answer 1/2? |
s**********y
发帖数: 353 | 2 if one step from the cliff means he falls after he makes one step, I think
the answer is 1/2, otherwise it is 1/4.
【在 x********o 的大作中提到】
: A person is one step from the cliff. He does a random walk with
: probability 1/3 towards the cliff. What is
: the probability that he will eventually fall off the cliff
: is the answer 1/2?
|
j******n
发帖数: 271 | |
c**********e
发帖数: 2007 | 4 1/2 is correct.
【在 x********o 的大作中提到】
: A person is one step from the cliff. He does a random walk with
: probability 1/3 towards the cliff. What is
: the probability that he will eventually fall off the cliff
: is the answer 1/2?
|
r*******y
发帖数: 1081 | 5 got p(n) - p(n+1) = (1/2)(1 - p(1))
how to find p(1) ?
【在 x********o 的大作中提到】
: A person is one step from the cliff. He does a random walk with
: probability 1/3 towards the cliff. What is
: the probability that he will eventually fall off the cliff
: is the answer 1/2?
|
l*******l
发帖数: 248 | 6 说说过程。。。
【在 c**********e 的大作中提到】
: 1/2 is correct.
|
S*********g
发帖数: 5298 | 7 P(1->0)=1/3 + 2/3 P(2->0) = 1/3 + 2/3 * [P(1->0)]^2
=> 2x^2 - 3x + 1 = 0 => (2x-1)(x-1)=0 => x=1/2
【在 l*******l 的大作中提到】
: 说说过程。。。
|
r*******y
发帖数: 1081 | 8 nice
【在 S*********g 的大作中提到】
: P(1->0)=1/3 + 2/3 P(2->0) = 1/3 + 2/3 * [P(1->0)]^2
: => 2x^2 - 3x + 1 = 0 => (2x-1)(x-1)=0 => x=1/2
|
m****u
发帖数: 37 | 9 3/7
p(1->0)=3/7
p(2->0)=1/7 |
x********o
发帖数: 519 | 10 can you explain it?
【在 m****u 的大作中提到】
: 3/7
: p(1->0)=3/7
: p(2->0)=1/7
|
|
|
w*********m
发帖数: 196 | 11 p=1/3+2/3*p^2
solve p=1 or 1/2
p=1/2 |
m****u
发帖数: 37 | 12 1/3+(1/3)*[(1/3)*(2/3)]+(1/3)*[(1/3)*(2/3)]^2+(1/3)*[(1/3)*(2/3)]^3+.....=
(1/3)*[1/(1-2/9)]=3/7
在 xiaozhuluo (Xiao Zhu Luo) 的大作中提到: 】 |
l*******l
发帖数: 248 | 13 this is NOT the right one
【在 m****u 的大作中提到】
: 1/3+(1/3)*[(1/3)*(2/3)]+(1/3)*[(1/3)*(2/3)]^2+(1/3)*[(1/3)*(2/3)]^3+.....=
: (1/3)*[1/(1-2/9)]=3/7
: 在 xiaozhuluo (Xiao Zhu Luo) 的大作中提到: 】
|
x********o
发帖数: 519 | 14 are you sure?
do you have any reference on this problem?
I think the answer should be 1/2
【在 l*******l 的大作中提到】
: this is NOT the right one
|
l*******l
发帖数: 248 | 15 打错了。。。。是1/2
想说那个是不对的。。lol
【在 x********o 的大作中提到】
: are you sure?
: do you have any reference on this problem?
: I think the answer should be 1/2
|
c**********s
发帖数: 295 | 16 this is a standard random walk with drift problem.
the equation listed above is simple but not the best solution. what if the
boundary is not 1 but 10. |
x********o
发帖数: 519 | 17 good point.
then what will be the solution?
【在 c**********s 的大作中提到】
: this is a standard random walk with drift problem.
: the equation listed above is simple but not the best solution. what if the
: boundary is not 1 but 10.
|
l*******l
发帖数: 248 | 18 (1/2)^10
【在 x********o 的大作中提到】
: good point.
: then what will be the solution?
|
a******e
发帖数: 710 | 19 Why P(2-> 0) = P(1->0)^2
thanks
【在 S*********g 的大作中提到】
: P(1->0)=1/3 + 2/3 P(2->0) = 1/3 + 2/3 * [P(1->0)]^2
: => 2x^2 - 3x + 1 = 0 => (2x-1)(x-1)=0 => x=1/2
|
o*p
发帖数: 77 | 20 1/4
【在 x********o 的大作中提到】
: A person is one step from the cliff. He does a random walk with
: probability 1/3 towards the cliff. What is
: the probability that he will eventually fall off the cliff
: is the answer 1/2?
|
|
|
e******0
发帖数: 211 | 21 P(2->0) = P(2->1)P(1->0)
P(2->1)=P(1->0)
【在 a******e 的大作中提到】
: Why P(2-> 0) = P(1->0)^2
: thanks
|
S*********g
发帖数: 5298 | 22 gambler's ruin
【在 c**********s 的大作中提到】
: this is a standard random walk with drift problem.
: the equation listed above is simple but not the best solution. what if the
: boundary is not 1 but 10.
|
s**********y
发帖数: 353 | 23 It is still a gamler's ruin problem. You just take the other end to infinity
.
【在 x********o 的大作中提到】
: good point.
: then what will be the solution?
|
c**********s
发帖数: 295 | 24 it is the gambler's ruin, that is why i said it is a very standard question.
i prefer to solve it by moving it to the exp space so that it connects to
the continues case better and also there is no linear equation set to mess
around. |
s**********y
发帖数: 353 | 25 Are you talking about exp martingale? How to connect this problem to
continuous space? Can you elaborate more on your approach?
question.
【在 c**********s 的大作中提到】
: it is the gambler's ruin, that is why i said it is a very standard question.
: i prefer to solve it by moving it to the exp space so that it connects to
: the continues case better and also there is no linear equation set to mess
: around.
|
f**a
发帖数: 2498 | 26 喜粉鸡一是对滴。耳粪妓一是不对滴。
you have to go one step further to fall over, ie S_n = -2.
also you need a little extra argument to show stopping time (S_n = -2 is an
absorbing state) is finite almost sure. this essentially exclude the
possibility for solution x=1.
【在 x********o 的大作中提到】
: A person is one step from the cliff. He does a random walk with
: probability 1/3 towards the cliff. What is
: the probability that he will eventually fall off the cliff
: is the answer 1/2?
|
a******e
发帖数: 710 | 27 Thanks. Do you know any books talking about this kind of problem?
【在 e******0 的大作中提到】
: P(2->0) = P(2->1)P(1->0)
: P(2->1)=P(1->0)
|
c**********s
发帖数: 295 | 28 the same as you solve the continuous case,
y=exp(lambda*x) and solve lambda so that y is a martingale.
【在 s**********y 的大作中提到】
: Are you talking about exp martingale? How to connect this problem to
: continuous space? Can you elaborate more on your approach?
:
: question.
|
n*********u
发帖数: 34 | 29 大家说的都好高深，有没有人帮我看看这个最初等的解法有什么问题，先有个假设，如
果n步不是迈向悬崖，那么必须要向悬崖走(n+1)步才能掉下去，这里好像假设了是直路
，然后各种走法概率求和：
1/3+2/3*(1/3)^2+(2/3)^2*(1/3)^3+...=3/7 |
r*******y
发帖数: 1081 | 30 suppose cliff is indexed 0, and from left on we index the points as 1, 2, 3,
...
suppose we are at point 2, then your question is whether the probability to
get
off the cliff is (1/3)^2 starting at point 2.
But this probability should be bigger than (1/3)^2, because besides the way
2-1-0, we have other ways like 2-1-2-1-0,...
To use your idea, the correct equation should be
1/3 + 2/3 * p(2) + (2/3)^2 p(3) + (2/3)^3 p(3) + ....
where p(n) = (p(1))^n.
If we plugin p(1) = 1/ 2, we can find the sum above also equals 1/2. But we
can not determine what p(1) is here.
【在 n*********u 的大作中提到】
: 大家说的都好高深，有没有人帮我看看这个最初等的解法有什么问题，先有个假设，如
: 果n步不是迈向悬崖，那么必须要向悬崖走(n+1)步才能掉下去，这里好像假设了是直路
: ，然后各种走法概率求和：
: 1/3+2/3*(1/3)^2+(2/3)^2*(1/3)^3+...=3/7
|
|
|
n*********u
发帖数: 34 | 31 Thank you very much for the detailed explanation!
3,
to
way
【在 r*******y 的大作中提到】
: suppose cliff is indexed 0, and from left on we index the points as 1, 2, 3,
: ...
: suppose we are at point 2, then your question is whether the probability to
: get
: off the cliff is (1/3)^2 starting at point 2.
: But this probability should be bigger than (1/3)^2, because besides the way
: 2-1-0, we have other ways like 2-1-2-1-0,...
: To use your idea, the correct equation should be
: 1/3 + 2/3 * p(2) + (2/3)^2 p(3) + (2/3)^3 p(3) + ....
: where p(n) = (p(1))^n.
|
p*******p
发帖数: 94 | 32 X_(n+1)=X_(n)+/-1
Head: +1 with probability p
Tail: -1 with probability q
Martingale: (q/p)^X_n
Martingale stopped at stopping time is a martingale.
left bound: -1
right bound: +inf
1=(q/p)^X_0=(1/2)^0=(1/2)^(-1)*P+0*(1-P)
P=1/2
or
1=(q/p)^X_0=(1/2)^0=(1/2)^(-2)*P+0*(1-P)
P=1/4 |
k**u
发帖数: 60 | 33 1/2:
P(0)=1;
p(1)=1/3*p(0)+2/3*p(2);
p(1)-p(0)=2*(p(2)-p(1));
assume P(N)=0;
so p(1)=1/2
anyway P(1)=1/3*p(0)+ 2/3*P(1)*P(1) is smart.
btw feel this is somehow related to stopped martingale is still a martingale, anyone has the same feeling? |
L**********u
发帖数: 194 | 34 这题的结果就是1/2. 用 markov chain 做。 |
