Tail bound for the truncated random harmonic series

Question

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

Answer 1

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$.

Answer 2

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.

Answer 3

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$.