Skip to main content
added 4 characters in body
Source Link
Yuval Peres
  • 14.2k
  • 1
  • 28
  • 49

Expanding the comment above to a complete proof of Noam Elkies' formula:

Let $\tau$ be the first meeting time for independent simple random walks $X_t, Y_t$ and $Z_t$ started at the even points $x<y<z$. Write $f(x,y,z)= (z-y)(y-x)$. Claim: $ E(\tau)=f(x,y,z)$.

Proof: let $F_n=f(X_{\tau \wedge n},Y_{\tau \wedge n},Z_{\tau \wedge n})$ and $M_n:=F_n+{\tau \wedge n}$. It is easy to verify that $M_n$ is a Martingale so $f(x,y,z)=M_0=E(F_n+\tau\wedge n)$ for any $n$. Therefore $E(\tau) \le f(x,y,z)$. It remains to verify that $\lim_n E(F_n)=0$. Clearly $F_n \to 0$ a.s. so it suffices to verify that $\max_n F_n$ is integrable. For this we will use the linear martingale $L_n=(Z_n-X_n)/2$ and the quadratic martingale $Q_n=F_n+ 2 L_n^2$. The first is a lazy SRW on the integers. The AMGM inequality gives $4f(x,y,z)\le (z-x)^2$, so $E (\max_{n \le t} F_n) \le E(\max_{n \le t} L_n^2) \le 4 E(L_t^2)$ by Doob’s $L^2$ maximal inequality. But $E(L_t^2) \le E(Q_t)=Q_0$$4E(L_t^2) \le 2E(Q_t)=2Q_0$ for every $t$. We conclude that $ E (\max_n F_n) \le Q_0$$ E (\max_n F_n) \le 2Q_0$.

Expanding the comment above to a complete proof of Noam Elkies' formula:

Let $\tau$ be the first meeting time for independent simple random walks $X_t, Y_t$ and $Z_t$ started at the even points $x<y<z$. Write $f(x,y,z)= (z-y)(y-x)$. Claim: $ E(\tau)=f(x,y,z)$.

Proof: let $F_n=f(X_{\tau \wedge n},Y_{\tau \wedge n},Z_{\tau \wedge n})$ and $M_n:=F_n+{\tau \wedge n}$. It is easy to verify that $M_n$ is a Martingale so $f(x,y,z)=M_0=E(F_n+\tau\wedge n)$ for any $n$. Therefore $E(\tau) \le f(x,y,z)$. It remains to verify that $\lim_n E(F_n)=0$. Clearly $F_n \to 0$ a.s. so it suffices to verify that $\max_n F_n$ is integrable. For this we will use the linear martingale $L_n=(Z_n-X_n)/2$ and the quadratic martingale $Q_n=F_n+ 2 L_n^2$. The first is a lazy SRW on the integers. The AMGM inequality gives $4f(x,y,z)\le (z-x)^2$, so $E (\max_{n \le t} F_n) \le E(\max_{n \le t} L_n^2) \le 4 E(L_t^2)$ by Doob’s $L^2$ maximal inequality. But $E(L_t^2) \le E(Q_t)=Q_0$ for every $t$. We conclude that $ E (\max_n F_n) \le Q_0$.

Expanding the comment above to a complete proof of Noam Elkies' formula:

Let $\tau$ be the first meeting time for independent simple random walks $X_t, Y_t$ and $Z_t$ started at the even points $x<y<z$. Write $f(x,y,z)= (z-y)(y-x)$. Claim: $ E(\tau)=f(x,y,z)$.

Proof: let $F_n=f(X_{\tau \wedge n},Y_{\tau \wedge n},Z_{\tau \wedge n})$ and $M_n:=F_n+{\tau \wedge n}$. It is easy to verify that $M_n$ is a Martingale so $f(x,y,z)=M_0=E(F_n+\tau\wedge n)$ for any $n$. Therefore $E(\tau) \le f(x,y,z)$. It remains to verify that $\lim_n E(F_n)=0$. Clearly $F_n \to 0$ a.s. so it suffices to verify that $\max_n F_n$ is integrable. For this we will use the linear martingale $L_n=(Z_n-X_n)/2$ and the quadratic martingale $Q_n=F_n+ 2 L_n^2$. The first is a lazy SRW on the integers. The AMGM inequality gives $4f(x,y,z)\le (z-x)^2$, so $E (\max_{n \le t} F_n) \le E(\max_{n \le t} L_n^2) \le 4 E(L_t^2)$ by Doob’s $L^2$ maximal inequality. But $4E(L_t^2) \le 2E(Q_t)=2Q_0$ for every $t$. We conclude that $ E (\max_n F_n) \le 2Q_0$.

Source Link
Yuval Peres
  • 14.2k
  • 1
  • 28
  • 49

Expanding the comment above to a complete proof of Noam Elkies' formula:

Let $\tau$ be the first meeting time for independent simple random walks $X_t, Y_t$ and $Z_t$ started at the even points $x<y<z$. Write $f(x,y,z)= (z-y)(y-x)$. Claim: $ E(\tau)=f(x,y,z)$.

Proof: let $F_n=f(X_{\tau \wedge n},Y_{\tau \wedge n},Z_{\tau \wedge n})$ and $M_n:=F_n+{\tau \wedge n}$. It is easy to verify that $M_n$ is a Martingale so $f(x,y,z)=M_0=E(F_n+\tau\wedge n)$ for any $n$. Therefore $E(\tau) \le f(x,y,z)$. It remains to verify that $\lim_n E(F_n)=0$. Clearly $F_n \to 0$ a.s. so it suffices to verify that $\max_n F_n$ is integrable. For this we will use the linear martingale $L_n=(Z_n-X_n)/2$ and the quadratic martingale $Q_n=F_n+ 2 L_n^2$. The first is a lazy SRW on the integers. The AMGM inequality gives $4f(x,y,z)\le (z-x)^2$, so $E (\max_{n \le t} F_n) \le E(\max_{n \le t} L_n^2) \le 4 E(L_t^2)$ by Doob’s $L^2$ maximal inequality. But $E(L_t^2) \le E(Q_t)=Q_0$ for every $t$. We conclude that $ E (\max_n F_n) \le Q_0$.