# Tail bound for the truncated random harmonic series

Context: the distribution of the random harmonic series is touched upon in e.g. this and that question. However, in this case I am considering the partial sum of this series only.

Let $(X_k)_{1\leq k\leq\infty}$ be a sequence of i.i.d. Rademacher random variables, i.e. uniform on $\{-1,1\}$. For parameter $n\geq 1$, let $$H^{(n)}\stackrel{\rm def}{=} \sum_{k=1}^n \frac{X_k}{k}$$ be the "partial random harmonic sum."

What is the distribution of $H^{(n)}$, in particular what is its tail bound behavior?

Specifically: given $\delta > 0$,, what is the asymptotic behavior of $$\mathbb{P}\{ H^{(n)} \geq \delta \ln n\}$$ as $n\to\infty$?

Hoeffding/Chernoff bounds would apply, or more basically bounds on Rademacher sums; giving something, if I'm not mistaken, along the lines of $$\mathbb{P}\{ H^{(n)} \geq \delta \ln n\} \leq e^{-c \delta^2 \ln^2 n}$$

for some explicit constant $c \approx \frac{3}{\pi^2}$ (if I didn't screw up). But the bound seem very loose to me, and based on [1] (which deals with the non-truncated version) I would expect $\mathbb{P}\{ H^{(n)} \geq \delta \ln n\} = e^{-\Theta(n^\alpha \log^\beta n)}$ for some $\alpha >0$ and $\beta$. Is any such result known -- or, if it's not insanely hard to show, how can I obtain it?

[1] Montgomery-Smith S.J. (1990) The distribution of Rademacher sums. Proc. Amer. Math. Soc. 109:517522

• Remark: [1] yields the bound $e^{-n^{\delta/c}} \geq \mathbb{P} (H^{(n)} \geq \delta \ln (n)) \geq c^{-1} e^{-cn^{\delta c}}$ for some universal constant $c$ and all small enough $\delta$. – D. Thomine Jun 12 '16 at 1:33
• @D.Thomine I am not entirely clear how you derived that. In particular, are you using directly the statement after the main theorem, "An interesting example is"? If so, this applies to the full random harmonic series (not the partial sum), doesn't it? – Clement C. Jun 12 '16 at 3:23
• No, I had to redo the whole computations with the truncated series, but it isn't that bad. – D. Thomine Jun 12 '16 at 9:21

The answer is given by [1]. There is an absolute constant $c \geq 1$ such that the following holds.

By the Theorem, for all $t \geq 0$,

$$\mathbb{P} \left( H^{(n)} > K_n(t) \right) \leq e^{-\frac{t^2}{2}}$$

and

$$\frac{e^{-ct^2}}{c} \leq \mathbb{P} \left( H^{(n)} > \frac{K_n(t)}{c} \right),$$

where $K_n (t) = \inf \{\|x'\|_{\ell^1}+t\|x''\|_{\ell^2} \ : \ x'+x'' = x^{(n)}\}$ is an interpolating norm for the sequence $x^{(n)}=(1, 1/2, \ldots, 1/n, 0, 0, \ldots)$. By the equation in the middle of p. $518$,

$$\frac{K_n(t)}{c} \leq \sum_{k=1}^{\lfloor t^2\rfloor \wedge n} \frac{1}{k} + t \sqrt{\sum_{k=\lfloor t^2\rfloor \wedge n+1}^n \frac{1}{k^2}} \leq K_n (t).$$

I guess that this bound can most likely be improved with some analysis. Anyway, for $3/2 \leq t \leq \sqrt{n}$, and up to increasing the constant $c$, we get:

$$2 \ln (t) \leq K_n(t) \leq 2 c\ln(t),$$

whence:

$$\mathbb{P} \left( H^{(n)} > 2c \ln (t) \right) \leq e^{-\frac{t^2}{2}}$$

and:

$$\frac{e^{-ct^2}}{c} \leq \mathbb{P} \left( H^{(n)} > \frac{2 \ln (t)}{c} \right).$$

Let $\delta \in (0, c^{-1})$. In the former inequality, I use $t := n^{\frac{\delta}{2c}}$. In the later, I use $t := n^{\frac{c \delta}{2}}$. Then I get:

$$\frac{e^{-cn^{c \delta}}}{c} \leq \mathbb{P} \left( H^{(n)} > \delta \ln (n) \right) \leq e^{-\frac{n^{\delta/c}}{2}}.$$

This holds for all $\delta \in (0, c^{-1})$ and all $n \geq 2$.

• That seems right to me... thank you. I am trying to see if one can save a factor $c$ in the upper bound (and get that upper bound to work up to $\delta \in(0,1)$), I believe it should not be too hard. – Clement C. Jun 12 '16 at 18:48
• @ Clement C. : for the upper bound, the only problem is to get a better estimate of $K_n (t)$, which shouldn't be too hard (at worse, a bothersome optimization problem). – D. Thomine Jun 12 '16 at 19:31
• Yes, that's my feeling... I did something in that direction, although there is a sketchy part (in the definition of $t_\delta$, and then the assumption justified in hindsight that $t_\delta = o(n)$). I am making my own answer Community Wiki, in case anyone wants to update (or fix, if incorrect?) the argument. – Clement C. Jun 12 '16 at 19:41

The characteristic function of $H^{(n)}$ is not difficult to compute, it is just $\varphi^{(n)}(t)=\prod_{k=1}^{n}\cos\left(\frac{t}{k}\right)$.
We also have $$\mathbb{P}[|H^{(n)}|\leq \alpha] = \int_{-\infty}^{+\infty}\varphi^{(n)}(t)\,\widehat{\mathbb{1}_{(-\alpha,\alpha)}}(t)\,dt = \frac{1}{\pi}\int_{-\infty}^{+\infty}\text{sinc}(\alpha t)\,\varphi^{(n)}(t)\,dt\tag{1}$$ so by approximating $\varphi^{(n)}(t)$ with: $$\psi^{(n)}(t) = \prod_{k=1}^{n}\exp\left(-\frac{t^2}{2k^2}\right)\approx \exp\left(-\frac{\pi^2 t^2}{12}\right) \tag{2}$$ I would expect the LHS of $(1)$ to behave like $\frac{1}{a}\,\text{Erf}\left(\frac{a\sqrt{3}}{\pi}\right)$, with the chance to recover a tight bound for our probability from the continued fraction expansion for the $\text{Erfc}$ function. Such a bound is exactly of the form $$\mathbb{P}\left[|H^{(n)}|\geq \alpha\right] \approx e^{-K\alpha^2}\tag{3}$$ so I think you cannot really improve your seemingly loose bound.

You may also notice that $H^{(n)}$ has a bounded ($\leq \pi^2/3$) variance, hence the gaussian behaviour of $H^{(n)}$ for large $n$ should be ensured by some version of the central limit theorem.

• I had gotten as far as the product $\prod_{k=1}^n \cos\frac{t}{k}$ for the characteristic function, but was unsure what to do afterwards. But I'm still a bit on the fence about the approximation — "morally" speaking, doesn't it amounts to plugging in the CLT? – Clement C. Jun 11 '16 at 22:42
• @ClementC.: that is exactly what I mention in my updated answer :D – Jack D'Aurizio Jun 11 '16 at 22:43
• Oh, sorry, I hadn't realized there was an edit. So I reckon at its core, my question boils down to "is the CLT tight in this case." (I'll try and check to see what Berry-Esseen gives, for instance.) – Clement C. Jun 11 '16 at 22:44
• @ClementC.: I agree, and I believe the bound is tight, but I will run some simulations to be sure about it. Anyway, $\mathbb{E}[|H^{(n)}|^3]$ is bounded for sure. – Jack D'Aurizio Jun 11 '16 at 22:46

