I am a bit confused with approximating the $L^{\infty}$ norm of a random variable.
Suppose that we are interested in estimating the $L^p$ norm of $X$ where $p < \infty$. In this case, we just generate samples $X_i$ of $X$ distributed according to the measure $\mu$ and compute $\frac{1}{N}\sum_{i=1}^N |X_i|^p$.
For $L^{\infty}$ norm, the idea would be to generate samples $X_i$ and compute $\text{max} |X_i|$. The question now is that: should the samples $X_i$ be generated uniformly or according to the measure $\mu$?
I have checked a few probability books and the definition of $L^{\infty}$ is left out. However, in these notes (link here) for example, it appears that the measure does not play much of a role in the definition.
Thoughts?
The $L^\infty$ norm of a function $X$ on a probability space $(\Omega,\mathcal{F},\mu)$ does depend on the measure $\mu$, but only in a weak way: it only depends on the null sets of $\mu$. More precisely, the definition is $$\|X\|_\infty=\sup\{r\in\mathbb{R}:\mu(\{\omega:|X(\omega)|>r\})>0\},$$ where the only aspect of $\mu$ we are using is whether or not $\mu(\{\omega:|X(\omega)|>r\})=0$. So to estimate $\|X\|_\infty$ by sampling points, it does not matter what measure you use to sample them as long as that measure has the same null sets as $\mu$.
To make things more precise, you can say that if you generate a sequence of independent samples $X_i$ of $X$ with distribution $\mu$, then $M_N=\max_{i\leq N} |X_i|$ will almost surely converge to $\|X\|_\infty$ as $N\to\infty$ (since for any $r<\|X\|_\infty$, almost surely there will eventually be an $X_i$ such that $|X_i|>r$). But since the value of $\|X\|_\infty$ depends only on the null sets of $\mu$, the same thing will be true if the $X_i$ are sampled using any other distribution with the same null sets.