4
$\begingroup$

Consider the following process for generating a random sample:

  • Sample $X_1, X_2, \dots, X_n \sim \mathcal{N}(0,1)$
  • Compute $M = \max\limits_i |X_i|$
  • Scale the values to get $Z_i = X_i / M$

Can we say anything about the convergence of distribution of $Z_i$ as $n\to\infty$?

The $Z_i$s are clearly identically distributed, but they aren't independent since for any $n$ almost certainly exactly 1 $Z_i$ will take the value -1 or 1.

Here's what the points are distributed like for various values of $n$ (65,000 trials each):

$n=16$ enter image description here

$n=64$ enter image description here

$n=4,096$ enter image description here

These all use 100 evenly spaced bins, hence the spikes at the ends for the smaller values of $n$. Does the limiting distribution have a name?

Edit: I should clarify that the obvious candidate thing for it to converge to would be a point mass on 0, but I'm not sure whether it does that or not.

Renamed $Y$ to $Z$ for consistency with the plots.

$\endgroup$
12
  • $\begingroup$ If the cdf for $Y_n$ is $F_n$, and the cdf of the standard normal is $\Phi$, then I would expect $F_n(x E[M_n]) \to \Phi(x)$. $\endgroup$
    – Matt F.
    May 24, 2023 at 1:45
  • $\begingroup$ I don't think the support works out there does it? $\endgroup$ May 24, 2023 at 1:54
  • $\begingroup$ This q&a may be helpful: math.stackexchange.com/questions/89030/…. $\endgroup$
    – jbowman
    May 24, 2023 at 2:22
  • 1
    $\begingroup$ For some $N$, $n > N \implies E[M_n] > 1$, at which point $n > N \implies F_n(-2 E[M_n]) = 0$, but $\Phi(-2) \neq 0$ $\endgroup$ May 24, 2023 at 3:45
  • 1
    $\begingroup$ Maybe add the tag "extreme-value"? $\endgroup$
    – Yves
    May 24, 2023 at 12:34

2 Answers 2

5
$\begingroup$

$Z$ converges to point mass at zero. We know $M_n\stackrel{p}{\to}\infty$ since the Normal distribution is unbounded.

So, for any fixed $\epsilon$ and any $i$, $$P(|Z_i|>\epsilon)=P(|X_i/M_n|>\epsilon)\to 0$$ implying $Z_i\stackrel{p}{\to} 0$ and $Z_i\stackrel{d}{\to} 0$.

The convergence will be quite slow, because $M_n$ increases roughly as $\sqrt{\log n}$. It's going to be relatively hard to get convincing simulations for the Gaussian case.

$\endgroup$
7
  • $\begingroup$ Usually this kind of convergence statement is of little use, as in this case, because the sequence, properly normalized, does converge to a Normal distribution. $\endgroup$
    – whuber
    May 25, 2023 at 10:57
  • $\begingroup$ This is actually for a practical application, in which the choice of normalizing is not available: arxiv.org/abs/2305.14314 (There's a lot of stuff going on in that paper, only the NF4 data type stuff is relevant here) $\endgroup$ May 25, 2023 at 18:14
  • 1
    $\begingroup$ That's a fascinating paper, thank you. But this sounds rather like an X/Y problem: if the issue is with low-precision floating point computation, the question you asked scarcely looks relevant. $\endgroup$
    – whuber
    May 25, 2023 at 19:42
  • $\begingroup$ It's relevant because the way the quantization algorithm works is to take a batch of values, then divide them by the max absolute value to scale them into [-1, 1]. The authors propose a discretization of [-1, 1] based on quantiles of the normal distribution. The reason for my question is that I was wondering whether there was some known distribution the quantiles should be calculated from instead. $\endgroup$ May 25, 2023 at 21:18
  • 1
    $\begingroup$ That doesn't sound like "the choice of normalizing is not available"! $\endgroup$
    – whuber
    May 26, 2023 at 14:42
3
$\begingroup$

The following demonstration is not rigorous, but it's correct :-).

Because the Normal distribution is continuous, there is almost surely a unique maximum absolute value. Thus, the chance that $|Z_n|=1$ is $1/n.$ In all other cases $Z_n = X_n/X_i$ where $X_i$ attains the maximum absolute value. Furthermore, for extremely large $n,$ the standard deviation of the distribution of that maximum $M_n$ shrinks towards zero as $n$ grows. Consequently, $M_n$ is nearly constant and will necessarily be close to its median.

Because the CDF of the maximum is $\Phi(x)^n,$ its median $m_n$ is where $\Phi(m_n)^n = 1/2,$ so that

$$M_n \approx m_n = \Phi^{-1}(2^{-1/n}).$$

Thus,

$Z_n$ will (with probability $1-1/n$) be arbitrarily close to $X_n/m_n,$ which has a mean-zero Normal distribution with standard deviation $1/m_n.$

In a simulation of $5\,000$ samples, each of size $50\,000,$ I computed all the $Z_n.$ Here are histograms for four selected values of $n.$ Over them I have plotted the Normal approximation. The p-value is that obtained by removing the values of $Z_n$ equal to $1$ (we know they contribute a small "atom") and applying a Kolmogorov-Smirnov test to the rest.

enter image description here

Even with this $5\,000$ samples, the KS test -- which is notorious for its power to distinguish Normal from non-Normal data (some people on this site have claimed it will always reject Normality on any dataset this large) -- does not reject the foregoing claim when $n = 50\,000.$

More specifically, upon dividing $Z_n$ by the standard deviation $1/m_n,$ we find the distribution of $Z_n \Phi^{-1}(2^{-1/n})$ converges to the standard Normal distribution. An immediate consequence is that the distribution of $Z_n$ converges to zero at a rate given by $1 / \Phi^{-1}(2^{-1/n}).$ This is a slow rate, because a crude approximation gives $m_n = O(1/\sqrt{\log n}).$ For instance, $1/m_n=1/10$ for $n \approx e^{100} \approx 10^{43}$ and a standard deviation of $1/10$ is still appreciable. Thus, in any application it would usually be unwise to approximate $Z_n$ by $0:$ use this limiting Normal distribution instead as a better approximation.

$\endgroup$
7
  • 1
    $\begingroup$ Thanks for the analysis! I'll try this out as a quantization grid and see how it works. $\endgroup$ May 26, 2023 at 21:07
  • $\begingroup$ I think that should be $Z_n \times \Phi^-1(2^{-1/n})$ right? If you divide by a quantity which is growing in $n$ it'll still converge to 0. $\endgroup$ May 26, 2023 at 21:56
  • $\begingroup$ Of course--thanks for the correction. I see another typo to fix, too... $\endgroup$
    – whuber
    May 26, 2023 at 21:59
  • $\begingroup$ There's one other issue, which is that rather than $\Phi^{-1}$, one should use the inverse CDF of the half-normal distribution (since $M$ is the max absolute value), but that's easy to implement. $\endgroup$ May 26, 2023 at 22:05
  • $\begingroup$ Actually, that's not needed -- but it's a great suggestion and would be better insofar as it more clearly indicates the role played by this quantity. $\endgroup$
    – whuber
    May 26, 2023 at 22:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.