Return to Answer

Let $Z \sim \mathcal{N}(0,\sigma^2 I_n)$ be an $n$-dimensional Gaussian vector with independent $\mathcal{N}(0,\sigma^2)$ components. Consider the family of binary vectors in $\mathbb{R}^n$ with exactly $k$ ones, denoted by $\mathcal{X}_k = \{x \in \{0,1\}^n : |x|_1 = k\}$, where $1 \leq k \leq \lfloor n/2 \rfloor$. Define $Y = \sup_{X \in \mathcal{X}_k} |\langle Z, X \rangle|^2$.

Now consider the vector $x \in \mathbb{R}^n$ and define $|x|_1 = \sum_{i=1}^n |x_i|$ and $\|x\|_2 = \sqrt{\sum_{i=1}^n x_i^2}$. The set $\mathcal{X}_k$, equipped with the Euclidean metric $d(x,y) = \|x-y\|_2$, has a diameter of $\sqrt{2k}$. For each $X \in \mathcal{X}_k$, let $Z_X = \langle Z,X\rangle = \sum_{i=1}^n Z_i x_i$ which follows a $\mathcal{N}(0,\sigma^2 k)$ distribution only when $X$ has $k$ ones and the rest are zeros. We also define the Gaussian process $Y(X) = \sum_{i=1}^n w_i x_i$ where $w_i$ are i.i.d. $\mathcal{N}(0,\sigma^2)$ variables.

