An Application of a Theorem I Just Learned

Question : Recall that a polygonal number is a number that counts dots arranged in the shape of a regular polygon. Prove that the $n$-th non $s$-gonal number is given by

$$\lfloor \frac{1}{2}+\sqrt{\frac{1}{4}+\frac{2n}{s-2}}\rfloor +n$$

where $\lfloor x\rfloor$ represents the least integer less than or equal to $x$.

Answer : It is well known that

$$(s-2)\frac{n(n-1)}{2}+n$$

is the $n$-th $s$-gonal number.

Now, we will use the Lambek-Moser Theorem to get

$$f(n)=(s-2)\frac{n(n-1)}{2}$$

and hence

$$f^{\ast }(n)=\lfloor \frac{1}{2}+\sqrt{\frac{1}{4}+\frac{2n}{s-2}}\rfloor$$

and hence

$$F^{\ast }(n)=\lfloor \frac{1}{2}+\sqrt{\frac{1}{4}+\frac{2n}{s-2}}\rfloor +n$$

hence completing the proof.

Remark : A careful induction on $n$ (keeping $s$ fixed) would probably have also done the job.

Acknowledgement : I learnt about the Lambek-Moser Theorem from the book The Irrationals: a Story of the Numbers You Can't Count On by Julian Havil (section Theoretical Matters of chapter Does Irrationality Matter?) which I also reviewed for zbMATH. 

The Law of Iterated Logarithm

1. Introduction

The goal is to give a complete proof of the Law of Iterated Logarithm. The setup we will work in is the following. Let $\{X_i{\}}_{i=1}^{\mathrm{\infty }}$ be a sequence of iid random variables with mean $0$ and variance $1$. Let

$$S_n:=\sum _{i=1}^n{X}_i\text{ and }{\overline{S}}_n:=\frac{S_n}{n}$$

for $n\in {\mathbb{Z}}^{+}$. From now on, we will use $X_n$ and $S_n$ as defined in our discussions.

We wish to prove the following theorem.

Theorem 1 (The Law of Iterated Logarithm) : Let

$${\mathrm{\Lambda }}_n:=\sqrt{2n\log \log n}$$

wherever it is defined. Then,

$$\underset{n\to \mathrm{\infty }}{lim sup}\frac{S_n}{{\mathrm{\Lambda }}_n}=1$$

almost surely. By replacing $X_j$ by $-X_j$, this also proves that

$$\underset{n\to \mathrm{\infty }}{lim inf}\frac{S_n}{{\mathrm{\Lambda }}_n}=-1$$

almost surely. In fact, for any $f\in C(\mathbb{R},\mathbb{R})$,

$$\underset{n\to \mathrm{\infty }}{lim sup}f\left(\frac{S_n}{{\mathrm{\Lambda }}_n}\right)=\underset{t\in [-1,1]}{sup}f(t)$$

almost surely. That is, the set of limit points of

$$\{\frac{S_n}{{\mathrm{\Lambda }}_n}:n\ge 1\}$$

coincides with the interval $[-1,1]$ almost surely.

In what follows, we will use the notation

$${\mathrm{\Lambda }}_{\beta }:={\mathrm{\Lambda }}_{\lfloor \beta \rfloor }\text{ and }{\tilde{S}}_{\beta }:=\frac{S_{\lfloor \beta \rfloor }}{{\mathrm{\Lambda }}_{\beta }}$$

where $\lfloor \beta \rfloor$ is greatest integer less than or equal to $\beta$.

The main reference we are following is Probability Theory, An Analytic View by Daniel W. Stroock.

2. Lemmas

To prove Theorem 1, we need three lemmas.

Lemma 1 : For $a\in (0,\mathrm{\infty })$ and $\beta \in (1,\mathrm{\infty })$, if

$$\sum _{m=1}^{\mathrm{\infty }}\mathbb{P}(\left|{\tilde{S}}_{{\beta }^m}\right|\ge \frac{a}{\sqrt{\beta }})<\mathrm{\infty }$$

then

$$\underset{n\to \mathrm{\infty }}{lim sup}\left|{\tilde{S}}_n\right|\le a$$

almost surely.

Lemma 2 : For any sequence $\{X_n:n\ge 1\}$ of iid random variables with mean $0$ and variance ${\sigma }^2$, we have

