Average number of times a random walk passes a point

[jamie.j1989]

Hi, I'm trying to work out how many time a particle going on a random walk starting at the origin would pass a particular point or points for a given total number of steps. I've simulated the problem and get approximately the same answer every time, however I'm struggling to know where to even start trying to work the number out analytically.

Problem

If two points lie on the x-axis at points s and -s and a particle starting at the origin goes on a random walk with step size b for a total of N steps, what is the average number of times it crosses s or -s?

For the problem simulated I used s = 7 , b = 1, N = 1000
I ran the simulation 30000 times and the number I got was 37.6310, I did this by simply creating a random number between 0 and 1 if the number is > 0.5 walk left < 0.5 walk right, and incremented a counting variable every time it crossed s or -s, and then averaged over the 30000 runs.

Thanks

Jamie

 

[mfb]

Those problems rarely have practical analytic solutions.

 

[andrewkirk]

An expression could be written involving nested sums.

If ##W(t)## is the value of the random walk variable at time step ##t## and ##X_s(t)## is the number of times that ##W(u)=s## for ##u\in\{0,1,...,t\}## then we have

$$E[X_s(N)]=\sum_{c=0}^n\ C\cdot Pr(X_s(N)=c)$$

and

$$Pr(X_s(N)=c)=\sum_{t_1=0}^N A(s,t_1)\sum_{z=t_1+2(c-1)}^N B(c-1,t_1,z)\cdot B(0,z,N)$$

where

• ##A(s,t)## is the probability that ##W(t)=s## and ##\forall u\in\{0,1,...,t-1\}:\ W(u)\neq s## (ie that ##W## reaches ##s## for the first time at step ##t##); and
• ##B(h,a,b)## is the probability that there are exactly ##h## elements ##u## in ##\{a+1,a+2,...,b\}## for which ##W(u)=W(a)##. Note that, because of the memoryless property of random walks, ##B(h,a,b)=B(h,0,b-a)##.

To complete the analytic expression we need to get analytic expressions for ##A## and ##B##. I think expressions will be able to be proven correct using induction, once we have good candidate expressions.

