17
$\begingroup$

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$

$\endgroup$
5
  • 2
    $\begingroup$ Note that it is impossible to have $S_n$ actually equal $0$. By Bertrand's Postulate for any $n\ge 2$ there is a prime $p$ such that $n/2 < p \le n$, so exactly one of the rational numbers $X_1, \ldots, X_n$ has a denominator divisible by $p$, and this implies $S_n$ must be a nonzero multiple of $1/p$. $\endgroup$ Dec 25, 2023 at 3:24
  • 1
    $\begingroup$ $e = 2.718\ldots$, not $2.78\ldots$. $\endgroup$ Dec 25, 2023 at 3:26
  • 2
    $\begingroup$ Mind to share your simulations? $\endgroup$ Dec 25, 2023 at 6:55
  • $\begingroup$ I think I might have undercounted the rare freak cases that cross 0 extremely often. I suspect it might similar to en.m.wikipedia.org/wiki/St._Petersburg_paradox in that way. I'll do some more simulations. I think if $S_n = 0$, then the probability that $S_m =0$ for some $ m>2n$ might be interesting. Where I meant crossings and not literally equal to 0. $\endgroup$ Dec 25, 2023 at 10:41
  • $\begingroup$ If $P(+) = P(-)$, we have $E(X) = 0$ i.e. for $2n$ trials, there'll be $n$ crossings. As $2n \to \infty$, also $n \to \infty$ $\endgroup$ Dec 26, 2023 at 4:46

2 Answers 2

9
$\begingroup$

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.

$\endgroup$
8
  • $\begingroup$ Your argument looks like some of what’s in this paper: web.williams.edu/Mathematics/sjmiller/public_html/105Sp11/… The OP is asking for the expected number of sign changes in the sequence of partial sums of $S$, where $S$ is a random harmonic series. According to Schmuland, $S$ converges almost surely to a non-zero value, whence the number of crossings is almost surely finite. Perhaps Schmuland’s paper helps show whether the expected value of the number of crossings is finite or not, and if finite, something more specific. $\endgroup$
    – Steve Kass
    Jan 2 at 4:16
  • 1
    $\begingroup$ Yep, I agree with your assertions - Schmuland does prove that it almost surely converges to a nonzero number and so almost surely has a finite number of crossings. Schmuland does well at characterizing the tail behavior of the distribution but has less to say about intermediate partial sums because “these partial sums does not offer much of a foothold. These partial sums are discrete random variables and do not have densities.” $\endgroup$
    – Eric
    Jan 2 at 5:37
  • 1
    $\begingroup$ This paper seems to give bounds on the distribution of the partial sums themselves by looking at the Fourier transform of the partial sums (which effectively smooths them), but it seems to need some tweaking before it can be applied here: comptes-rendus.academie-sciences.fr/mathematique/item/10.1016/… $\endgroup$
    – Eric
    Jan 2 at 6:20
  • $\begingroup$ You are of course right about it being infinite and growing as log(n). If we take r randomly between inf S and sup S, then the expected number of crossings of r is $1/(sup S -inf S) \sum 1/n $ right ? $\endgroup$ Jan 2 at 9:38
  • $\begingroup$ Err, no - the largest and smallest values of $S_n$ go to $\pm \infty$, so your formula wouldn’t gives $\log(n)$. You need to both be near $1/n$ and hop the right direction. The expected number of crossings is $\sum_n 1/2 P(|S_{n-1}|<1/n)$ since you need to be near enough to $0$ and hop the right way. I believe (but haven’t shown) that additionally $P(|S_{n-1}|<1/n)\propto 1/n/\sqrt{Var(S_{n-1})}\propto 1/n$ which would give the result, but that is difficult to show rigorously since $S_n$ is discrete. $\endgroup$
    – Eric
    Jan 2 at 13:03
3
$\begingroup$

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))

empirical density of final position

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)

frequency of crossing

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) 

log-log frequency of crossing

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)

frequency of number of crosses

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .