Let $X^i\in \mathbb R^d$ be iid. random variables for $i=1$ to $n$.
Assume $\mathbb E[X^i]=0$ and the covariance matrix $\mathbb C[X^i] = \mathbb E[X^iX^{iT}] = I$ is the identity matrix.


Define $S^k=\frac{1}{\sqrt k}\sum\_{i=1}^k X^i$, so that $\mathbb C[S^k] = I$.


**Question**


We would like to prove a bound on the form
$$
\Pr\left[\sup\_{k=1}^n\left\|S^k\right\|\_2> Kt\right]<\frac{1}{t^2}\tag{1}$$
for some universal constant $K$ or perhaps some slowly increasing function in $n$, like $K(n)=\sqrt{\log n}$ or $K(n)=\sqrt{2\log\log n}$ as we would expect from the [Law of the Iterated Logarithm](https://en.wikipedia.org/wiki/Law_of_the_iterated_logarithm).


(*Updated:* Actually the Iterated Logarithm probably suggests that defining $S^k=\frac{1}{\sqrt {k\log\log k}}\sum\_{i=1}^k X^i$ would be the correct normalization.)


**Approach 1**


One approach is a union bound using the [multivariate Chebyshev bound](https://en.wikipedia.org/wiki/Multidimensional_Chebyshev%27s_inequality):
$$\Pr\left[\left\|S^k\right\|\_2> s\right]<\frac{d}{s^2}.$$


Taking $s=t \sqrt {dn}$ we get by a union bound
$\Pr\left[\sup\_{k=1}^n\left\|S^k\right\|\_2> t\sqrt{dn}\right]<\frac{1}{t^2}.$
Slightly stronger we might take the $t$ value for each $k$ to be an increasing sequence like $t\_k=\sqrt{k\log k}$.
This would then give us
$$\Pr\left[\sup\_{k=1}^n\frac{1}{\sqrt{k}\log k}\left\|S^k\right\|\_2> K t\right]<\frac{1}{t^2}$$
for some constant $K$. However this is still much worse than we would expect.


**Approach 2**


Alternatively, since $\sqrt{k}S^k$ is a martingale, we can use Doob's inequality on the individual coordinates to get


$$\Pr\left[\sup\_{k=1}^n(\sqrt{k}S^k\_i)^2> t\right]<\frac{\mathbb E[(\sqrt{n}S^n\_i)^2]}{t}$$
which implies
$\Pr\left[\sup\_{k=1}^n \sqrt{\frac{k}{n}} S^k\_i > t\right]<\mathbb E[(S^n\_i)^2]/t^2$
and so by a union bound over the $d$ coordiantes,
$$
\Pr\left[\sup\_{k=1}^n\sqrt{\frac{k}{n}}\left\|S^k\right\|\_2> t\right]
\le
\sum\_{i=1}^d \Pr\left[\sup\_{k=1}^n \sqrt{\frac{k}{n}} S^k\_i > t\sqrt{d}\right]
\le\frac{\mathbb E[\left\|S^n\right\|\_2^2]}{t^2d}
=\frac{1}{t^2}.
$$
This is closer to what we were aiming for, but the factor of $\sqrt{\frac{k}{n}}$ still imposes a much stronger requirement on the early terms than we were aiming for.


**Question again**


Am I wrong to expect the inequality in $(1)$ given only the first and second moments are known on the $X^i$?


In that case, say I also know the moment generating function of the $X^i$s, can I somehow use this knowledge with the Doob inequality or other vector-Martingale inequalities?



Expected supremum of normalised random walk
Let $X\_i:=X^i$, $S\_k:=\sum\_1^n X\_i$, $T\_k:=S\_k/\sqrt k$, $|\cdot|:=\|\cdot\|\_2$, $n\in\{1,2,\dots\}$, and $m:=\lceil\log\_2 n\rceil$, so that $2^m\ge n$. Then 
\begin{equation}
 \max\_{k=1}^n|T\_k|\le\max\_{k=1}^{2^m}|T\_k|
 =\max\_{j=0}^m\max\_{2^{j-1}<k\le 2^j}|T\_k|
 \le\max\_{j=0}^m 2^{-(j-1)/2}\max\_{2^{j-1}<k \le 2^j}|S\_k|.
\end{equation}
Hence, for any real $t>0$
\begin{multline}
 P\big(\max\_{k=1}^n|T\_k|\ge t\big)
 \le\sum\_{j=0}^m P\big(\max\_{k=1}^{2^j}|S\_k|\ge 2^{(j-1)/2}t\big) \\ 
 \le\sum\_{j=0}^m \frac{E|S\_{2^j}|^2}{2^{j-1}t^2}
 =(m+1)\frac{2d}{t^2}\le\frac{2(2+\log\_2 n)d}{t^2}; 
\end{multline}
the second inequality in the latter display is an instance of Doob's inequality, which holds because $(S\_k)$ is a martingale and hence $(|S\_k|^2)$ is a submartingale. 


Equivalently, for any real $s>0$
\begin{equation}
 P\big(\max\_{k=1}^n|T\_k|\ge s\sqrt{2+\log\_2 n}\big)
 \le\frac{2d}{s^2}. 
\end{equation}


So, the extra factor is $\sqrt{2+\log\_2 n}$, as you expected. 