Following on D.Thomine's answer: trying to improve the upper bound. [NB: this is Community Wiki]

We have the sequence $(x_k)_{k\geq 1}\in \ell_1$ defined by $x_k = \frac{1}{k}\mathbb{1}_{\{k \leq n\}}$, with $\lVert x\rVert_1 = H_n \displaystyle\operatorname*{\sim}_{n\to\infty} \ln n$. Montgomery-Smith [1] showed that, for $c\stackrel{\rm def}{=} \frac{1}{4\ln 12}\simeq \frac{1}{10}$, we have $$\mathbb{P}\{ H^{(n)} > K_{1,2}(x,t) \} \leq e^{-t^2/2}, \qquad \mathbb{P}\{ H^{(n)} > cK_{1,2}(x,t) \} \geq ce^{-t^2/c} \tag{1}$$ where $K_{1,2} (x,t) = \inf\{\lVert x'\rVert_1+t\lVert x''\rVert_2 \ \colon\ x',x'' \in \ell_2,\ x'+x'' = x\}$.

In particular, it directly follows that $K_{1,2} (x,t) \leq \lVert x\rVert_1 = H_n$. Moreover, the formula of Holmstedt mentioned in [1] also implies that, for $t\leq \sqrt{n}$, $K_{1,2} (x,t)\geq H_{\lfloor t^2\rfloor} \displaystyle\operatorname*{\sim}_{t\to\infty} 2\ln t$, and actually that for all $t$, $$H_n \geq K_{1,2}(x,t) \geq \min( H_{\lfloor t^2\rfloor}, H_n ) \tag{2}$$ We can use this to get what we want for fixed $\delta \in(0,1)$: let $t_\delta \geq 0$ be "the" value such that $$\delta\ln n \leq K_{1,2}(x,t_\delta) \leq \delta\ln n + o(1)$$ which in particular, given (2) and since $\delta < 1$, implies that $t_\delta\leq \sqrt{n}$ (we assume $n$ big enough for asymptotics to kick in).

From Holmstedt's bound again, we get $$K_{1,2}(x,t_\delta) \geq H_{\lfloor t_\delta^2\rfloor} + t_\delta\sqrt{\sum_{k=\lfloor t_\delta^2\rfloor+1}^n \frac{1}{k^2}} \operatorname*{=}_{t\to\infty} 2\ln t_\delta + \gamma + 1 + o(1)$$ (assuming $t_\delta = o(n)$) so that $\delta\ln n = 2\ln t_\delta + \gamma + 1 + o(1)$, and $t_\delta = e^{\frac{\gamma+1}{2}+o(1)} n^{\frac{\delta}{2}}$.

The probability we want to bound is then $$\mathbb{P}\{ H^{(n)} > K_{1,2}(x,t_\delta) \} \leq e^{-t_\delta^2/2} = e^{-e^{\gamma+1+o(1)} n^{\delta}/2} = e^{-\tau n^{\delta} + o(n^\delta)}$$ with $\tau \stackrel{\rm def}{=} \frac{e^{\gamma+1}}{2} \simeq 0.76$.