Rejection-sampling question, stuck in math Wish to generate uniform-random points in d-dimensional unit ball $B = \{ x \in \mathbb{R}^d : \|x\| \leq 1$}
One rejection-sampling approach is to pick a point $X$ uniformly randomly $\in [-1,1]^d$ by choosing each coordinate $X_i \in [-1,1]$ independently and if $\|X\| \leq 1$: output $X$ o.w. repeat.
We want to find in expectation, how many points should be picked in $[-1,1]^d$ before outputting a point in $B$?
The answer is $\frac{1}{P(x\in B)}$. I don't see how the expectation is equal to this value mathematically. Can someone please solve it mathematically?
 A: Each time we pick a point in $[-1,1]^d$ is one Bernoulli trial where the success criterion is that the point is in $B.$
The chance of success is $p = \mathbb P(x\in B).$
You will do some number $Y$ trials up to and including the first trial that is a success, then you will output the point found on the $Y$th trial. The number $Y$ is a random variable with an exponential distribution and mean $1/p.$
The exponential distribution is well-known, as are its mean and its relationship to repeated Bernoulli trials. You should be able to find these things explained in most decent probability textbooks, for example here.

Quickly summarizing: on each attempt you have probability $p$ to pick a point $x\in B,$ probability $1-p$ to pick a point you can't use.
The probability that it takes exactly $n$ trials to pick a suitable $x$ is the probability that you fail exactly $n-1$ times in a row and then succeed,
$$ \mathbb P(Y=n) = (1-p)^{n-1} p. $$
We get the expected value in the usual way for a variable $Y$ that can take on values $1, 2, 3, \ldots$:
$$ \mathbb E(Y) = \sum_{n=1}^\infty n \mathbb P(Y=n). $$
After working out the series, we find $\mathbb E(Y) = 1/p.$
A more intuitive way to visualize this result is that we have on average $p$ successes per attempt, or one success for every $1/p$ attempts, that is, on average $1/p$ attempts per success.
Somehow I thought I'd be able to just link to another answer with all of this but did not have good luck.