Considering any two vectors $X, X' \in \mathcal{X}_k$, the covariance $\mathrm{Cov}(Z_X, Z_{X'}) = \sigma^2 \sum_{i=1}^n x_i x'_i$, which is equal to $\sigma^2 k$ if and only if $X$ and $X'$ overlap completely in their nonzero entries. Similarly, $\mathrm{Cov}(Y(X), Y(X')) = \sigma^2 \sum_{i=1}^n x_i x'_i$. Therefore, for any $X, X' \in \mathcal{X}_k$, $\mathrm{Cov}(Z_X, Z_{X'}) = \mathrm{Cov}(Y(X), Y(X'))$.

By applying the Sudakov-Fernique inequality, which is applicable since $\mathcal{X}_k$ is a finite subset of Euclidean space and the Gaussian covariances obey the relationship described, we have:

$$ \mathbb{E}[\sup_{X \in \mathcal{X}_k} Z_X] \leq \mathbb{E}[\sup_{X \in \mathcal{X}_k} Y(X)] $$

Using the Dudley entropy integral bound with an absolute constant $K > 0$ and noting that $|\mathcal{X}_k| = {n \choose k} \leq (\frac{en}{k})^k$, we obtain:

$$ \mathbb{E}[\sup_{X \in \mathcal{X}_k} Y(X)] \leq K\int_0^{\sqrt{2k}} \sqrt{\log |\mathcal{X}_k|\epsilon^{-1}} d\epsilon \leq C_1 \sigma \sqrt{2k\log(\frac{en}{k})} < \infty $$

for some universal constant $C_1 > 0$, confirming that $\mathbb{E}[Y]$ is indeed finite.

To derive the concentration inequality, we employ the Borell-TIS (Tsirelson-Ibragimov-Sudakov) inequality. This inequality states that if $Y$ is a centered Gaussian process, then for any $t > 0$,

$$ \mathbb{P}(|Y - \mathbb{E}[Y]| \geq t) \leq 2\exp\left(-\frac{t^2}{2\sigma^2_Y}\right) $$

where $\sigma^2_Y$ is the supremum of the variance of the process. In our context, $Y$ is the supremum of a Gaussian process indexed by vectors in $\mathcal{X}_k$, and $\sigma^2_Y = \sigma^2 k$ reflects the maximum variance of $Z_X$ across all $X \in \mathcal{X}_k$.

The refinement considers the cardinality of $\mathcal{X}_k$. By employing a union bound over the elements of $\mathcal{X}_k$, we adjust the concentration inequality to account for the multiple comparisons being made. This leads to:

$$ \mathbb{P}(|Y - \mathbb{E}[Y]| > t) \leq 2|\mathcal{X}_k|e^{-\frac{t^2}{2\sigma^2 k}} $$

So the probability of a large deviation decreases exponentially with $t^2$, but the rate of decrease is moderated by the cardinality of $\mathcal{X}_k$.

Let $Z \sim \mathcal{N}(0,\sigma^2 I_n)$ be an $n$-dimensional Gaussian vector with independent $\mathcal{N}(0,\sigma^2)$ components. Consider the family of binary vectors in $\mathbb{R}^n$ with exactly $k$ ones, denoted by $\mathcal{X}_k = \{x \in \{0,1\}^n : |x|_1 = k\}$, where $1 \leq k \leq \lfloor n/2 \rfloor$. Define $Y = \sup_{X \in \mathcal{X}_k} |\langle Z, X \rangle|^2$.

Now consider the vector $x \in \mathbb{R}^n$ and define $|x|_1 = \sum_{i=1}^n |x_i|$ and $\|x\|_2 = \sqrt{\sum_{i=1}^n x_i^2}$. The set $\mathcal{X}_k$, equipped with the Euclidean metric $d(x,y) = \|x-y\|_2$, has a diameter of $\sqrt{2k}$. For each $X \in \mathcal{X}_k$, let $Z_X = \langle Z,X\rangle = \sum_{i=1}^n Z_i x_i$ which follows a $\mathcal{N}(0,\sigma^2 k)$ distribution only when $X$ has $k$ ones and the rest are zeros. We also define the Gaussian process $G(X) = \sum_{i=1}^n w_i x_i$ where $w_i$ are i.i.d. $\mathcal{N}(0,\sigma^2)$ variables.

Considering any two vectors $X, X' \in \mathcal{X}_k$, the covariance $\mathrm{Cov}(Z_X, Z_{X'}) = \sigma^2 \sum_{i=1}^n x_i x'_i$, which is equal to $\sigma^2 k$ if and only if $X$ and $X'$ overlap completely in their nonzero entries. Similarly, $\mathrm{Cov}(G(X), G(X')) = \sigma^2 \sum_{i=1}^n x_i x'_i$. Therefore, for any $X, X' \in \mathcal{X}_k$, $\mathrm{Cov}(Z_X, Z_{X'}) = \mathrm{Cov}(G(X), G(X'))$.

By applying the Sudakov-Fernique inequality, which is applicable since $\mathcal{X}_k$ is a finite subset of Euclidean space and the Gaussian covariances obey the relationship described, we have:

$$ \mathbb{E}[\sup_{X \in \mathcal{X}_k} Z_X] \leq \mathbb{E}[\sup_{X \in \mathcal{X}_k} G(X)] $$

Using the Dudley entropy integral bound with an absolute constant $K > 0$ and noting that $|\mathcal{X}_k| = {n \choose k} \leq (\frac{en}{k})^k$, we obtain:

$$ \mathbb{E}[\sup_{X \in \mathcal{X}_k} G(X)] \leq K\int_0^{\sqrt{2k}} \sqrt{\log |\mathcal{X}_k|\epsilon^{-1}} d\epsilon \leq C_1 \sigma \sqrt{2k\log(\frac{en}{k})} < \infty $$

for some universal constant $C_1 > 0$, confirming that $\mathbb{E}[Y]$ is indeed finite.

To derive the concentration inequality, we employ the Borell-TIS (Tsirelson-Ibragimov-Sudakov) inequality. This inequality states that if $Y$ is a centered Gaussian process, then for any $t > 0$,

$$ \mathbb{P}(|Y - \mathbb{E}[Y]| \geq t) \leq 2\exp\left(-\frac{t^2}{2\sigma^2_Y}\right) $$

where $\sigma^2_Y$ is the supremum of the variance of the process. In our context, $Y$ is the supremum of a Gaussian process indexed by vectors in $\mathcal{X}_k$, and $\sigma^2_Y = \sigma^2 k$ reflects the maximum variance of $Z_X$ across all $X \in \mathcal{X}_k$.

The refinement considers the cardinality of $\mathcal{X}_k$. By employing a union bound over the elements of $\mathcal{X}_k$, we adjust the concentration inequality to account for the multiple comparisons being made. This leads to:

$$ \mathbb{P}(|Y - \mathbb{E}[Y]| > t) \leq 2|\mathcal{X}_k|e^{-\frac{t^2}{2\sigma^2 k}} $$

So the probability of a large deviation decreases exponentially with $t^2$, but the rate of decrease is moderated by the cardinality of $\mathcal{X}_k$.

We will be using the following lemmas:

Lemma 6.4 (from Probability in High Dimension): For zero-mean subgaussian random variables $Y_1, ..., Y_k$, a constant $c$ exists such that $$E\left[\max_{i \leq k} Y_i\right] \leq c \max_i |Y_i|_{\text{subgaussian}} \sqrt{\log k}$$

Lemma 6.19 (from Probability in High Dimension): For $(\epsilon^2)$-subgaussian random variables $Y_1, ..., Y_k$ and any $t > 0$, $$P\left(\max_{1 \leq i \leq k} Y_i \geq t \right) \leq 2k\exp\left(-\frac{t^2}{2\epsilon^2}\right)$$

Consider $Z_1, ..., Z_n$ as independent standard normal random variables and $X_k$ as binary vectors of length $n$ with $k$ ones, each with unit Euclidean norm. For any $X \in X_k$, the variable $Z^T X$ is Gaussian with zero mean, implying $E[Z^T X] = 0$. The distribution of $Z^T X$ remains Gaussian due to the properties of Gaussian distributions, where the linear combination of Gaussian variables is also Gaussian. Given that each component of $Z$ is standard normal and $X$ has a unit norm, the variance of $Z^T X$ is 1, making it a standard normal variable.

To apply the subgaussian norm definition, $|Y|_{\psi_2} = \inf \{ t > 0 : E[\exp(Y^2 / t^2)] \leq 2 \}$, we note that for standard Gaussian variables, this norm is a constant factor. Specifically, for a standard normal variable, the subgaussian norm can be directly related to its variance, leading to the identification of $\sigma^2 = 1$ for $Z^T X$. This quantifies the tail behavior, with its value being 1 reflecting the standard deviation of the Gaussian distribution.

Using Lemma 6.4, the expectation of the maximum deviation of $Z^T X$ from zero, for any $X$ in the set $X_k$, is bounded as follows: $$E\left[\max_{X \in X_k} \left|Z^T X\right|\right] \leq c \sigma \sqrt{\log k}$$ where $c$ is a constant for zero-mean subgaussian random variables, as established in Lemma 6.4, and $\sigma = 1$ in our case. This equation provides an upper limit on the expected maximum deviation, using the logarithmic relationship with $k$ to illustrate how the expected maximum grows as the number of vectors in $X_k$ increases.

Using Lemma 6.19, we derive the tail probability bound for the maximum deviation of $Z^T X$ exceeding a threshold $t$: $$P\left(\max_{X \in X_k} \left|Z^T X\right| \geq t \right) \leq 2k\exp(-t^2/(2\sigma^2))$$ Here, $\sigma^2 = 1$ represents the squared subgaussian norm of $Z^T X$, and highlights the rapid decrease in the probability of observing extreme deviations as $t$ increases.

Let $Z \sim \mathcal{N}(0,\sigma^2 I_n)$ be an $n$-dimensional Gaussian vector with independent $\mathcal{N}(0,\sigma^2)$ components. Consider the family of binary vectors in $\mathbb{R}^n$ with exactly $k$ ones, denoted by $\mathcal{X}_k = \{x \in \{0,1\}^n : |x|_1 = k\}$, where $1 \leq k \leq \lfloor n/2 \rfloor$. Define $Y = \sup_{X \in \mathcal{X}_k} |\langle Z, X \rangle|^2$.

Now consider the vector $x \in \mathbb{R}^n$ and define $|x|_1 = \sum_{i=1}^n |x_i|$ and $\|x\|_2 = \sqrt{\sum_{i=1}^n x_i^2}$. The set $\mathcal{X}_k$, equipped with the Euclidean metric $d(x,y) = \|x-y\|_2$, has a diameter of $\sqrt{2k}$. For each $X \in \mathcal{X}_k$, let $Z_X = \langle Z,X\rangle = \sum_{i=1}^n Z_i x_i$ which follows a $\mathcal{N}(0,\sigma^2 k)$ distribution only when $X$ has $k$ ones and the rest are zeros. We also define the Gaussian process $Y(X) = \sum_{i=1}^n w_i x_i$ where $w_i$ are i.i.d. $\mathcal{N}(0,\sigma^2)$ variables.

Considering any two vectors $X, X' \in \mathcal{X}_k$, the covariance $\mathrm{Cov}(Z_X, Z_{X'}) = \sigma^2 \sum_{i=1}^n x_i x'_i$, which is equal to $\sigma^2 k$ if and only if $X$ and $X'$ overlap completely in their nonzero entries. Similarly, $\mathrm{Cov}(Y(X), Y(X')) = \sigma^2 \sum_{i=1}^n x_i x'_i$. Therefore, for any $X, X' \in \mathcal{X}_k$, $\mathrm{Cov}(Z_X, Z_{X'}) = \mathrm{Cov}(Y(X), Y(X'))$.

By applying the Sudakov-Fernique inequality, which is applicable since $\mathcal{X}_k$ is a finite subset of Euclidean space and the Gaussian covariances obey the relationship described, we have:

$$ \mathbb{E}[\sup_{X \in \mathcal{X}_k} Z_X] \leq \mathbb{E}[\sup_{X \in \mathcal{X}_k} Y(X)] $$

Using the Dudley entropy integral bound with an absolute constant $K > 0$ and noting that $|\mathcal{X}_k| = {n \choose k} \leq (\frac{en}{k})^k$, we obtain:

$$ \mathbb{E}[\sup_{X \in \mathcal{X}_k} Y(X)] \leq K\int_0^{\sqrt{2k}} \sqrt{\log |\mathcal{X}_k|\epsilon^{-1}} d\epsilon \leq C_1 \sigma \sqrt{2k\log(\frac{en}{k})} < \infty $$

for some universal constant $C_1 > 0$, confirming that $\mathbb{E}[Y]$ is indeed finite.

To derive the concentration inequality, we employ the Borell-TIS (Tsirelson-Ibragimov-Sudakov) inequality. This inequality states that if $Y$ is a centered Gaussian process, then for any $t > 0$,

$$ \mathbb{P}(|Y - \mathbb{E}[Y]| \geq t) \leq 2\exp\left(-\frac{t^2}{2\sigma^2_Y}\right) $$

where $\sigma^2_Y$ is the supremum of the variance of the process. In our context, $Y$ is the supremum of a Gaussian process indexed by vectors in $\mathcal{X}_k$, and $\sigma^2_Y = \sigma^2 k$ reflects the maximum variance of $Z_X$ across all $X \in \mathcal{X}_k$.

The refinement considers the cardinality of $\mathcal{X}_k$. By employing a union bound over the elements of $\mathcal{X}_k$, we adjust the concentration inequality to account for the multiple comparisons being made. This leads to:

$$ \mathbb{P}(|Y - \mathbb{E}[Y]| > t) \leq 2|\mathcal{X}_k|e^{-\frac{t^2}{2\sigma^2 k}} $$

So the probability of a large deviation decreases exponentially with $t^2$, but the rate of decrease is moderated by the cardinality of $\mathcal{X}_k$.

For a concentration bound, we decompose $\mathbf{Y}$ by introducing random variables $\mathbf{Y}_i = z_i^2 x_i$, where $\mathbf{x}_i$ denotes the $\mathbf{i}$-th coordinate of $\mathbf{X} \in X_k$. Then $\mathbf{Y} = \sum_{i=1}^n \mathbf{Y}_i$. Assuming vectors $\mathbf{X} \in X_k$ are chosen uniformly at random, the $\mathbf{Y}_i$ become independent for a fixed $\mathbf{X}$ due to the independence of the $z_i$. To apply Bernstein's inequality, we must establish:

• Mean: Given $z_i \sim \mathcal{N}(0, \sigma^2)$ and $\mathbf{x}_i$ has a binary distribution with $P(\mathbf{x}_i=1) = \frac{k}{n}$. $$\mathbb{E}[\mathbf{Y}_i] = \mathbb{E}[z_i^2] \mathbb{E}[\mathbf{x}_i] = \sigma^2 \cdot \frac{k}{n}$$

• Variance: We have $$\operatorname{Var}(\mathbf{Y}_i) = \mathbb{E}[z_i^4] \mathbb{E}[\mathbf{x}_i^2] - (\mathbb{E}[z_i^2] \mathbb{E}[\mathbf{x}_i])^2 = \mathbb{E}[z_i^4] \cdot \frac{k}{n} - (\sigma^2 \cdot \frac{k}{n})^2$$

and $$\sum_{i=1}^n \operatorname{Var}[\mathbf{Y}_i] = n \cdot \left( 3\sigma^4 \cdot \frac{k}{n} - \sigma^4 \left(\frac{k}{n}\right)^2 \right)$$ Applying Bernstein's inequality gives: $$\mathbb{P}\left(\left|\sum_{i=1}^n Y_i - \mathbb{E}\left[\sum_{i=1}^n Y_i\right]\right| > t\right) \leq 2\exp\left(\frac{-t^2/2}{\sum_{i=1}^n \text{Var}[Y_i] + Mt/3}\right)$$ Given that for a normal distribution with variance $\sigma^2$, $\mathbb{E}[z_i^4] = 3\sigma^4$, we would then have: $$\operatorname{Var}(\mathbf{Y}_i) = 3\sigma^4 \cdot \frac{k}{n} - \sigma^4 \left(\frac{k}{n}\right)^2$$

We can calculate $M$ using the 99th percentile of the chi-squared distribution with 1 degree of freedom, scaled by $\sigma^2$. The 99th percentile of a chi-squared distribution with 1 degree of freedom is approximately $6.635$. Thus, for $z_i^2$, $M = 6.635 \cdot \sigma^2$. Substituting our established mean, variance, and almost-sure bound, we get the concentration inequality for $Y$: $$\mathbb{P}\left(\left|\sum_{i=1}^n \mathbf{Y}_i - nk \cdot \sigma^2 \right| > t\right) \leq 2\exp\left(\frac{-t^2/2}{\sum_{i=1}^n \operatorname{Var}[\mathbf{Y}_i] + Mt/3}\right)$$ $$\mathbb{P}\left(\left|\sum_{i=1}^n \mathbf{Y}_i - \mathbb{E}\left[\sum_{i=1}^n \mathbf{Y}_i\right]\right| \right) \leq 2\exp\left(-\frac{t^2}{2(\sigma^2 + Mt/3)}\right)$$

Simulations can be used to validate the concentration inequality and explore influences on bound tightness. I ran some simulations and there seemed to be support for the concentration inequality across a range of $n$ and $k$ values. An increase in the sparsity parameter $k$ leads to a higher variability in $Y$, evidenced by the rise in empirical tail probabilities. So basically the more non-zero components in the vector $X$ contribute to greater dispersion in the sum of squared variables, aligning with theoretical expectations. Also, the impact of dimensionality $n$ on the concentration properties of $Y$) is evident, with larger dimensions amplifying the effects of sparsity on variability. The simulations further validate the theoretical predictions provided by Bernstein's inequality, demonstrating its efficacy in bounding deviations from the expected sum.

Here is some python code used for the simulation:

import numpy as np

def gen_Y(n, k, sigma, trials):
    results = []
    for _ in range(trials):
        Z = np.random.randn(n) * sigma  # Generate Gaussian random variables
        X = np.random.choice([0, 1], size=n, p=[1 - k/n, k/n])  # Generate X vector with specified sparsity
        Y = np.sum(Z**2 * X)  # Calculate Y as the sum of Y_i = z_i^2 * x_i
        results.append(Y)
    return results

def theoretical_bound(n, k, sigma, t, M=3):
    # Assuming M as a placeholder for the maximum deviation bound for simplification
    var_Y_i = (k/n) * 2 * sigma**4 + (k/n) * (1 - (k/n)) * sigma**4
    sum_var_Y_i = n * var_Y_i
    bound = 2 * np.exp(-t**2 / (2 * (sum_var_Y_i + M * t / 3)))
    return bound

n_values = [10, 50, 100]
k_values = [5, 20, 35]
sigma = 1
t = 1  # Example threshold value
trials = 10000
simulation_results = []

for n in n_values:
    for k in k_values:
        # Ensure k is not greater than n
        if k <= n:
            Y_vals = gen_Y(n, k, sigma, trials)
            avg_Y = np.mean(Y_vals)
            tail_bound = theoretical_bound(n, k, sigma, t)
            tail_count = np.sum(np.abs(Y_vals - avg_Y) > t)
            tail_prob = tail_count / trials
            simulation_results.append((n, k, avg_Y, tail_bound, tail_count, tail_prob))
        else:
            print(f"Skipping invalid parameters: n = {n}, k = {k} (k must be <= n)")

for result in simulation_results:
    print(f"n: {result[0]}, k: {result[1]}, Avg Y: {result[2]:.3f}, Tail Bound: {result[3]:.3f}, Tail Count: {result[4]}, Empirical Tail Prob: {result[5]:.4f}")

We will be using the following lemmas:

Lemma 6.4 (from Probability in High Dimension): For zero-mean subgaussian random variables $Y_1, ..., Y_k$, a constant $c$ exists such that $$E\left[\max_{i \leq k} Y_i\right] \leq c \max_i |Y_i|_{\text{subgaussian}} \sqrt{\log k}$$

Lemma 6.19 (from Probability in High Dimension): For $(\epsilon^2)$-subgaussian random variables $Y_1, ..., Y_k$ and any $t > 0$, $$P\left(\max_{1 \leq i \leq k} Y_i \geq t \right) \leq 2k\exp\left(-\frac{t^2}{2\epsilon^2}\right)$$

Consider $Z_1, ..., Z_n$ as independent standard normal random variables and $X_k$ as binary vectors of length $n$ with $k$ ones, each with unit Euclidean norm. For any $X \in X_k$, the variable $Z^T X$ is Gaussian with zero mean, implying $E[Z^T X] = 0$. The distribution of $Z^T X$ remains Gaussian due to the properties of Gaussian distributions, where the linear combination of Gaussian variables is also Gaussian. Given that each component of $Z$ is standard normal and $X$ has a unit norm, the variance of $Z^T X$ is 1, making it a standard normal variable.

To apply the subgaussian norm definition, $|Y|_{\psi_2} = \inf \{ t > 0 : E[\exp(Y^2 / t^2)] \leq 2 \}$, we note that for standard Gaussian variables, this norm is a constant factor. Specifically, for a standard normal variable, the subgaussian norm can be directly related to its variance, leading to the identification of $\sigma^2 = 1$ for $Z^T X$. This quantifies the tail behavior, with its value being 1 reflecting the standard deviation of the Gaussian distribution.

Using Lemma 6.4, the expectation of the maximum deviation of $Z^T X$ from zero, for any $X$ in the set $X_k$, is bounded as follows: $$E\left[\max_{X \in X_k} \left|Z^T X\right|\right] \leq c \sigma \sqrt{\log k}$$ where $c$ is a constant for zero-mean subgaussian random variables, as established in Lemma 6.4, and $\sigma = 1$ in our case. This equation provides an upper limit on the expected maximum deviation, using the logarithmic relationship with $k$ to illustrate how the expected maximum grows as the number of vectors in $X_k$ increases.

Using Lemma 6.19, we derive the tail probability bound for the maximum deviation of $Z^T X$ exceeding a threshold $t$: $$P\left(\max_{X \in X_k} \left|Z^T X\right| \geq t \right) \leq 2k\exp(-t^2/(2\sigma^2))$$ Here, $\sigma^2 = 1$ represents the squared subgaussian norm of $Z^T X$, and highlights the rapid decrease in the probability of observing extreme deviations as $t$ increases.