$$\underset{n\to \mathrm{\infty }}{lim sup}\left|{\tilde{S}}_n\right|\le 8\sigma$$

almost surely.

Lemma 3 : Let the sequence $\{X_n\}$ have a common distribution $\mu$. Further, let the moment-generating function

$$M_{\mu }(\xi ):={\int }_{\mathbb{R}}{e}^{\xi x}\mu (\text{d}x)<\mathrm{\infty }$$

for all $\xi \in \mathbb{R}$. Then, for all $R\in (0,\mathrm{\infty })$, there is an $N(R)\in {\mathbb{Z}}^{+}$ and a suitable constant $K$ such that

$$\mathbb{P}(\left|{\tilde{S}}_n\right|\ge R)\le 2\exp [-(1-K\sqrt{\frac{8R\log \log n}{n}})R^2\log \log n]$$

for all $n\ge N(R)$. Also, for each $\epsilon \in (0,1]$, there is an $N(\epsilon )\in {\mathbb{Z}}^{+}$ such that for all for all $n\ge N(\epsilon )$ and $\left|a\right|\le \frac{1}{\epsilon }$,

$$\mathbb{P}(|{\tilde{S}}_n-a|<\epsilon )\ge \frac{1}{2}\exp [-(a^2+4K\left|a\right|\epsilon )\log \log n]$$

for some suitable constant $K$.

3. Proof of Theorem

We will first give a proof assuming the three lemmas and then give a proof of the lemmas afterwards.

Proof of Theorem 1 : Observe first that for any $X_n$ and $\epsilon >0$, it is easy to find a $\psi \in C_{\text{b}}(\mathbb{R})$ so that $Y_n:=\psi \circ X_n$ has mean $0$ and variance $1$ while $Z_n:=X_n-Y_n$ has variance less than ${\epsilon }^2$ (what we want is to find a smooth truncation - one way to do this is by first considering $X_n\cdot {\mathbf{1}}_{\left|X_n\right|<n}$ and then appropriately smoothening the edges). Applying Lemma 2 to this $Z_n$, we have

$$\underset{n\to \mathrm{\infty }}{lim sup}|{\tilde{S}}_n(\omega )|\le 1+\underset{n\to \mathrm{\infty }}{lim sup}\left|\frac{\sum _{m=1}^n{Z}_m(\omega )}{{\mathrm{\Lambda }}_n}\right|\le 1+8\epsilon$$

and for $a\in [-1,1]$, we have

$$\underset{n\to \mathrm{\infty }}{lim inf}|{\tilde{S}}_n(\omega )-a|\le \underset{n\to \mathrm{\infty }}{lim sup}\left|\frac{\sum _{m=1}^n{Z}_m(\omega )}{{\mathrm{\Lambda }}_n}\right|\le 8\epsilon$$

for almost every $\omega \in \mathrm{\Omega }$. So, it is enough to assume that the random variables are bounded, and that is what will be assumed in the rest of the proof.

Now, for a given $\beta >1$, we can use Lemma 3 to argue

$$\mathbb{P}(\left|{\tilde{S}}_{{\beta }^m}\right|\ge \sqrt{\beta })\le 2\exp [-\sqrt{\beta }\log \log \lfloor {\beta }^m\rfloor ]$$

for all sufficiently large $m\in {\mathbb{Z}}^{+}$. So, using Lemma 1 with $a=\beta$, we see that

$$\underset{n\to \mathrm{\infty }}{lim sup}\left|{\tilde{S}}_n\right|\le \beta$$

almost surely for all $\beta \in (1,\mathrm{\infty })$.

So, to complete the proof, we need to show

$$\mathbb{P}(\underset{n\to \mathrm{\infty }}{lim inf}|{\tilde{S}}_n-a|<\epsilon )=1$$

for all $a\in (-1,1)$ and all $\epsilon >0$. To do this, we wish to use the Borel-Cantelli Lemma. But for that, we need to make sure we are dealing with independent events. For this, we can use the previously proved result to argue that

$$\underset{n\to \mathrm{\infty }}{lim inf}|{\tilde{S}}_n-a|\le \underset{k\ge 2}{inf}\underset{m\to \mathrm{\infty }}{lim inf}|{\tilde{S}}_{k^m}-a|\le \underset{k\to \mathrm{\infty }}{lim inf}\underset{n\to \mathrm{\infty }}{lim inf}|\frac{S_{k^m}-S_{k^{m-1}}}{{\mathrm{\Lambda }}_{k^m}}-a|$$

