Lebesgue measure and the curse of dimensionality (application)

69 Views Asked by At

Apologies for the cryptic, Harry Potter-esque title; I really did not know how to name this! (Very much open to suggestions of more informative titles.)

Fix $\varepsilon>0$ and $a>0$. For each $n\in\{2,3,...\}$, define $$ S_n := \left\{(x_1,...,x_n)\in [0,a]^n : \frac{e^{x_i}}{\sum_{j=1}^n e^{x_j}}< \varepsilon \ \forall i\in\{1,...,n\}\right\} $$ I'm having difficulty calculating the Lebesgue measure (denoted by $\lambda(\cdot)$) of $S_n$. Is this possible? If so, advice on how to do this would be very appreciated.

If not, would there be another way for me to analytically characterize $\text{limit}_{n\to\infty} \frac{\lambda(S_n)}{a^n}$? (I.e. how "large" $S_n$ is relative to $[0,a]^n$ as $n$ becomes large?.)

Note: Assume $\varepsilon$ is such that $S_n$ is non-empty for at least some $n\in\{2,3,...\}.$

1

There are 1 best solutions below

0
On

Let $\mathbb P=a^{-n} \lambda$ restricted to $Q=[0,a]^n$ be the uniform distribution on $Q$. Write $\mu:=\frac1a\int_0^a e^x \,dx=\frac1a(e^a-1)$. By the weak law of large numbers, $$\mathbb P(S_n^c) \le \mathbb P\bigl\{x\in Q : \sum_{j=1}^n e^{x_j} \le e^a/\varepsilon \bigr\} \le \mathbb P\bigl\{x\in Q : \sum_{j=1}^n e^{x_j} \le n\mu/2 \bigr\} \to 0 \tag{*}$$ as $n \to \infty$. Standard concentration inequalities, e.g. Hoeffding's inequality, imply that the RHS of $(*)$ tends to zero exponentially fast as $n \to \infty$. In fact, by comparison to a sum of uniform variables, it can be shown that the middle term in $(*)$ tends to zero super-exponentially fast. See, e.g., [1] or [2].

[1] Expected stopping time

[2] https://en.wikipedia.org/wiki/Irwin%E2%80%93Hall_distribution