David R. MacIver's Blog

Asymptotic behaviour of max(Z_n)

More on high variance strategies.

I was wondering what the asymptotic behaviour of \(\max(Z_n)\) was. It seems “obvious” that it should grow without bound, but it turns out that it grows really very slowly. It turns out that for \(n = 10^{10}\) it’s still less than 7.

I thought I would quickly verify that it does actually grow without bound.

Let \(T_n = \max Z_n\). Then \(E(T_n) = E(T_n | T_n < 0) P(T_n < 0) + E(T_n | T_n > 0) P(T_n > 0)\). But \(E(T_n | T_n < 0) \geq -1\) (because \(E(Z_1 | Z_1 < 0) = -1\) and \(T_n \geq Z_1\)$ and \(P(T_n \< 0) = 2\^{-n}\), so \(E(T_n) \\geq (1 - 2\^{-n}) E(T_n\|T_n \> 0) - 2\^{-n}\). So we need only concern ourselves with the positive behaviour.

Let \(S_n\) be a random variable with the distribution of \(T_n \| T_n \> 0\).

Consider \(t \> 0\). We want to show that for sufficiently large \(n\), \(E(S_n) \> t\).

Now for any \(s\), \(E(S_n) \\geq s P(S_n \\geq s)\), because \(S_n\) is always positive. So let \(s = 2t\). Now \(E(S_n) \\geq 2t P(S_n \\geq 2t)\).

But \(P(S_n \\geq s) \\geq P(T_n \\geq s) = 1 - F(s)\^n\) where \(F\) is the cdf of the standard normal distribution. So \(E(S_n) \\geq 2t (1 - F(2t)\^n)\).

But if \(n \\geq \\frac{\\log(\\frac{1}{2})}{\\log(F(2t))}\) then \(F(2t)\^n \\leq \\frac{1}{2}\) and so \(E(S_n) \\geq 2t (1 - \\frac{1}{2}) = t\).

Thus \(E(S_n)\) grows without bound and thus so does \(E(T_n)\).

This could be tightened up a bit to get the asymptotic behaviour of the growth, but I’m not that clear on what the asymptotic behaviour of $F(t)$ is so I haven’t worked through the details yet.