almost surely for all integers $k\ge 2$.

Now, since the events

$$A_{k,m}:={\{|\frac{S_{k^m}-S_{k^{m-1}}}{{\mathrm{\Lambda }}_{k^m}}-a|<\epsilon \}}_{m\in {\mathbb{Z}}^{+}}$$

are mutually independent for each $k\ge 2$, it is enough to check that

$$\sum _{m=1}^{\mathrm{\infty }}\mathbb{P}\left(A_{k,m}\right)=\mathrm{\infty }$$

for sufficiently large $k$.

But, since

$$\underset{k\to \mathrm{\infty }}{lim}\underset{m\in {\mathbb{Z}}^{+}}{max}|\frac{{\mathrm{\Lambda }}_{k^m}}{{\mathrm{\Lambda }}_{k^m-k^{m-1}}}-1|=0$$

and

$$\mathbb{P}\left(A_{k,m}\right)=\mathbb{P}(|{\tilde{S}}_{k^m-k^{m-1}}-\frac{a{\mathrm{\Lambda }}_{k^m}}{{\mathrm{\Lambda }}_{k^m-k^{m-1}}}|<\frac{\epsilon {\mathrm{\Lambda }}_{k^m}}{{\mathrm{\Lambda }}_{k^m-k^{m-1}}})$$

for all $k\ge 2$, it is enough to show

$$\sum _{m=1}^{\mathrm{\infty }}\mathbb{P}(|{\tilde{S}}_{k^m-k^{m-1}}-a|<\epsilon )=\mathrm{\infty }$$

for every $k\ge 2$ and $a\in (-1,1)$ and $\epsilon >0$. This follows by using the second part of Lemma 3 and choosing $\tilde{\epsilon }>0$ so small that $\rho :=a^2+4K\tilde{\epsilon }|a|<1$ from which it is possible to conclude that when $0<\epsilon <\tilde{\epsilon }$, we have

$$\mathbb{P}(|{\tilde{S}}_n-a|<\epsilon )\ge \frac{1}{2}\exp [-\rho \log \log n]$$

for all sufficiently large $n$.

This completes the proof. $◻$

4. Proof of Lemma 1

We first introduce the idea of a median. Give a real valued random variable $Y$, we say $\alpha \in \mathbb{R}$ is a median of $Y$ if

$$\mathbb{P}(Y\le \alpha )\ge \frac{1}{2}\text{ and }\mathbb{P}(Y\ge \alpha )\ge \frac{1}{2}$$

and write as $\alpha \in \mathrm{med}(Y)$. It is easy to see that

$$\alpha :=inf\{t\in \mathbb{R}:\mathbb{P}(Y\le t)\ge \frac{1}{2}\}$$

is a median of $Y$. In other words, every $Y$ has a median. Additionally, it can be shown that if $Y\in L^2(\mathbb{R})$ and $m$ is the mean of $Y$, then

$$|\alpha -m|\le \sqrt{2\text{Var}(Y)}$$

for all $\alpha \in \text{med}(Y)$.

We also have the following theorem.

Theorem 2 (Lévy Reflection Principle) : For $k\le \ell$, choose ${\alpha }_{\ell ,k}\in \mathrm{med}(S_{\ell }-S_k)$. Then, for all $\epsilon >0$, we have

$$\mathbb{P}(\underset{1\le n\le N}{max}|S_n+{\alpha }_{n,m}|\ge \epsilon )\le 2\mathbb{P}(\left|S_N\right|\ge \epsilon )$$

for all $N\in {\mathbb{Z}}^{+}$.

With this at hand, we move to the proof.

Proof of Lemma 1 : Let $\beta \in (1,\mathrm{\infty })$ be given. For each $m\in \mathbb{N}$ and $1\le n\le {\beta }^m$, let ${\alpha }_{m,n}$ be a median of $S_{\lfloor {\beta }^m\rfloor }-S_n$. This gives $\left|{\alpha }_{m,n}\right|\le \sqrt{2{\beta }^m}$ so that

