Mixing
Expected number of tail before $T_M$.
Clash Royale CLAN TAG#URR8PPP
up vote
0
down vote
favorite
We flip a coin with head probability $p$. Before the game starts, we have 1 dollars. Each time we flip the coin, if it's head, then our fortune increases by 1; if it's tail, then our fortune returns to 1. Let $S_i$ be our fortune at $i$-th trial (so $S_0 = 1$).
Let $T_M = minlefti: S_i = M right$. Find the expected value of tails before $T_M$, $mathbbEleft[ sum_i=1^T_M 1_Tailright]$
I tried to use Wald's identity since $T_M$ is a stopping time, but I still need to find $mathbbEleft[T_Mright]$. I'm not sure how to find it. My vague thought is to use geometric random variable, with the event "getting $M-1$ heads in row" as success (having probability $p^M-1$), but I'm not sure how to proceed.
probability probability-theory stochastic-processes markov-chains markov-process
asked Jul 18 at 22:02
3x89g2
3,8251932
 |Â
show 2 more comments
up vote
0
down vote
favorite
We flip a coin with head probability $p$. Before the game starts, we have 1 dollars. Each time we flip the coin, if it's head, then our fortune increases by 1; if it's tail, then our fortune returns to 1. Let $S_i$ be our fortune at $i$-th trial (so $S_0 = 1$).
Let $T_M = minlefti: S_i = M right$. Find the expected value of tails before $T_M$, $mathbbEleft[ sum_i=1^T_M 1_Tailright]$
I tried to use Wald's identity since $T_M$ is a stopping time, but I still need to find $mathbbEleft[T_Mright]$. I'm not sure how to find it. My vague thought is to use geometric random variable, with the event "getting $M-1$ heads in row" as success (having probability $p^M-1$), but I'm not sure how to proceed.
probability probability-theory stochastic-processes markov-chains markov-process
asked Jul 18 at 22:02
3x89g2
3,8251932
math.stackexchange.com/questions/1672956/…
– d.k.o.
Jul 18 at 22:36
@d.k.o. In this problem, tails returns you back to 1, so this is not a random walk.
– E-A
Jul 18 at 22:42
@d.k.o. In asymmetric random walk, the sum either goes up or down by 1. (So, if I have 5 mesos at time $i$, I would now have 4 or 6 mesos.) Here, tails takes you back to 1. (So, I either have 6 mesos or one meso)
– E-A
Jul 18 at 22:46
1
@E.A. Oh, I misread the question!
– d.k.o.
Jul 18 at 22:46
Also OP, yes, your intuition should work; you will have success after on average $p^-(M-1)$ streaks of heads, and number of expected trials is precisely the number of tails you have.
– E-A
Jul 18 at 22:50
 |Â
show 2 more comments
up vote
0
down vote
favorite
up vote
0
down vote
favorite
We flip a coin with head probability $p$. Before the game starts, we have 1 dollars. Each time we flip the coin, if it's head, then our fortune increases by 1; if it's tail, then our fortune returns to 1. Let $S_i$ be our fortune at $i$-th trial (so $S_0 = 1$).
Let $T_M = minlefti: S_i = M right$. Find the expected value of tails before $T_M$, $mathbbEleft[ sum_i=1^T_M 1_Tailright]$
I tried to use Wald's identity since $T_M$ is a stopping time, but I still need to find $mathbbEleft[T_Mright]$. I'm not sure how to find it. My vague thought is to use geometric random variable, with the event "getting $M-1$ heads in row" as success (having probability $p^M-1$), but I'm not sure how to proceed.
probability probability-theory stochastic-processes markov-chains markov-process
asked Jul 18 at 22:02
3x89g2
3,8251932
We flip a coin with head probability $p$. Before the game starts, we have 1 dollars. Each time we flip the coin, if it's head, then our fortune increases by 1; if it's tail, then our fortune returns to 1. Let $S_i$ be our fortune at $i$-th trial (so $S_0 = 1$).
Let $T_M = minlefti: S_i = M right$. Find the expected value of tails before $T_M$, $mathbbEleft[ sum_i=1^T_M 1_Tailright]$
I tried to use Wald's identity since $T_M$ is a stopping time, but I still need to find $mathbbEleft[T_Mright]$. I'm not sure how to find it. My vague thought is to use geometric random variable, with the event "getting $M-1$ heads in row" as success (having probability $p^M-1$), but I'm not sure how to proceed.
probability probability-theory stochastic-processes markov-chains markov-process
asked Jul 18 at 22:02
3x89g2
3,8251932
asked Jul 18 at 22:02
3x89g2
3,8251932
asked Jul 18 at 22:02
3x89g2
3,8251932
asked Jul 18 at 22:02
3x89g2
3,8251932
3,8251932
math.stackexchange.com/questions/1672956/…
– d.k.o.
Jul 18 at 22:36
@d.k.o. In this problem, tails returns you back to 1, so this is not a random walk.
– E-A
Jul 18 at 22:42
@d.k.o. In asymmetric random walk, the sum either goes up or down by 1. (So, if I have 5 mesos at time $i$, I would now have 4 or 6 mesos.) Here, tails takes you back to 1. (So, I either have 6 mesos or one meso)
– E-A
Jul 18 at 22:46
1
@E.A. Oh, I misread the question!
– d.k.o.
Jul 18 at 22:46
Also OP, yes, your intuition should work; you will have success after on average $p^-(M-1)$ streaks of heads, and number of expected trials is precisely the number of tails you have.
– E-A
Jul 18 at 22:50
 |Â
