Feasible region of probabilistic constraint

Question

Let $\varepsilon \in (0,1)$ and $\xi \in \mathbb{R}^n$ with $\xi \sim \mathcal{N}(0,I_n)$ be a random vector from a multivariate normal distribution with zero mean and identity covariance matrix. In a paper I'm reading on chance-constrained optimization, the authors claim that the feasible region of the probabilistic constraint $$\{x \in \mathbb{R}^n : \text{Prob}(\xi^{\text{T}} x \leq 1) \geq 1 - \varepsilon\}$$ is a Euclidean ball centered at the origin of radius

\begin{align} \label{eqn:radius} r &= (1 + o(1))\sqrt{2\log\left(\frac{1}{\varepsilon}\right)} \tag{1}. \end{align}

as $\varepsilon \to 0$. I would like to derive the above result.

We can rewrite the probabilistic constraint as $$\left\lbrace x \in \mathbb{R}^n : \text{Prob}\left(\xi^{\text{T}} \frac{x}{\left\lVert x\right\rVert} \leq \frac{1}{\left\lVert x\right\rVert}\right) \geq 1 - \varepsilon \right\rbrace$$ to see that the feasible region of this constraint will be a sphere of certain radius (this follows from the fact that we can pick any unit vector $\frac{x}{\left\lVert x\right\rVert}$ because of the spherical symmetry of the distribution of $\xi$), but I don't know how to proceed further to derive \eqref{eqn:radius}.

Answer 1

Since the distribution is spherically symmetrical, just look at one of the axes; in which case, you are essentially trying to find the $r$ that satisfies $P(|\xi r| > 1) < \epsilon$, which is equivalent to $P(|\xi| > \frac{1}{r}) < \epsilon$.

Now, a popular bound in probability called Chernoff bound for gaussian variables (with variance 1) tells you that $P(|\xi| > t) < 2e^{-\frac{t^2}{2}}$. As such, if $2e^{-\frac{1}{2r^2}} < \epsilon$, you are in the feasible region.

Solving it by algebra, you get $r < \sqrt{\frac{2}{\log{\frac{2}{\epsilon}}}}$ (You should check to verify), and this has I think the "right" scaling with epsilon; in the bound you gave in the question, picking epsilon close to 1 seems to shrink your feasible region, whereas it should be expanding (since if epsilon could be 1, any x would be feasible).

I could be wrong though, but since you asked how such bounds are derived, this is one way to approach this problem.

Answer 2

Based on user E-A's hint, I've derived a related description of the feasible region.

Consider the following equivalent form of the chance constraint: $$\left\lbrace x \in \mathbb{R}^n : \text{Prob}\left(\xi^{\text{T}} \frac{x}{\left\lVert x\right\rVert} \leq \frac{1}{\left\lVert x\right\rVert}\right) \geq 1 - \varepsilon \right\rbrace.$$ Since the distribution of $\xi$ is spherically symmetric, we can choose $\frac{x}{\left\lVert x \right\rVert}$ to be the unit vector along the first coordinate direction, which then yields the following condition for the (maximal) radius $r$: $$\text{Prob}\left(\xi_1 \leq \frac{1}{r}\right) = 1 - \varepsilon \implies \text{Prob}\left(\xi_1 \geq \frac{1}{r}\right) = \varepsilon.$$ Since $\xi_1 \sim \mathcal{N}(0,1)$, we can simplify this to $$1 - \Phi\left( \frac{1}{r} \right) = \frac{1}{2}\left[1 - \text{erf}\left(\frac{1}{\sqrt{2}r}\right) \right] = \varepsilon \implies r = \frac{1}{\sqrt{2}\text{erf}^{-1}(1-2\varepsilon)}.$$ For $\varepsilon \ll 1$, we can use the approximation $\text{erf}^{-1}(1-2\varepsilon) \sim \sqrt{-\log\left[1-(1-2\varepsilon)^2\right]} = \sqrt{-\log\left[4\varepsilon - 4\varepsilon^2\right]}$ to get $$r \sim \frac{1}{\sqrt{-2 \log\left[4\varepsilon - 4\varepsilon^2\right]}},$$ which also agrees with the scaling argument put forth by user E-A.