$$\begin{array}{rl}\underset{n\to \mathrm{\infty }}{lim sup}\left|{\tilde{S}}_n\right|& =\underset{m\to \mathrm{\infty }}{lim sup}\underset{{\beta }^{m-1}\le n\le {\beta }^m}{max}\left|{\tilde{S}}_n\right|\\ & \le \sqrt{\beta }\underset{m\to \mathrm{\infty }}{lim sup}\underset{n\le {\beta }^m}{max}\frac{\left|S_n\right|}{{\mathrm{\Lambda }}_{{\beta }^m}}\\ & \le \sqrt{\beta }\underset{m\to \mathrm{\infty }}{lim sup}\underset{n\le {\beta }^m}{max}\frac{|S_n+{\alpha }_{m,n}|}{{\mathrm{\Lambda }}_{{\beta }^m}}\end{array}$$

which gives

$$\mathbb{P}(\underset{n\to \mathrm{\infty }}{lim sup}\left|{\tilde{S}}_n\right|\ge a)\le \mathbb{P}(\underset{m\to \mathrm{\infty }}{lim sup}\underset{n\le {\beta }^m}{max}\frac{|S_n+{\alpha }_{m,n}|}{{\mathrm{\Lambda }}_{{\beta }^m}}\ge \frac{a}{\sqrt{\beta }})$$

and hence on application of Theorem 2, we have

$$\mathbb{P}(\underset{n\le {\beta }^m}{max}\frac{|S_n+{\alpha }_{m,n}|}{{\mathrm{\Lambda }}_{{\beta }^m}}\ge \frac{a}{\sqrt{\beta }})\le 2\mathbb{P}(\left|{\tilde{S}}_{{\beta }^m}\right|\ge \frac{a}{\sqrt{\beta }})$$

from which the desired result follows using Borel-Cantelli Lemma. $◻$

5. Proof of Lemma 2

Again, we need to introduce a few objects before we can move to our proof.

We define the Rademacher functions $\{R_n{\}}_{n\in {\mathbb{Z}}^{+}}$ on $[0,1)$ as follows. Consider the function $R:\mathbb{R}\to \{-1,1\}$ given by

