How to generate random points in $\ell_p$ balls? 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.
 A: 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$.
A: 
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$.
