Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
There's an obvious map from the ell_2 ball to the ell_1 ball. Does that not work for you? What kind of distribution do you want? –  Qiaochu Yuan Dec 17 '09 at 17:27
    
I'm interested in the uniform distribution. If by "obvious map" you mean rescaling, then that wouldn't work. –  Mitch Dec 17 '09 at 17:38
add comment

2 Answers 2

up vote 18 down vote accepted

For arbitrary p, this paper 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$.

The paper also shows how to generate certain other distributions on the $\ell_p^n$ ball by modifying the distribution of $Y$.

share|improve this answer
3  
This is the natural answer to the problem. It directly generalizes the Gaussian point method for $p=2$. –  Greg Kuperberg Dec 17 '09 at 19:40
add comment

I'll assume that you're looking for a uniformly chosen random point in the ball, since you didn't state otherwise. For p=1, you're asking for a uniform random point in the cross polytope in n dimensions. That is the set

$ C_n = \{ x_1, x_2, \ldots, x_n \in \mathbb{R} : |x_1| + \cdots + |x_n| \le 1 \}. $

By symmetry, it suffices to pick a random point $(X_1, \ldots, X_n)$ from the simplex

$ S_n = \{ x_1, x_2, \ldots, x_n \in \mathbb{R}^+ : x_1 + \cdots + x_n \le 1 \}$

and then flip $n$ independent coins to attach signs to the $x_i$.

From Devroye's book Non-uniform random variable generation (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:

  • let $U_1, \ldots, U_n$ be iid uniform(0,1) random variables
  • 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$
  • let $X_i = V_i - V_{i-1}$

So do this to pick the absolute values of the coordinates of your points; attach signs chosen uniformly at random, and you're done.

This of course relies on the special structure of balls in $\ell^1$; I don't know how to generalize it to arbitrary $p$.

share|improve this answer
    
C_n and S_N are of course sets; I can't figure out how to get the braces to show up. –  Michael Lugo Dec 17 '09 at 17:37
    
Thanks for the reference. For $p=1$ this was what I thought, but I didn't have a reference. I'm still interested in p>2 though. –  Mitch Dec 17 '09 at 17:45
    
Fixed the braces. If you're curious how I did this, I'll put up a note on tea.mathoverflow.net –  David Speyer Dec 17 '09 at 17:48
    
David, thanks for fixing the notation. Mitch, I'd love an answer for other p as well. It seems like a problem someone should have considered but quick searching isn't finding any answers other than the obvious one of picking a random point in the unit cube and throwing it out if it doesn't work, which for large n gets very bad. –  Michael Lugo Dec 17 '09 at 17:50
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.