geometry - How to generate random points in ell_p balls?

---

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$.