show 2 more comments
math.stackexchange.com/questions/1672956/…
– d.k.o.
Jul 18 at 22:36
@d.k.o. In this problem, tails returns you back to 1, so this is not a random walk.
– E-A
Jul 18 at 22:42
@d.k.o. In asymmetric random walk, the sum either goes up or down by 1. (So, if I have 5 mesos at time $i$, I would now have 4 or 6 mesos.) Here, tails takes you back to 1. (So, I either have 6 mesos or one meso)
– E-A
Jul 18 at 22:46
1
@E.A. Oh, I misread the question!
– d.k.o.
Jul 18 at 22:46
Also OP, yes, your intuition should work; you will have success after on average $p^-(M-1)$ streaks of heads, and number of expected trials is precisely the number of tails you have.
– E-A
Jul 18 at 22:50
math.stackexchange.com/questions/1672956/…
– d.k.o.
Jul 18 at 22:36
math.stackexchange.com/questions/1672956/…
– d.k.o.
Jul 18 at 22:36
@d.k.o. In this problem, tails returns you back to 1, so this is not a random walk.
– E-A
Jul 18 at 22:42
@d.k.o. In this problem, tails returns you back to 1, so this is not a random walk.
– E-A
Jul 18 at 22:42
@d.k.o. In asymmetric random walk, the sum either goes up or down by 1. (So, if I have 5 mesos at time $i$, I would now have 4 or 6 mesos.) Here, tails takes you back to 1. (So, I either have 6 mesos or one meso)
– E-A
Jul 18 at 22:46
@d.k.o. In asymmetric random walk, the sum either goes up or down by 1. (So, if I have 5 mesos at time $i$, I would now have 4 or 6 mesos.) Here, tails takes you back to 1. (So, I either have 6 mesos or one meso)
– E-A
Jul 18 at 22:46
1
1
@E.A. Oh, I misread the question!
– d.k.o.
Jul 18 at 22:46
@E.A. Oh, I misread the question!
– d.k.o.
Jul 18 at 22:46
Also OP, yes, your intuition should work; you will have success after on average $p^-(M-1)$ streaks of heads, and number of expected trials is precisely the number of tails you have.
– E-A
Jul 18 at 22:50
Also OP, yes, your intuition should work; you will have success after on average $p^-(M-1)$ streaks of heads, and number of expected trials is precisely the number of tails you have.
– E-A
Jul 18 at 22:50
 |Â
