How to generate random points in ell_p balls? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-26T06:02:08Z http://mathoverflow.net/feeds/question/9185 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/9185/how-to-generate-random-points-in-ell-p-balls How to generate random points in ell_p balls? Mitch 2009-12-17T17:02:32Z 2009-12-17T18:40:30Z <p>How do I feasibly generate a random sample from an n-dimensional ell_p ball? Specifically, I'm interested in p=1 and large n. I'm looking for descriptions analogous to the statement for p=2: Take n standard gaussian random variables and normalize.</p> http://mathoverflow.net/questions/9185/how-to-generate-random-points-in-ell-p-balls/9188#9188 Answer by Michael Lugo for How to generate random points in ell_p balls? Michael Lugo 2009-12-17T17:35:27Z 2009-12-17T17:45:24Z <p><hr /></p> <p>I'll assume that you're looking for a <i>uniformly chosen</i> random point in the ball, since you didn't state otherwise. For p=1, you're asking for a uniform random point in the <a href="http://en.wikipedia.org/wiki/Cross-polytope" rel="nofollow">cross polytope</a> in n dimensions. That is the set</p> <p>$C_n = \{ x_1, x_2, \ldots, x_n \in \mathbb{R} : |x_1| + \cdots + |x_n| \le 1 \}.$</p> <p>By symmetry, it suffices to pick a random point $(X_1, \ldots, X_n)$ from the simplex</p> <p>$S_n = \{ x_1, x_2, \ldots, x_n \in \mathbb{R}^+ : x_1 + \cdots + x_n \le 1 \}$</p> <p>and then flip $n$ independent coins to attach signs to the $x_i$.</p> <p>From Devroye's book <a href="http://cg.scs.carleton.ca/~luc/rnbookindex.html" rel="nofollow">Non-uniform random variable generation</a> (freely available on the web at the link above, see p. 207 near the beginning of Chapter 5), we can pick a point in the simplex uniformly at random by the following procedure:</p> <ul> <li>let $U_1, \ldots, U_n$ be iid uniform(0,1) random variables</li> <li>let $V_1, \ldots, V_n$ be the $U_i$ reordered so that $V_1 \le V_2 \le \cdots \le V_n$ (the "order statistics"); let $V_0 = 0, V_{n+1} = 1$</li> <li>let $X_i = V_i - V_{i-1}$ </ul> <p>So do this to pick the absolute values of the coordinates of your points; attach signs chosen uniformly at random, and you're done.</p> <p>This of course relies on the special structure of balls in $\ell^1$; I don't know how to generalize it to arbitrary $p$.</p> http://mathoverflow.net/questions/9185/how-to-generate-random-points-in-ell-p-balls/9192#9192 Answer by Mark Meckes for How to generate random points in ell_p balls? Mark Meckes 2009-12-17T18:23:06Z 2009-12-17T18:40:30Z <p>For arbitrary p, <a href="http://arxiv.org/abs/math/0503650" rel="nofollow">this paper</a> does exactly what you want. Specifically, pick $X_1,\ldots,X_n$ independently with density proportional to $\exp(-|x|^p)$, and $Y$ an independent exponential random variable with mean 1. Then the random vector $$\frac{(X_1,\ldots,X_n)}{(Y+\sum |X_i|^p)^{1/p}}$$ is uniformly distributed in the unit ball of $\ell_p^n$.</p> <p>The paper also shows how to generate certain other distributions on the $\ell_p^n$ ball by modifying the distribution of $Y$.</p>