Expected number of steps random walk

In summary: P[S = ∞ ] > 0 so ES = ∞. However, if P[S = ∞ ] = 0 then S = ∞, so it seems like P[S = ∞ ] should always be > 0. What am I not understanding?)In summary, the expected number of steps a walk starting from 1 hits 0 is infinity.
  • #1
fignewtons
28
0

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:wt(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|w1=1+1]P[w1=1+1] + E[S|w1=1-1]P[w1=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.
 
Last edited:
Physics news on Phys.org
  • #2
figNewtons said:

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:wt(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|w1=1+1]P[w1=1+1] + E[S|w1=1-1]P[w1=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.
 
  • #3
Ray Vickson said:
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 Wt(a) starting at a goes back to 0. R(a) = {Wt(a) = 0 for some t > 0, a > 0}.
Let S = min{t >= 0: Wt(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...
 
Last edited:
  • #4
figNewtons said:
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 Wt(a) starting at a goes back to 0. R(a) = {Wt(a) = 0 for some t > 0, a > 0}.
Let S = min{t >= 0: Wt(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.
 
  • #5
Ray Vickson said:
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 Sa,b = min{t>0, Wt(a) = b}

I get E[S1,0|R(1)] = E[S1,0 | X1 = +1 ]P[X1 = +1] + E[S1,0 | X1 = -1]P[X1 = -1]
= [E[S2,0] + 1]p + [E[S0,0]+ 1]q
=1 + pE[S2,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..
 
  • #6
figNewtons said:
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 Sa,b = min{t>0, Wt(a) = b}

I get E[S1,0|R(1)] = E[S1,0 | X1 = +1 ]P[X1 = +1] + E[S1,0 | X1 = -1]P[X1 = -1]
= [E[S2,0] + 1]p + [E[S0,0]+ 1]q
=1 + pE[S2,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\}##.
 

Related to Expected number of steps random walk

1. What is a random walk?

A random walk is a mathematical concept that describes a path or trajectory that is determined by a series of random steps or movements.

2. What is the expected number of steps in a random walk?

The expected number of steps in a random walk is the average number of steps that would be taken in multiple repetitions of the walk.

3. How is the expected number of steps calculated?

The expected number of steps can be calculated by multiplying the number of steps in the walk by the probability of taking each step, and then summing all of these values.

4. What factors can affect the expected number of steps in a random walk?

The expected number of steps can be affected by the number of possible directions or movements, the probability of taking each step, and the starting point of the walk.

5. Why is the expected number of steps important in scientific research?

The expected number of steps in a random walk is important in scientific research as it can help to predict the behavior or outcome of a system or process that involves random movements or interactions. It can also provide insight into the efficiency or effectiveness of certain strategies or algorithms in achieving a desired result.

Similar threads

  • Calculus and Beyond Homework Help
Replies
1
Views
1K
  • Calculus and Beyond Homework Help
Replies
1
Views
414
  • Calculus and Beyond Homework Help
Replies
3
Views
808
  • Calculus and Beyond Homework Help
Replies
3
Views
1K
  • Calculus and Beyond Homework Help
Replies
9
Views
825
Replies
5
Views
2K
  • Calculus and Beyond Homework Help
Replies
12
Views
1K
  • Calculus and Beyond Homework Help
Replies
16
Views
1K
  • Calculus and Beyond Homework Help
Replies
17
Views
1K
Replies
1
Views
698
Back
Top