Skip to main content
5 of 10
added 1 character in body
fedja
  • 61.9k
  • 11
  • 160
  • 302

could you elaborate more on your high tech solution?

OK, but it is just a standard boring exercise giving one no intellectual pleasure whatsoever. Write $X=t+Y$ where $EY=0$. Note that $t\ge\frac 1{2M}$. Let $f=f_1$ be the pdf of $Y$. Then the pdf $f_n$ of $Y+\dots+Y$ ($n$ times) is $f*\dots*f$, so $\widehat {f_n}=(\widehat f)^n$. Now $\widehat f(z)$ is an analytic function that is bounded by $e^{-\delta}$ on $(\mathbb R\setminus[-\rho,\rho])\cup [-\rho-i\tau,-\rho+i\tau]\cup[\rho-i\tau,\rho+i\tau]$ and $|f(x+iy)|\le e^{-ax^2+by^2}$ whenever $|x|\le\rho, |y|\le\tau$ with some efficient $a,b,\rho,\tau,\delta>0$ depending on $M$ only. Now, for $n\ge 2$, we can write $$ f_n(u)=\frac{1}{2\pi}\int_C (\widehat f(z))^n e^{iuz}dz $$ where $C$ is the contour $-\infty\to -\rho\to -\rho+iy \to \rho+iy\to\rho\to +\infty$ with any $y\in[-\tau,\tau]$ we want such that $uy>0$. Bounding $|f(z)|^n$ by $e^{-\delta(n-2)}|f(z)|^2$ on $C\setminus [-\rho+iy,\rho+iy]$, we see that that part of the contour contributes at most $Ce^{-\delta n}$ (recall that $\int_{\mathbb R}|\widehat f|^2=\int_{\mathbb R}|f|^2$ is controlled and the integral over the remaining interval is at most $e^{(bny^2-uy)}\int_\mathbb R e^{-anx^2}\,dx$. We would like to take $bny=\frac u2$, i.e. $y=cu/n$ to get $n^{-1/2}e^{-\gamma u^2/n}$ from here. That is fine as long as $|u|<c'n$. If $|u|>c'n$, we only get $e^{-\tau|u|/2}$, but we have allowed ourselves an exponential error already, so the final bound $$ f_n(u)\le C(e^{-\delta n}+n^{-1/2}e^{-\gamma u^2/n}) $$ holds always. The pdf of the sum of $n$ independent copies of $X$ is just $f_n(u-nt)$. I leave the estimation of the sum to you.

Edit. OK, here is a cute (in my taste) way to do it. Note that the statement can be reformulated as follows: For every $y>0,0<\varepsilon<\varepsilon_0$, the expected number of times the random walk $W_n=X_1+\dots+X_n$ hits $[y,y+\varepsilon]$ is at most $C\varepsilon$. Now, conditioning on $n$ such that $W_1,\dots,W_n<y-1; W_{n+1}>y-1$, we see that it is enough to get the bound for $y<1$. Now the probability to hit our interval after $n$ steps is at most $P\{W_{n-1}<1+\varepsilon_0\}M\varepsilon$, so it will suffice to sum $P_n=P\{W_n<1\}$. But now we obviously have $P_n\le \frac{M^n}{n!}$, so the Lipschitz constant is at most $Me^M$ (of course, this bound can be greatly improved, but, when doing it, try not to raise the level of complexity :-) ).

Next edit: Now we shall remove the condition that $X<1$ (but will still keep the iid assumption; the next question will be if we need the second "i" in it).

Let $t$ be the median of $X$. Split the pdf of $X$ into $f_-=f\chi_{[0,t]}$ and $f_+=f\chi_{(t,+\infty)}$. Now consider $F=f+f*f+\dots+f^{*N}$. It is a bounded function ($N$ is finite), so let $Z$ be its maximum. Write $$ F\le f+F*f=f+F*f_++F*f_-\le M+\frac Z2+F*f_- $$ The last term has a clear meaning: it is the chance to hit the target from distance $t$ or less. Now, if our target is $[y,y+\varepsilon]$, as before, then we can condition on $n$ such that $W_1,\dots,W_{n-1}<y-t, W_n\ge y-t$. Now, even if $W_n$ hits the target, it is not the hit we are interested in because in this case $X_n$ is a long shot and we count short shots only. However the score from the short range cannot be too large because every time you have $\frac 12$ chance to overshoot, which will terminate your attempts. Thus, the total probability to hit the target from the short range is at most $M\varepsilon(1+\frac 12+\frac 14+\dots)=2M\varepsilon$, so $$ Z=\max F\le M+\frac Z2+2M $$ so $Z\le 6M$ regardless of $N$.

Anybody in the mood for removing the identical distribution now? (before some serious probabilist steps in and tells us in which textbook it is all written)

fedja
  • 61.9k
  • 11
  • 160
  • 302