To start the process, I suggest trying to find an expression for ##D(t)##, which we define to be the probability that the random walk returns to zero for the first time at step ##t##. If you draw a recombining binary lattice, you can work out this probability for the first few time steps. Perhaps a formula will suggest itself. I did up to t=6 and got the following values for D(0), D(1),...D(6):
1/1, 0/2, 2/4, 0/8, 10/16, 0/32, 44/64 (haven't checked that last one completely)
For every second step the numerator is zero, as an even number of steps is needed to return to the start. If you did up to D(10) a formula for the numerators might suggest itself, which you could then try to prove correct by induction.

Armed with that, I think it should be possible to find formulas for ##A## and ##B##.

The end result formula will be somewhat long. To be more practical than your brute force simulation, the number of calculations in the formula needs to be of order less than ##2^N##. It seems feasible that that will be the case, although it may not turn out so. In any case there will be fun in trying.

It's also conceivable that answers to this sort of question are in some textbook on discrete random processes and stopping times. But looking that up would take the fun out of it.

 

[mfb]

Hmm...
If s is a multiple of b (so we count how often we arrive at exactly s), a simple sum works for the expectation value (but not for the distribution).

The probability to be m steps away (in one specific direction) from the origin after n steps is just (n choose (n-m)/2)/2ⁿ if n-m is even, and zero otherwise. Multiply by two to include both directions. Sum this expression over n from 0 to whatever you want to calculate.

 

[andrewkirk]

I don't think we can just sum, because that event includes cases where the walk has visited s one or more times in the interval of interest prior to arriving there (again) at step n, and we want to count the number of times it has been at s. That's why I'm thinking of trying to get a formula for the probability that the walk gets to s for the first time at a given step number. That 'for the first time' seems to complicate it quite a bit.

 

[mfb]

I don't think we can just sum, because that event includes cases where the walk has visited s one or more times in the interval of interest prior to arriving there (again) at step n

So what? Expectation values add up, correlations do not matter.

 

[andrewkirk]

Ah, I see what you're saying. That's an excellent trick.

If we write ##I_m(n)## as an indicator variable that is 1 if ##W(n)=m## and zero otherwise, then the number of hits at ##m## in ##0, 1, ...,N## is
$$X_m(N)=\sum_{n=0}^N I_m(n)$$

So then we have the expected number of hits at ##s## in ##0,1,...,N## is
$$E[X_m(N)]=E\left[\sum_{n=0}^N I_m(n)\right]
=\sum_{n=0}^N E\left[ I_m(n)\right]
=\sum_{n=0}^N\,Pr\left(W(n)=m\right)$$

and ##Pr\left(W(n)=m\right)## is as given in post 4.

 

[jamie.j1989]

Thanks, I'll need to scratch up on my probabilities, I've strayed a bit from my normal interests.

 

[mfb]

I've been thinking a bit more about a closed form that avoids any sums.
Formula-heavy post ahead.

Avoiding that odd/even thing, and with m=s/b and N as in post 1:
$$ E(m,N) = \sum_{i=0}^{N/2} 2^{-2i-m} {2i+m \choose i}$$
Where N/2 has to be rounded down.
Expressing the binomial coefficient as sum
$$ {2i+m \choose i} = {2i+m-1 \choose i} + {2i+m-1 \choose i-1}$$
and with some index shifting it is possible to get a recurrence relation:
$$ E(m,N) = \frac{1}{2}E(m+1,N-1) + \frac{1}{2}E(m-1,N-1) + \delta_{m0}$$
where ##\delta_{m0}=1## for m=0 and ##\delta_{m0}=0## otherwise (this handles the (0 choose 0) case where the expression as sum doesn't work).

WolframAlpha doesn't find an analytic expression for the general formula, but it does find analytic expressions for individual m, using M=N/2. Again, round N/2 down if N is odd (even where we add things like 3/2):

$$E(0,N) = 2^{-N-1} \left(\frac{N}{2}+1\right) {N+2 \choose N/2+1} = \frac{2 \Gamma(N/2+3/2)} {\sqrt{\pi} \Gamma(N/2+1)}$$
Where ##\Gamma## is the gamma function. Interesting π there...
$$E(1,N) = 2^{-N-2} \left(\frac{N}{2}+2\right) {N+3 \choose N/2+1} -1 = \frac{2 \Gamma(N/2+5/2)} {\sqrt{\pi} \Gamma(N/2+2)} -1 $$
See a pattern? Well, bad luck.
$$E(2,N) = \frac{1}{N/2+2} 2^{-N-3} \left(\frac{N}{2}+3\right)^2 {N+4 \choose N/2+1} -2 = \frac{2(N/2+3) \Gamma(N/2+5/2)} {\sqrt{\pi} \Gamma(N/2+3)} -2 $$
An additional (N/2+3)/(N/2+2) term appeared. Going to larger m, both expressions get ugly:
m=3
m=4
and so on.

The asymptotic behavior for large N is independent of m:$$\frac{E(m,N)}{\sqrt{N}} \to \sqrt\frac 2 \pi$$

I can confirm the value found in post #1, by the way, the calculation gives 37.9026. The simulation was less than 1% off, which is reasonable with 30000 simulations.
WA query.

 

[jamie.j1989]

Could we not also think about the problem in terms of allowed frequencies, if the average displacement over N steps is to be 0 then we have a set amount of frequencies that will create the full walk over N steps which all average 0?

If the nth frequency is ##\omega_n##, then

$$\omega_n = \frac{N}{4n}$$
With ## n=1,2,...,\frac{N}{4}##, this gives an average ##\omega## of
$$\left<\omega\right>=\frac{4}{N}\sum_{n=1}^{\frac{N}{4}}\frac{\frac{N}{4}}{n} = \sum_{n=1}^{\frac{N}{4}}\frac{1}{n}$$

We can also write the set of amplitudes that go with each ##\omega_n## as ##A_n##, where ##A_n = n##, and
$$\left<A\right> = \frac{4}{N}\sum_{n=1}^{\frac{N}{4}}n$$

Could we some how use these to determine on average how many times it crosses a position of certain amplitude s and -s, call it ##±A_s##?

 

[mfb]

I don't understand what you mean by "frequency". There is nothing periodic.