Expected number of steps random walk

[fignewtons]

Homework Statement

Let w(1) = event of a random walk with right drift (p > q, p+q = 1) starting at 1 returns to 0
Let p(w(1)) = probability of w(1)
Let S=min{t>=0:w_t(1)=0} be the minimum number of steps t a walk starting from 1 hits 0.
What is E[S|w(1)]?

Homework Equations

I know E[S|w(0)] = 0 (expected # of steps to get from 0 to 0 is 0)

The Attempt at a Solution

E[S|w(1)]=E[S|w₁=1+1]P[w₁=1+1] + E[S|w₁=1-1]P[w₁=1-1]
=[1+E[S|w(2)]]p+[1+E[S|w(0)]]
=pE[S|w(2)] + qE[S|w(0)] + 1
=pE[S|w(2)] + 1
I'm not sure how to proceed. Any tips? Please be specific and try to be as simple as possible. I'm new to this.

 

[Ray Vickson]

Homework Statement

Let w(1) = event of a random walk with right drift (p > q, p+q = 1) starting at 1 returns to 0
Let p(w(1)) = probability of w(1)
Let S=min{t>=0:w_t(1)=0} be the minimum number of steps t a walk starting from 1 hits 0.
What is E[S|w(1)]?

Homework Equations

I know E[S|w(0)] = 0 (expected # of steps to get from 0 to 0 is 0)

The Attempt at a Solution

E[S|w(1)]=E[S|w₁=1+1]P[w₁=1+1] + E[S|w₁=1-1]P[w₁=1-1]
=[1+E[S|w(2)]]p+[1+E[S|w(0)]]
=pE[S|w(2)] + qE[S|w(0)] + 1
=pE[S|w(2)] + 1
I'm not sure how to proceed. Any tips? Please be specific and try to be as simple as possible. I'm new to this.

Your notation is confusing: usually when we see a symbol like $E[S|w(1)]$ it means the expected value of $S$, conditional on the occurrence of the event $w(1)$. However, you SEEM to be asking for the expectation of the first time to hit state 0, starting from state 1, which is $E[S|X(0)=1]$. That is a totally different thing.

Your definition of $S$ is a bit confused also, because although you define it initially as the hitting time of 0 starting from 1, you later seem to let S refer to the hitting time to 0, starting from 0, and then from 2, etc. I suspect that you really intend for $S$ to be the first time to hit 0, no matter where you start from, and then you want to evaluate things like $E[S|X(0) = i]$, where $X(t)$ means the state at time $t$ and so $X(0)$ is the initial state at time $0$.

Anyway if your random walk is unrestricted (no upper limit on $X(t)$) and if $p > q$, then some very funny things happen when you attempt to evaluate $E[S|X(0) =1]$. I think the PF rules forbid me from being much more specific, but nothing prevents you from searching for "unrestricted random walks" on the internet.

 

[fignewtons]

Your notation is confusing: usually when we see a symbol like $E[S|w(1)]$ it means the expected value of $S$, conditional on the occurrence of the event $w(1)$. However, you SEEM to be asking for the expectation of the first time to hit state 0, starting from state 1, which is $E[S|X(0)=1]$. That is a totally different thing.

Your definition of $S$ is a bit confused also, because although you define it initially as the hitting time of 0 starting from 1, you later seem to let S refer to the hitting time to 0, starting from 0, and then from 2, etc. I suspect that you really intend for $S$ to be the first time to hit 0, no matter where you start from, and then you want to evaluate things like $E[S|X(0) = i]$, where $X(t)$ means the state at time $t$ and so $X(0)$ is the initial state at time $0$.

Anyway if your random walk is unrestricted (no upper limit on $X(t)$) and if $p > q$, then some very funny things happen when you attempt to evaluate $E[S|X(0) =1]$. I think the PF rules forbid me from being much more specific, but nothing prevents you from searching for "unrestricted random walks" on the internet.

Ok I thought i was going to make the notation easier but perhaps I made it more confusing so I'm just going to quote verbatim from the problem.
Given 1 > p > 1/2 > q=1-p > 0, let R(a) be the event that the random walk W_t(a) starting at a goes back to 0. R(a) = {W_t(a) = 0 for some t > 0, a > 0}.
Let S = min{t >= 0: W_t(1) = 0}. S = ∞ if walk never hits 0. We know P[S = ∞ ] > 0 so ES = ∞. (This part is a bit confusing to me, since later it says: for outcomes belonging to R(1), S < ∞). Find E[S|R(1)].

I think you are correct in saying that I am looking for the expected number of steps it takes for the walk to return to 0 for the first time, but S's definition has the required condition that the walk must start from 1.
I am confused because isn't R(1) a subset of R(a) where ES = ∞?

EDIT: I see what you're saying about how my definition of S changed as I did the calculations. I'm working on another way to write it.

UPDATE: I am very confused on how to express the expectation since S is defined based on the walk starting at 1. It is a very strange notation. Usually if S was not defined to be only based on the walk starting at 1 I can compute the expectation from the neighboring two point (like I did above) but now I don't know how to recondition the expectation...

 

[Ray Vickson]

Ok I thought i was going to make the notation easier but perhaps I made it more confusing so I'm just going to quote verbatim from the problem.
Given 1 > p > 1/2 > q=1-p > 0, let R(a) be the event that the random walk W_t(a) starting at a goes back to 0. R(a) = {W_t(a) = 0 for some t > 0, a > 0}.
Let S = min{t >= 0: W_t(1) = 0}. S = ∞ if walk never hits 0. We know P[S = ∞ ] > 0 so ES = ∞. (This part is a bit confusing to me, since later it says: for outcomes belonging to R(1), S < ∞). Find E[S|R(1)].

I think you are correct in saying that I am looking for the expected number of steps it takes for the walk to return to 0 for the first time, but S's definition has the required condition that the walk must start from 1.
I am confused because isn't R(1) a subset of R(a) where ES = ∞?

EDIT: I see what you're saying about how my definition of S changed as I did the calculations. I'm working on another way to write it.

For some reason, whenever I try to enter symbols or formulas in a response to your message, all the formulas have "strikeout" lines through them; you can still read them but they look exceedingly annoying. This occurs both in plain text but using symbols from the menu bar, or in LaTeX. So, no symbols at all in this response: the event R of 1 has probability less than 1, so on part of the s ample space the event R of 1 occurs and on another (non-zero probability) part the event R of 1 does not occur. So, it is perfectly OK to have the expectation of S be infinite, but the conditional expectation of S, given R of 1, is finite. The latter is looking only at that part of the sample space where the event R of 1 actually does occur, so where the state 0 is hit at some finite time.

Rebooted the computer and got $E[S|R(1)] < \infty$ in LaTeX and E[S|R(1) < ∞ in plain text. Weird.

 

[fignewtons]

For some reason, whenever I try to enter symbols or formulas in a response to your message, all the formulas have "strikeout" lines through them; you can still read them but they look exceedingly annoying. This occurs both in plain text but using symbols from the menu bar, or in LaTeX. So, no symbols at all in this response: the event R of 1 has probability less than 1, so on part of the s ample space the event R of 1 occurs and on another (non-zero probability) part the event R of 1 does not occur. So, it is perfectly OK to have the expectation of S be infinite, but the conditional expectation of S, given R of 1, is finite. The latter is looking only at that part of the sample space where the event R of 1 actually does occur, so where the state 0 is hit at some finite time.

Rebooted the computer and got $E[S|R(1)] < \infty$ in LaTeX and E[S|R(1) < ∞ in plain text. Weird.

Ok I see what you're saying. But I'm still not sure how to write S appropriately given that the definition is only for a walk starting at 1. I just abandoned the notation instead for a more explicit and general one. Let S_a,b = min{t>0, W_t(a) = b}

I get E[S_1,0|R(1)] = E[S_1,0 | X₁ = +1 ]P[X₁ = +1] + E[S_1,0 | X₁ = -1]P[X₁ = -1]
= [E[S_2,0] + 1]p + [E[S_0,0]+ 1]q
=1 + pE[S_2,0]

I am not sure if this is a step in the right direction because I don't know how to condition R(1).
On the side, I calculated that probability of R(1) is just q/p. But I don't know how to put it into the expectation..

 

[Ray Vickson]

Ok I see what you're saying. But I'm still not sure how to write S appropriately given that the definition is only for a walk starting at 1. I just abandoned the notation instead for a more explicit and general one. Let S_a,b = min{t>0, W_t(a) = b}

I get E[S_1,0|R(1)] = E[S_1,0 | X₁ = +1 ]P[X₁ = +1] + E[S_1,0 | X₁ = -1]P[X₁ = -1]
= [E[S_2,0] + 1]p + [E[S_0,0]+ 1]q
=1 + pE[S_2,0]

I am not sure if this is a step in the right direction because I don't know how to condition R(1).
On the side, I calculated that probability of R(1) is just q/p. But I don't know how to put it into the expectation..

No: you cannot say that
$$E[S_{1,0}| R(1)] = E[S_{1,0} | X_1 = +1] P(X_1 = +1) + E[S_{1,0}|X_1 = -1] P(X_1 = -1)$$
because we have $E[S_{1,0} | X_1 = \pm 1] = \infty$ but possibly $E[S_{1,0}| R(1)]$ is finite. When you condition on $R(1)$ you are looking at that part of the sample space on which the event $R(1)$ occurs---and that is not the whole sample space (because on some parts of the sample space the event $R(1)$ does not occur at all). When, instead, you condition on $X_1 = +1$ you are again looking at part of the sample space, but in this part there is a finite probability portion in which $R(1)$ does not occur, so $S = \infty$ on a nonzero-probability part of the subspace $\{ X_1 = +1\}$.