How often do we expect a random walk with decreasing step size to cross $0$?

Question

Let $S_n = \sum_{i=1}^{n} X_i$ be a random walk where the steps $X_i$ are $+\frac{1}{i}$ or $-\frac{1}{i}$ with equal probability. How often do we expect such a walk to cross $0$? By "cross 0", I mean that $S_i$ has the opposite sign as $S_{i-1}$. I'll use the following notation for such a crossing: $S_i \updownarrow 0$

Answer 1

Note that, as Schmuland has showed here (https://web.williams.edu/Mathematics/sjmiller/public_html/105Sp11/addcomments/Schmuland_RandomHarmonicSeries.pdf, thanks Steve Kass for the link), the limiting distribution of $S_n$ almost surely converges The limiting distribution is continuous, so it almost surely converges to a nonzero point and so after a certain point it almost surely has no more crossings. Thus, it almost surely has a finite number of crossings.

Despite having a finite number of crossings, the expected number of crossings is infinite. Here’s a rigorous proof of this. Let $Y_n$ be 0 if there’s no crossing and $1$ when there is a crossing, and let $Y$ be the total number of crossings, so that:

$$\mathbb E [Y]=\sum_{n=1} \mathbb E[Y_n]$$

Now let’s compute a lower bound for this sum. We can do so by showing that there’s some probability $S_n$ is close to $0$ and so a jump in the near future is very likely. Let $n>3$ and $2^m$ be the largest power of $2$ which is at most $n$, so $2^m\leq n <2^{m+1}$.

Let $W_n=\pm 1/1 \pm 1/2 \pm 1/4 \dots \pm 1/2^m$ be the sum of all the terms which are powers of $2$ and $Z_n$ be the rest, so $S_n=W_n + Z_n$ where $W_n$ and $Z_n$ are independent.

Note that $2^m W_n=\pm 2^m \pm \dots \pm 1$ is a uniform random odd integer between $-2^{m+1}+1$ and $2^{m+1}-1$

Since $Z_n$ is the sum of random reciprocals excluding powers of $2$ (which means excluding $\pm 1/1$ and $\pm 1/2$) we have: $$\textrm{Var}[Z_n]\leq 1/3^2+1/4^2+\dots=\pi^2/6-1-1/4$$ and $Z_n$ is centered at $0$, so by Chebyshev’s inequality: $$\Pr [|Z_n|\geq 1]<\textrm{Var}[Z_n]/1^2\leq \pi^2/6-1-1/4\leq 0.4$$ Thus, $\Pr[|Z_n|<1]\geq 0.6$.

If $|Z_n|<1$, then $|2^m Z_n|$ is less than $2^m$. Letting $a$ be the nearest odd integer we have that $\Pr[2^m W_n=-a]=1/2^{m+1}$ and in that case $|S_n|=|W_n+Z_n|\leq 1/2^m$.

If $|S_n|\leq 1/2^m\leq 2/n\leq 1/(n+1)+1/(n+2)+1/(n+3)$, then if the next 3 hops are torward the origin, we get a crossing. Thus, $\mathbb E [Y_{n+1}+Y_{n+2}+Y_{n+3}]\geq 1/8\times \Pr[|S_n|\leq 1/2^m]\geq 1/8\times \Pr[|Z_n|<1,W_n=-a/2^m]\geq 1/8\times 0.6 \times 1/2^m\geq 1/8\times 0.6 \times 1/n \geq .07/n$

Grouping every 3 terms greater than $5$ then gives that the number of crossings up to $N$ is at least $0.07/3 \log(N)\geq .02 \log(N)$, so as $N$ increases this goes to infinity, so the expected total number of crosses is infinite.

Answer 2

This is an extended comment rather than an answer, and provides some simulations as requested by Alma Arjuna. It gives some empirical justification for the claim of an unbounded number of expected crossings as the length of the walk increases.

The simulation using R, takes $10^5$ of the described random walk where the $i$th step is independently $\pm \frac1i$, with $1000$ steps.

walk <- function(maxn){
  flips <- sample(c(-1,1), maxn, replace=TRUE)
  steps <- flips / (1:maxn)
  position <- cumsum(steps)
  crosses <- c(0,abs(diff(sign(position)))/2) 
  c(sum(crosses), position[maxn], crosses)
  }

set.seed(2024) 
cases <- 10^5
lengthwalk <- 1000 
sims <- replicate(cases, walk(lengthwalk))
numbercrosses <- sims[1,]
finalposition <- sims[2,]
freqplacescrossed <- rowMeans(sims[-(1:2),]) 

We would expect the final position to have expectation $0$ and variance close to $\frac{\pi^2}{6}\approx 1.6449$ and indeed it does. Visually, the distribution appears platykurtic and empirically the raw kurtosis seems well below $3$.

mean(finalposition)
# -0.00100215
var(finalposition)
# 1.650323
pi^2/6 # Basel problem
# 1.644934
mean(finalposition^4) / mean(finalposition^2)^2 # estimate of raw kurtosis
# 2.194777
plot(density(finalposition))

Theoretically, the walk is not going to cross $0$ in the first three steps since $1-\frac12-\frac13>0$, but has a probability of crossing at the fourth step of $\frac18$, at the fifth step of $\frac1{16}$, at the sixth step of $\frac1{32}$, at the seventh step of $\frac3{64}$, and at the eighth step of $\frac1{32}$. Allowing for simulation noise, the simulation confirms this, and the frequencies then tend to decline for later steps.

cbind(c(0, 0, 0, 1/8, 1/16, 1/32, 3/64, 1/32), freqplacescrossed[1:8])
#         [,1]    [,2]
#[1,] 0.000000 0.00000
#[2,] 0.000000 0.00000
#[3,] 0.000000 0.00000
#[4,] 0.125000 0.12613
#[5,] 0.062500 0.06252
#[6,] 0.031250 0.03159
#[7,] 0.046875 0.04727
#[8,] 0.031250 0.03164
plot(freqplacescrossed)

and if this is replotted on a log-log scale, for larger $i$ it seems that the probability of crossing at the $i$th step might visually perhaps be close to $\frac1{4i}$.

plot(4:lengthwalk, freqplacescrossed[-(1:3)], log="xy")
curve(1/(4*x), from=4, to=lengthwalk, col="red", add=TRUE) 

If something like that $\frac1{4i}$ probability of crossing is broadly correct, it might suggest that the total expected number of crossings in the first $n$ steps might be about $\frac{19}{64}+\sum\limits_{i=9}^n \frac{1}{4i} \approx \frac14\log_e(n)-0.238$ and clearly this would increase without limit as $n$ increases, supporting the original assertion.

This simulation is broadly consistent with this.

mean(numbercrosses)
# 1.4892
1/8 + 1/16 + 1/32 + 3/64 + 1/32 + sum(0.25/(9:lengthwalk))
# 1.488778
(1/4)*log(lengthwalk) - 0.238
# 1.488939

There is a very high dispersion of the number of crosses in the first $1000$ steps, as the large majority of simulated walks never cross $0$, while at the other extreme one walk crossed $125$ times in this simulation of $100000$ walks of $1000$ steps.

var(numbercrosses)
# 32.36233
plot(table(numbercrosses)/cases)