show 2 more comments
1 Answer
1
active
oldest
votes
up vote
0
down vote
accepted
It requires $M-1$ consecutive heads to stop. The expected number of steps until $M-1$ consecutive heads is given by
$$
mathsfET_M=fracp^-M+1-11-p.
$$
Then the expected number of tails is $(1-p)mathsfET_M=p^-M+1-1$.
answered Jul 18 at 23:55
d.k.o.
7,709526
But the correct answer is $frac1 - p^M-1p^M-1$
– 3x89g2
Jul 19 at 2:45
@3x89g2 Indeed, $$ frac1-p^M-1p^M-1=p^-M+1-1. $$
– d.k.o.
Jul 19 at 3:11
Sorry. I meant, how do we get $E T_M$? Why $fracp^-M+1 - 11-p$?
– 3x89g2
Jul 19 at 3:15
@3x89g2 If $E_n$ is the average number of steps until the first run of $n$ heads, then it satisfies the following relation: beginalign E_n&=(1-p)(1+E_n)+p(1-p)(2+E_n)+cdots+p^nn \ &=E_n-p^nE_n+sum_k=0^n-1p^k. endalign So $$ E_n=sum_k=0^n-1fracp^kp^n=fracp^-n-11-p. $$
– d.k.o.
Jul 19 at 3:29
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
0
down vote
accepted
It requires $M-1$ consecutive heads to stop. The expected number of steps until $M-1$ consecutive heads is given by
$$
mathsfET_M=fracp^-M+1-11-p.
$$
Then the expected number of tails is $(1-p)mathsfET_M=p^-M+1-1$.
answered Jul 18 at 23:55
d.k.o.
7,709526
But the correct answer is $frac1 - p^M-1p^M-1$
– 3x89g2
Jul 19 at 2:45
@3x89g2 Indeed, $$ frac1-p^M-1p^M-1=p^-M+1-1. $$
– d.k.o.
Jul 19 at 3:11
Sorry. I meant, how do we get $E T_M$? Why $fracp^-M+1 - 11-p$?
– 3x89g2
Jul 19 at 3:15
@3x89g2 If $E_n$ is the average number of steps until the first run of $n$ heads, then it satisfies the following relation: beginalign E_n&=(1-p)(1+E_n)+p(1-p)(2+E_n)+cdots+p^nn \ &=E_n-p^nE_n+sum_k=0^n-1p^k. endalign So $$ E_n=sum_k=0^n-1fracp^kp^n=fracp^-n-11-p. $$
– d.k.o.
Jul 19 at 3:29
add a comment |Â
up vote
0
down vote
accepted
It requires $M-1$ consecutive heads to stop. The expected number of steps until $M-1$ consecutive heads is given by
$$
mathsfET_M=fracp^-M+1-11-p.
$$
Then the expected number of tails is $(1-p)mathsfET_M=p^-M+1-1$.
answered Jul 18 at 23:55
d.k.o.
7,709526
But the correct answer is $frac1 - p^M-1p^M-1$
– 3x89g2
Jul 19 at 2:45
@3x89g2 Indeed, $$ frac1-p^M-1p^M-1=p^-M+1-1. $$
– d.k.o.
Jul 19 at 3:11
Sorry. I meant, how do we get $E T_M$? Why $fracp^-M+1 - 11-p$?
– 3x89g2
Jul 19 at 3:15
@3x89g2 If $E_n$ is the average number of steps until the first run of $n$ heads, then it satisfies the following relation: beginalign E_n&=(1-p)(1+E_n)+p(1-p)(2+E_n)+cdots+p^nn \ &=E_n-p^nE_n+sum_k=0^n-1p^k. endalign So $$ E_n=sum_k=0^n-1fracp^kp^n=fracp^-n-11-p. $$
– d.k.o.
Jul 19 at 3:29
add a comment |Â
up vote
0
down vote
accepted
up vote
0
down vote
accepted
It requires $M-1$ consecutive heads to stop. The expected number of steps until $M-1$ consecutive heads is given by
$$
mathsfET_M=fracp^-M+1-11-p.
$$
Then the expected number of tails is $(1-p)mathsfET_M=p^-M+1-1$.
answered Jul 18 at 23:55
d.k.o.
7,709526
It requires $M-1$ consecutive heads to stop. The expected number of steps until $M-1$ consecutive heads is given by
$$
mathsfET_M=fracp^-M+1-11-p.
$$
Then the expected number of tails is $(1-p)mathsfET_M=p^-M+1-1$.
answered Jul 18 at 23:55
d.k.o.
7,709526
edited Jul 19 at 3:12
answered Jul 18 at 23:55
d.k.o.
7,709526
answered Jul 18 at 23:55
d.k.o.
7,709526
answered Jul 18 at 23:55
d.k.o.
7,709526
7,709526
But the correct answer is $frac1 - p^M-1p^M-1$
– 3x89g2
Jul 19 at 2:45
@3x89g2 Indeed, $$ frac1-p^M-1p^M-1=p^-M+1-1. $$
– d.k.o.
Jul 19 at 3:11
Sorry. I meant, how do we get $E T_M$? Why $fracp^-M+1 - 11-p$?
– 3x89g2
Jul 19 at 3:15
@3x89g2 If $E_n$ is the average number of steps until the first run of $n$ heads, then it satisfies the following relation: beginalign E_n&=(1-p)(1+E_n)+p(1-p)(2+E_n)+cdots+p^nn \ &=E_n-p^nE_n+sum_k=0^n-1p^k. endalign So $$ E_n=sum_k=0^n-1fracp^kp^n=fracp^-n-11-p. $$
– d.k.o.
Jul 19 at 3:29
add a comment |Â
But the correct answer is $frac1 - p^M-1p^M-1$
– 3x89g2
Jul 19 at 2:45
@3x89g2 Indeed, $$ frac1-p^M-1p^M-1=p^-M+1-1. $$
– d.k.o.
Jul 19 at 3:11
Sorry. I meant, how do we get $E T_M$? Why $fracp^-M+1 - 11-p$?
– 3x89g2
Jul 19 at 3:15
@3x89g2 If $E_n$ is the average number of steps until the first run of $n$ heads, then it satisfies the following relation: beginalign E_n&=(1-p)(1+E_n)+p(1-p)(2+E_n)+cdots+p^nn \ &=E_n-p^nE_n+sum_k=0^n-1p^k. endalign So $$ E_n=sum_k=0^n-1fracp^kp^n=fracp^-n-11-p. $$
– d.k.o.
Jul 19 at 3:29
But the correct answer is $frac1 - p^M-1p^M-1$
– 3x89g2
Jul 19 at 2:45
But the correct answer is $frac1 - p^M-1p^M-1$
– 3x89g2
Jul 19 at 2:45
@3x89g2 Indeed, $$ frac1-p^M-1p^M-1=p^-M+1-1. $$
– d.k.o.
Jul 19 at 3:11
@3x89g2 Indeed, $$ frac1-p^M-1p^M-1=p^-M+1-1. $$
– d.k.o.
Jul 19 at 3:11
Sorry. I meant, how do we get $E T_M$? Why $fracp^-M+1 - 11-p$?
– 3x89g2
Jul 19 at 3:15
Sorry. I meant, how do we get $E T_M$? Why $fracp^-M+1 - 11-p$?
– 3x89g2
Jul 19 at 3:15
@3x89g2 If $E_n$ is the average number of steps until the first run of $n$ heads, then it satisfies the following relation: beginalign E_n&=(1-p)(1+E_n)+p(1-p)(2+E_n)+cdots+p^nn \ &=E_n-p^nE_n+sum_k=0^n-1p^k. endalign So $$ E_n=sum_k=0^n-1fracp^kp^n=fracp^-n-11-p. $$
– d.k.o.
Jul 19 at 3:29
@3x89g2 If $E_n$ is the average number of steps until the first run of $n$ heads, then it satisfies the following relation: beginalign E_n&=(1-p)(1+E_n)+p(1-p)(2+E_n)+cdots+p^nn \ &=E_n-p^nE_n+sum_k=0^n-1p^k. endalign So $$ E_n=sum_k=0^n-1fracp^kp^n=fracp^-n-11-p. $$
– d.k.o.
Jul 19 at 3:29
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2856055%2fexpected-number-of-tail-before-t-m%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
math.stackexchange.com/questions/1672956/…
– d.k.o.
Jul 18 at 22:36
@d.k.o. In this problem, tails returns you back to 1, so this is not a random walk.
– E-A
Jul 18 at 22:42
@d.k.o. In asymmetric random walk, the sum either goes up or down by 1. (So, if I have 5 mesos at time $i$, I would now have 4 or 6 mesos.) Here, tails takes you back to 1. (So, I either have 6 mesos or one meso)
– E-A
Jul 18 at 22:46
1
@E.A. Oh, I misread the question!
– d.k.o.
Jul 18 at 22:46
Also OP, yes, your intuition should work; you will have success after on average $p^-(M-1)$ streaks of heads, and number of expected trials is precisely the number of tails you have.
– E-A
Jul 18 at 22:50