o****e
发帖数: 80 | 1 Suppose you have a coin in which the probability of flipping a heads is p,
where p>=0.5 . What is the expected number of flips it will take for the
number of heads to equal the number of tails, assuming the first flip is a
tail?
answer is like this;
Think of the problem as a random walk where the probability is p of moving
to the left and 1-p of moving to the right. The expected change in the
position on the number line per move is p*(+1) + (1-p)*(-1) = 2p-1. The
first flip resulted in moving on |
z****g
发帖数: 1978 | 2 try to think in terms of Markov chain
is p,
the
is a
moving
The
number of
movement
【在 o****e 的大作中提到】
: Suppose you have a coin in which the probability of flipping a heads is p,
: where p>=0.5 . What is the expected number of flips it will take for the
: number of heads to equal the number of tails, assuming the first flip is a
: tail?
: answer is like this;
: Think of the problem as a random walk where the probability is p of moving
: to the left and 1-p of moving to the right. The expected change in the
: position on the number line per move is p*(+1) + (1-p)*(-1) = 2p-1. The
: first flip resulted in moving on
|
z****i
发帖数: 406 | 3 还挺严谨的吧。
最后一步用的是Wald's equation.
a Markov approach:
Let the desired expectation be E, then
E = p*1 + (1-p)*(2E+1)
of
movement
【在 o****e 的大作中提到】
: Suppose you have a coin in which the probability of flipping a heads is p,
: where p>=0.5 . What is the expected number of flips it will take for the
: number of heads to equal the number of tails, assuming the first flip is a
: tail?
: answer is like this;
: Think of the problem as a random walk where the probability is p of moving
: to the left and 1-p of moving to the right. The expected change in the
: position on the number line per move is p*(+1) + (1-p)*(-1) = 2p-1. The
: first flip resulted in moving on
|
o****e
发帖数: 80 | 4 谢谢，
E = p*1 + (1-p)*(2E+1)
--
这里为什么是2E?
【在 z****i 的大作中提到】
: 还挺严谨的吧。
: 最后一步用的是Wald's equation.
: a Markov approach:
: Let the desired expectation be E, then
: E = p*1 + (1-p)*(2E+1)
:
: of
: movement
|
z****i
发帖数: 406 | 5 with probability p, you move from -1 to 0, so the number of flips is 1;
with probability 1-p, you move from -1 to -2, and the expected number of
flips is 2*E, because you need E flips to get -1 first, then you need
another E to get to 0 from -1.
【在 o****e 的大作中提到】
: 谢谢，
: E = p*1 + (1-p)*(2E+1)
: --
: 这里为什么是2E?
|
o****e
发帖数: 80 | 6 明白了，谢谢，再请教一道题
Assuming you flipped a coin until over and over, keeping track of the number
of both heads and tails flipped, what is the expected number of flips
before the two totals were equal?
The answer is infinity.
这两道题，我没看出来有什么不一样，为什么答案不同？
【在 z****i 的大作中提到】
: with probability p, you move from -1 to 0, so the number of flips is 1;
: with probability 1-p, you move from -1 to -2, and the expected number of
: flips is 2*E, because you need E flips to get -1 first, then you need
: another E to get to 0 from -1.
|
z****i
发帖数: 406 | 7 你前一道题假设了the first flip is a tail.
你可以想像成带drift的brownian motion.
你前一道题，这个过程从-1开始，因为drift是正的，所以能在有限时间内到达0；
后一道题，过程从0开始，回到0点的expected time 是infinity.
number
【在 o****e 的大作中提到】
: 明白了，谢谢，再请教一道题
: Assuming you flipped a coin until over and over, keeping track of the number
: of both heads and tails flipped, what is the expected number of flips
: before the two totals were equal?
: The answer is infinity.
: 这两道题，我没看出来有什么不一样，为什么答案不同？
|
b******e
发帖数: 118 | 8 如果用Wald's equation， 为什么E[Sn]＝1呢？我的理解是如果最终head和tail的数目
一样，E[Sn]不应该是0吗？但现在有已知条件，第一次flip是tail，这个怎么考虑进去？
【在 z****i 的大作中提到】
: 还挺严谨的吧。
: 最后一步用的是Wald's equation.
: a Markov approach:
: Let the desired expectation be E, then
: E = p*1 + (1-p)*(2E+1)
:
: of
: movement
|
z****i
发帖数: 406 | 9 Let Sn be (# of heads - # of tails) after the 1st flip.
Then when the process stops, Sn = 1.
去？
【在 b******e 的大作中提到】
: 如果用Wald's equation， 为什么E[Sn]＝1呢？我的理解是如果最终head和tail的数目
: 一样，E[Sn]不应该是0吗？但现在有已知条件，第一次flip是tail，这个怎么考虑进去？
|
b******e
发帖数: 118 | 10 这样考虑的话，最终的flip的期望值应该是1/(2p-1)+1，即还加上第一次flip？这样想
对不？
【在 z****i 的大作中提到】
: Let Sn be (# of heads - # of tails) after the 1st flip.
: Then when the process stops, Sn = 1.
:
: 去？
|
|
|
z****i
发帖数: 406 | 11 对
【在 b******e 的大作中提到】
: 这样考虑的话，最终的flip的期望值应该是1/(2p-1)+1，即还加上第一次flip？这样想
: 对不？
|
v*******o
发帖数: 10 | 12 if so, what is E[x] in wald's equality? 2p-1 is the expected change for one
flip, E[Sn] should be expected change too? can you explain more details of
wald's equation?
【在 z****i 的大作中提到】
: Let Sn be (# of heads - # of tails) after the 1st flip.
: Then when the process stops, Sn = 1.
:
: 去？
|
z****i
发帖数: 406 | 13 x_i = 1 with probability p;
= -1 with probability 1-p.
so E[x_i] = 2p-1 for each i, i.e, each flip.
The process stops when \sum x_i = 1.
S_n = \sum_i^n x_i
where n is the stopping time, i.e., # of flips when S_n = 1.
We know at stopping time n, S_n = 1.
apply Wald's equation,
1=S_n = E(S_n) = E(n) *E(x_i)
we have E(n) = 1/(2p-1).
one
【在 v*******o 的大作中提到】
: if so, what is E[x] in wald's equality? 2p-1 is the expected change for one
: flip, E[Sn] should be expected change too? can you explain more details of
: wald's equation?
|
v*******o
发帖数: 10 | 14 Thanks a lot!!! I see, the initial position is -1, that's why S[n] = 1.
Correct me please if I am wrong!
【在 z****i 的大作中提到】
: x_i = 1 with probability p;
: = -1 with probability 1-p.
: so E[x_i] = 2p-1 for each i, i.e, each flip.
: The process stops when \sum x_i = 1.
: S_n = \sum_i^n x_i
: where n is the stopping time, i.e., # of flips when S_n = 1.
: We know at stopping time n, S_n = 1.
: apply Wald's equation,
: 1=S_n = E(S_n) = E(n) *E(x_i)
: we have E(n) = 1/(2p-1).
|
o*p
发帖数: 77 | 15 我有个疑问.
如果p<1/2,
按这样分析还对吗?那答案不就是负的了吗?
按照brown motion, the drift is negative.
但是我们仍然可以用构造殃的方法算出flips coin 数的期望值.
of
movement
【在 o****e 的大作中提到】
: Suppose you have a coin in which the probability of flipping a heads is p,
: where p>=0.5 . What is the expected number of flips it will take for the
: number of heads to equal the number of tails, assuming the first flip is a
: tail?
: answer is like this;
: Think of the problem as a random walk where the probability is p of moving
: to the left and 1-p of moving to the right. The expected change in the
: position on the number line per move is p*(+1) + (1-p)*(-1) = 2p-1. The
: first flip resulted in moving on
|