$$R(t):=\{\begin{array}{ll}-1& \text{if}t-\lfloor t\rfloor \in [0,\frac{1}{2})\\ 1& \text{if}t-\lfloor t\rfloor \in [\frac{1}{2},1)\end{array}$$

and define $R_n$ on $[0,1)$ by

$$R_n(\omega ):=R\left(2^{n-1}\omega \right)$$

for $n\in {\mathbb{Z}}^{+}$ and $\omega \in [0,1)$. It can be shown that the Rademacher functions are mutually independent.

We will use these functions in our proof.

Proof of Lemma 2 : Without loss of generality, it can be assumed that $\sigma =1$. We begin by considering the case where the $X_n$'s are symmetric, i.e., $X_n$ and $-X_n$ has the same distribution as $X_n$ itself. For this case, we will be able to prove the result with the constant $8$ replaced by $4$ once we can show

$$\sum _{m=0}^{\mathrm{\infty }}\mathbb{P}\left(|{\tilde{S}}_{2^m}\ge 2^{3/2}|\right)<\mathrm{\infty }$$

since we can then use Lemma 1.

Now, let $(\mathrm{\Omega },\mathcal{F},\mathbb{P})$ be the probability space on which the $X_n$'s are defined and let $\{R_n{\}}_{n\in {\mathbb{Z}}^{+}}$ be the sequence of Rademacher functions on $[0,1)$. Set $\mathbb{Q}:={\lambda }_{[0,1)}\times \mathbb{P}$ on $([0,1)\times \mathrm{\Omega },{\mathcal{B}}_{[0,1)}\times \mathcal{F})$ where ${\lambda }_{[0,1)}$ is the Lebesgue measure on $[0,1)$. It is easy to check that the symmetry of $X_n$ is equivalent to the statement that

$$\omega \in \mathrm{\Omega }\mapsto (X_1(\omega ),X_2(\omega ),\dots )\in {\mathbb{R}}^{{\mathbb{Z}}^{+}}$$

has the same distribution under $\mathbb{P}$ as

$$(t,\omega )\in [0,1)\times \mathrm{\Omega }\mapsto (R_1(t)X_1(\omega ),R_2(t)X_2(\omega ),\dots )\in {\mathbb{R}}^{{\mathbb{Z}}^{+}}$$

has under $\mathbb{Q}$.

Now, from Hoeffding's inequality, we know that for a given $\{{\sigma }_k{\}}_{k=1}^n\in \mathbb{R}$ and mutually independent random variables $\{X_i{\}}_{i=1}^n$ with common distribution $\mu$, the centered Bernoulli distribution given by $\mu (\{\pm 1\})=\frac{1}{2}$, if $\nu$ denotes the distribution $S:=\sum _1^n{\sigma }_k{X}_k$, then for all $a\in [0,\mathrm{\infty })$, we have

$$\mathbb{P}(|S|\ge a)\le 2\exp [-\frac{a^2}{2{\mathrm{\Sigma }}^2}]$$

where ${\mathrm{\Sigma }}^2:=\sum _1^n{\sigma }_k^2$. We use this with ${\sigma }_k=X_k(\omega )$ and note that

$${\lambda }_{[0,1)}\left(\{t\in [0,1):|\sum _{n=1}^{2^m}{R}_n(t)X_n(\omega )|\ge a\}\right)\le 2\exp [-\frac{a^2}{2\sum _1^{2^m}{X}_n(\omega {)}^2}]$$

for all $a\in [0,\mathrm{\infty })$ and $\omega \in \mathrm{\Omega }$.

So, if we define

$$A_m:=\{\omega \in \mathrm{\Omega }:\frac{1}{2^m}\sum _{n=1}^{2^m}{X}_m(\omega {)}^2\ge 2\}$$

and

$$F_m(\omega ):={\lambda }_{[0,1)}\left(\{t\in [0,1):|\sum _{n=1}^{2^m}{R}_n(t)X_n(\omega )|\ge 2^{3/2}{\mathrm{\Lambda }}_{2^m}\}\right)$$

then we have

$$\begin{array}{rl}\mathbb{P}\left(\{\omega \in \mathrm{\Omega }:|S_{2^m}(\omega )|\ge 2^{3/2}{\mathrm{\Lambda }}_{2^m}\}\right)& ={\int }_{\mathrm{\Omega }}{F}_m(\omega )\mathbb{P}\left(\text{d}\omega \right)\\ & \le 2{\int }_{\mathrm{\Omega }}\exp [-\frac{8{\mathrm{\Lambda }}_{2^m}^2}{2\sum _1^{2^m}{X}_n(\omega )}]\mathbb{P}\left(\text{d}\omega \right)\\ & \le 2\exp [-4\log \log 2^m]+2\mathbb{P}\left(A_m\right)\end{array}$$

due to Tonelli's Theorem.

So, it is enough to show $\sum _0^{\mathrm{\infty }}\mathbb{P}\left(A_m\right)<\mathrm{\infty }$. To do so, let us set

$$T_m:=\sum _{n=1}^{2^m}{X}_n^2{B}_m:=\{\frac{T_{m+1}-T_m}{2^m}\ge 2\}{\overline{T}}_m:=\frac{T_m}{2^m}$$

for $m\in {\mathbb{Z}}^{+}$. Clearly $\{B_m{\}}_{m\in {\mathbb{Z}}^{+}}$ are independent and $\mathbb{P}\left(A_m\right)=\mathbb{P}\left(B_m\right)$. So, it is enough to show

$$\mathbb{P}\left(\underset{m\to \mathrm{\infty }}{lim sup}{B}_m\right)=\mathbb{P}(\underset{m\to \mathrm{\infty }}{lim sup}\frac{T_{m+1}-T_m}{2^m}\ge 2)=0$$

and then use Borel-Cantelli Lemma.

But, by Strong Law of Large Numbers, we know ${\overline{T}}_m\to 1$ almost surely, and hence

$$\frac{T_{m+1}-T_m}{2^m}\to 1$$

almost surely. This completes the proof for the symmetric case replacing the constant $8$ by $4$.

To eliminate the symmetry assumption, let $(\mathrm{\Omega },\mathcal{F},\mathbb{P})$ be the space on which $X_n$'s are defined and define $\{Y_n\}$ on $({\mathrm{\Omega }}^2,{\mathcal{F}}^2,{\mathbb{P}}^2)$ as

$$Y_n({\omega }_1,{\omega }_2):=X_n({\omega }_1)-X_n({\omega }_2)$$

for $n\in {\mathbb{Z}}^{+}$. It is easy to check that the $Y_n$'s are symmetric. This gives

$$\underset{n\to \mathrm{\infty }}{lim sup}\frac{|S_n({\omega }_1)-S_n({\omega }_2)|}{{\mathrm{\Lambda }}_n}\le 2^{5/2}\le 8$$

for $\mathbb{Q}$ almost every $({\omega }_1,{\omega }_2)\in {\mathrm{\Omega }}^2$.

Now, we wish to proceed by contradiction. If possible, let

$$\underset{n\to \mathrm{\infty }}{lim sup}\frac{|S_n(\omega )|}{{\mathrm{\Lambda }}_n}>8$$

on a set of positive $\mathbb{P}$ measure so that by Kolmogorov's $0-1$ Law, there is an $\epsilon >0$ such that

$$\underset{n\to \mathrm{\infty }}{lim sup}\frac{|S_n(\omega )|}{{\mathrm{\Lambda }}_n}\ge 8+\epsilon$$

for $\mathbb{P}$ almost every $\omega \in \mathrm{\Omega }$. Using Fubini's Theorem, this gives that for ${\mathbb{P}}^2$ almost every $({\omega }_1,{\omega }_2)\in {\mathrm{\Omega }}^2$, there is a $\{n_m({\omega }_1):m\in {\mathbb{Z}}^{+}\}\subset {\mathbb{Z}}^{+}$ such that $n_m({\omega }_1)$ increases to $\mathrm{\infty }$ so that the limit

$$\underset{m\to \mathrm{\infty }}{lim}\frac{S_{n_m({\omega }_1)}({\omega }_1)}{{\mathrm{\Lambda }}_{n_m(\omega )}}\ge 8+\epsilon$$

exists and

$$\underset{m\to \mathrm{\infty }}{lim inf}\frac{|S_{n_m({\omega }_1)}({\omega }_2)|}{{\mathrm{\Lambda }}_{n_m({\omega }_1)}}\ge \underset{m\to \mathrm{\infty }}{lim}\frac{S_{n_m({\omega }_1)}({\omega }_1)}{{\mathrm{\Lambda }}_{n_m(\omega )}}-\underset{m\to \mathrm{\infty }}{lim sup}\frac{|S_{n_m(\omega )}({\omega }_1)-S_{n_m(\omega )}({\omega }_2)|}{{\mathrm{\Lambda }}_{n_m({\omega }_1)}}\ge \epsilon$$

so that by Fubini's Theorem, we have an $\{n_m:m\in {\mathbb{Z}}^{+}\}\subset {\mathbb{Z}}^{+}$ such that $n_m$ increases to $\mathrm{\infty }$ and

$$\underset{m\to \mathrm{\infty }}{lim inf}\frac{|S_{n_m}({\omega }_2)|}{{\mathrm{\Lambda }}_{n_m}}\ge \epsilon$$

for $\mathbb{P}$ almost every ${\omega }_2\in \mathrm{\Omega }$. This contradicts Markov's Inequality owing to

$$\mathbb{E}\left[{\left(\frac{S_n}{{\mathrm{\Lambda }}_n}\right)}^2\right]=\frac{1}{2\log \log n}\to 0$$

hence completing the proof. $◻$

Proof of Lemma 3

As usual, we need to discuss some new ideas before we can move to our proof. We define

$${\mathrm{\Lambda }}_{\mu }(\xi ):=\log (M_{\mu }(\xi ))$$

and define the Legendre transform of ${\mathrm{\Lambda }}_{\mu }$ as

$$I_{\mu }(x):=sup\{\xi x-{\mathrm{\Lambda }}_{\mu }(\xi ):\xi \in \mathbb{R}\}$$

for $x\in \mathbb{R}$. Also, let ${\mathrm{\Xi }}_{\mu }:={\left({\mathrm{\Lambda }}_{\mu }^{\prime }\right)}^{-1}$.

Lemma 4 : There exists a $\delta \in (0,1]$ and a $K\in (0,\mathrm{\infty })$ such that $[m-\delta ,m+\delta ]\subset (\alpha ,\beta )$ and

$$|{\mathrm{\Lambda }}_{\mu }^{\prime \prime }(\mathrm{\Xi }(x))|\le K|{\mathrm{\Xi }}_{\mu }(x)|\le K|x-m|$$

and

$$|I_{\mu }(x)-\frac{(x-m{)}^2}{2{\sigma }^2}|\le K{|x-m|}^3$$

for all $x\in [m-\delta ,m+\delta ]$. In particular, if $0<\epsilon <\delta$, then

$$\mathbb{P}(|{\overline{S}}_n-m|\ge \epsilon )\le 2\exp [-n(\frac{{\epsilon }^2}{2{\sigma }^2}-K{\epsilon }^3)]$$

and if $|a-m|<\delta$, then

$$\mathbb{P}(|{\overline{S}}_n-m|<\epsilon )\ge (1-\frac{K}{n{\epsilon }^2})\exp [-n(\frac{|a-m{|}^2}{2{\sigma }^2}+K|a-m|(\epsilon +|a-m{|}^2))]$$

for any $\epsilon >0$.

Proof : Recall that we started with the assumption that our random variables have mean $0$ and variance $1$. So, we have ${\mathrm{\Lambda }}_{\mu }(0)={\mathrm{\Lambda }}_{\mu }^{\prime }(0)=0$ and ${\mathrm{\Lambda }}_{\mu }^{\prime \prime }(0)=1$ and hence ${\mathrm{\Xi }}_{\mu }(0)=0$ and ${\mathrm{\Xi }}_{\mu }^{\prime }(0)=1$. So, we can find an $M\in (0,\mathrm{\infty })$ and a $\delta \in (0,1]$ with $\alpha <-\delta <\delta <\beta$ for which

$$|{\mathrm{\Xi }}_{\mu }(x)-x|\le M|x{|}^2$$

whenever $|x|\le \delta$ and

$$|{\mathrm{\Lambda }}_{\mu }(\xi )-\frac{{\xi }^2}{2}|\le M|\xi {|}^3$$

whenever $|\xi |\le (M+1)\delta$. This immediately proves

$$|{\mathrm{\Xi }}_{\mu }(x)|\le (M+1)|x|$$

for $|x|\le \delta$ and the estimate for $I_{\mu }$ follows since $I_{\mu }(x)=\mathrm{\Xi }(x)x-{\mathrm{\Lambda }}_{\mu }({\mathrm{\Xi }}_{\mu }(x))$. $◻$

This gives us enough room to discuss our proof.

Proof of Lemma 3 : Begin by setting

$${\lambda }_n:=\frac{{\mathrm{\Lambda }}_n}{n}=\sqrt{\frac{2\log \log n}{n}}$$

wherever it is defined.

To prove the first part, we apply the upper bound of $\mathbb{P}(|{\overline{S}}_n-m|\ge \epsilon )$ obtained in Lemma 4 to see that

$$\mathbb{P}(\left|{\tilde{S}}_n\right|\ge R)=\mathbb{P}(\left|{\overline{S}}_n\right|\ge R{\lambda }_n)\le 2\exp [-n(\frac{R^2{\lambda }_n^2}{2}-K{R}^3{\lambda }_n^3)]$$

for sufficiently large $n\in {\mathbb{Z}}^{+}$.

To prove the next part of the lemma, we note

$$\mathbb{P}(|{\tilde{S}}_n-a|<\epsilon )=\mathbb{P}(|{\overline{S}}_n-a_n|<{\epsilon }_n)$$

where $a_n=a{\lambda }_n$ and ${\epsilon }_n=\epsilon {\lambda }_n$.So, using the lower bound on $\mathbb{P}(|{\overline{S}}_n-m|<\epsilon )$ obtained in Lemma 4 to conclude

$$\begin{array}{rl}\mathbb{P}(|{\tilde{S}}_n-a|<\epsilon )& \ge (1-\frac{K}{n{\epsilon }_n^2})\exp [-n(\frac{a_n^2}{2}+K|a_n|({\epsilon }_n+a_n^2))]\\ & \ge (1-\frac{K}{2{\epsilon }^2\log \log n})\exp [-(a^2+2K|a|(\epsilon +a^2{\lambda }_n))\log \log n]\end{array}$$

for sufficiently large $n$. $◻$

Acknowledgement : I'd like to thank Satvik Saha, who has been my partner in reading this proof, patiently answering my barrage of inane questions and making clever observations that I've shamelessly passed off as my own in this write-up. I feel safe admitting it here because, let’s be real, no one’s reading this far anyway.