Return to Answer

As Nate Eldredge pointed out in his comment, your two-step procedure will not in general simulate (a random element of $\mathcal M$ with) the uniform density $f=1/|B_x|$ on $B_x:=\{y\in\mathcal M\colon d_{\mathcal M}(y,x)\le1\}$, where $|B_x|$ is the volume of $B_x$. However, this "two-step" density, say $h$, can be used to simulate $f$, using the so-called rejection sampling method, as follows.

Suppose that $c\in[1,\infty)$ is such that $$f(y)\le c\,h(y)\tag{1}$$ for all $y\in B_x$. Let $Y$ be a random element of $B_x$ with density $h$, and let $U$ be a random variable uniformly distributed in the interval $[0,1]$ and independent of $Y$. Then the random pair $(Y,Uc\,h(Y))$ will be uniformly distributed on the subgraph $\{(y,t)\colon y\in B_x,0\le t\le c\,h(y)\}$ of the function $c\,h$ on $B_x$.

Now simulate a value $y$ of $Y$ using your two-step procedure, and then independently simulate a value $u$ of $U$.

Next, if $u\,c\,h(y)>f(y)$, discard the simulated value $y$ of $Y$ (as well as the simulated value $u$ of $U$). Otherwise, i.e. if $u\,c\,h(y)\le f(y)$, accept the simulated value $y$ of $Y$ as the simulated value $x$ of a random element $X$ of $B_x$. Then the random pair $(X,Uc\,h(X))$ will be uniformly distributed on the subgraph $\{(y,t)\colon y\in B_x,0\le t\le f(y)\}$ of the function $f$ on $B_x$ and hence $X$ with have the desired density $f$.

The expected "waste" fraction due to the rejection of some realizations of $Y$ will then be $\int_{B_x}(h(y)-f(y)/c)\,dy=1-1/c$. So, if $h$ is not far from $f$, then we can take the bounding factor $c$ in (1) to be somewhat close to $1$, and then the expected "waste" fraction $1-1/c$ will be somewhat close to $0$.

As Nate Eldredge pointed out in his comment, your two-step procedure will not in general simulate (a random element of $\mathcal M$ with) the uniform density $f=1/|B_x|$ on $B_x:=\{y\in\mathcal M\colon d_{\mathcal M}(y,x)\le1\}$, where $|B_x|$ is the volume of $B_x$. However, this "two-step" density, say $h$, can be used to simulate $f$, using the so-called rejection sampling method, as follows.

Suppose that $c\in[1,\infty)$ is such that $$f(y)\le c\,h(y)\tag{1}$$ for all $y\in B_x$. Let $Y$ be a random element of $B_x$ with density $h$, and let $U$ be a random variable uniformly distributed in the interval $[0,1]$ and independent of $Y$. Then the random pair $(Y,Uc\,h(Y))$ will be uniformly distributed on the subgraph $\{(y,t)\colon y\in B_x,0\le t\le c\,h(y)\}$ of the function $c\,h$ on $B_x$.

Now simulate a value $y$ of $Y$ using your two-step procedure, and then independently simulate a value $u$ of $U$.

Next, if $u\,c\,h(y)>f(y)$, discard the simulated value $y$ of $Y$ (as well as the simulated value $u$ of $U$). Otherwise, i.e. if $u\,c\,h(y)\le f(y)$, accept the simulated value $y$ of $Y$ as the simulated value $x$ of a random element $X$ of $B_x$. Then the random pair $(X,Uc\,h(X))$ will be uniformly distributed on the subgraph $\{(y,t)\colon y\in B_x,0\le t\le f(y)\}$ of the function $f$ on $B_x$ and hence $X$ with have the desired density $f$.

The expected "waste" fraction due to the rejection of some realizations of $Y$ will then be $\int_{B_x}(h(y)-f(y)/c)\,dy=1-1/c$. So, if $h$ is not far from $f$, then we can take the bounding factor $c$ in (1) to be somewhat close to $1$, and then the expected "waste" fraction $1-1/c$ will be somewhat close to $0$.

As Nate Eldredge pointed out in his comment, your two-step procedure will not in general simulate (a random element of $\mathcal M$ with) the uniform density $f=1/|B_x|$ on $B_x:=\{y\in\mathcal M\colon d_{\mathcal M}(y,x)\le1\}$, where $|B_x|$ is the volume of $B_x$. However, this "two-step" density, say $h$, can be used to simulate $f$, using the so-called rejection sampling method, as follows.

Suppose that $c\in[1,\infty)$ is such that $$f(y)\le ch(y)\tag{1}$$ for all $y\in B_x$. Let $Y$ be a random element of $B_x$ with density $h$, and let $U$ be a random variable uniformly distributed in the interval $[0,1]$ and independent of $Y$. Then the random pair $(Y,Uch(Y))$ will be uniformly distributed on the subgraph $\{(y,t)\colon y\in B_x,0\le t\le ch(y)\}$ of the function $ch$ on $B_x$.

Now simulate a value $y$ of $Y$ using your two-step procedure, and then independently simulate a value $u$ of $U$.

Next, if $cuh(y)>f(y)$, discard the simulated value $y$ of $Y$ (as well as the simulated value $u$ of $U$). Otherwise, i.e. if $cuh(y)\le f(y)$, accept the simulated value $y$ of $Y$ as the simulated value $x$ of a random element $X$ of $B_x$. Then the random pair $(X,Uch(X))$ will be uniformly distributed on the subgraph $\{(y,t)\colon y\in B_x,0\le t\le f(y)\}$ of the function $f$ on $B_x$ and hence $X$ with have the desired density $f$.

The expected "waste" fraction due to the rejection of some realizations of $Y$ will then be $\int_{B_x}(h(y)-f(y)/c)\,dy=1-1/c$. So, if $h$ is not far from $f$, then we can take the bounding factor $c$ in (1) to be somewhat close to $1$, and then the expected "waste" fraction $1-1/c$ will be somewhat close to $0$.

As Nate Eldredge pointed out in his comment, your two-step procedure will not in general simulate (a random element of $\mathcal M$ with) the uniform density $f=1/|B_x|$ on $B_x:=\{y\in\mathcal M\colon d_{\mathcal M}(y,x)\le1\}$, where $|B_x|$ is the volume of $B_x$. However, this "two-step" density, say $h$, can be used to simulate $f$, using the so-called rejection sampling method, as follows.

Suppose that $c\in[1,\infty)$ is such that $$f(y)\le c\,h(y)\tag{1}$$ for all $y\in B_x$. Let $Y$ be a random element of $B_x$ with density $h$, and let $U$ be a random variable uniformly distributed in the interval $[0,1]$ and independent of $Y$. Then the random pair $(Y,Uc\,h(Y))$ will be uniformly distributed on the subgraph $\{(y,t)\colon y\in B_x,0\le t\le c\,h(y)\}$ of the function $c\,h$ on $B_x$.

Now simulate a value $y$ of $Y$ using your two-step procedure, and then independently simulate a value $u$ of $U$.

Next, if $u\,c\,h(y)>f(y)$, discard the simulated value $y$ of $Y$ (as well as the simulated value $u$ of $U$). Otherwise, i.e. if $u\,c\,h(y)\le f(y)$, accept the simulated value $y$ of $Y$ as the simulated value $x$ of a random element $X$ of $B_x$. Then the random pair $(X,Uc\,h(X))$ will be uniformly distributed on the subgraph $\{(y,t)\colon y\in B_x,0\le t\le f(y)\}$ of the function $f$ on $B_x$ and hence $X$ with have the desired density $f$.

The expected "waste" fraction due to the rejection of some realizations of $Y$ will then be $\int_{B_x}(h(y)-f(y)/c)\,dy=1-1/c$. So, if $h$ is not far from $f$, then we can take the bounding factor $c$ in (1) to be somewhat close to $1$, and then the expected "waste" fraction $1-1/c$ will be somewhat close to $0$.

As Nate Eldredge pointed out in his comment, your two-step procedure will not in general simulate (a random element of $\mathcal M$ with) the uniform density $f=1/|B_x|$ on $B_x:=\{y\in\mathcal M\colon d_{\mathcal M}(y,x)\le1\}$, where $|B_x|$ is the volume of $B_x$. However, this density, say $h$, can be used to simulate $f$, using the so-called rejection sampling method, as follows.

Suppose that $c\in[1,\infty)$ is such that $$f(y)\le ch(y)\tag{1}$$ for all $y\in B_x$. Let $Y$ be a random element of $B_x$ with density $h$, and let $U$ be a random variable uniformly distributed in the interval $[0,1]$ and independent of $Y$. Then the random pair $(Y,Uch(Y))$ will be uniformly distributed on the subgraph $\{(y,t)\colon y\in B_x,0\le t\le ch(y)\}$ of the function $ch$ on $B_x$.

Now simulate a value $y$ of $Y$ using your two-step procedure, and then independently simulate a value $u$ of $U$.

Next, if $cuh(y)>f(y)$, discard the simulated value $y$ of $Y$ (as well as the simulated value $u$ of $U$). Otherwise, i.e. if $cuh(y)\le f(y)$, accept the simulated value $y$ of $Y$ as the simulated value $x$ of a random element $X$ of $B_x$. Then the random pair $(X,Uch(X))$ is uniformly distributed on the subgraph $\{(y,t)\colon y\in B_x,0\le t\le f(y)\}$ of the function $f$ on $B_x$ and hence $X$ with have the desired density $f$.

The expected "waste" fraction due to the rejection of some realizations of $Y$ will then be $\int_{B_x}(h(y)-f(y)/c)\,dy=1-1/c$. So, if $h$ is not far from $f$, then we can take the bounding factor $c$ in (1) to be somewhat close to $1$, and then the expected "waste" fraction $1-1/c$ will be somewhat close to $0$.

As Nate Eldredge pointed out in his comment, your two-step procedure will not in general simulate (a random element of $\mathcal M$ with) the uniform density $f=1/|B_x|$ on $B_x:=\{y\in\mathcal M\colon d_{\mathcal M}(y,x)\le1\}$, where $|B_x|$ is the volume of $B_x$. However, this "two-step" density, say $h$, can be used to simulate $f$, using the so-called rejection sampling method, as follows.

Suppose that $c\in[1,\infty)$ is such that $$f(y)\le ch(y)\tag{1}$$ for all $y\in B_x$. Let $Y$ be a random element of $B_x$ with density $h$, and let $U$ be a random variable uniformly distributed in the interval $[0,1]$ and independent of $Y$. Then the random pair $(Y,Uch(Y))$ will be uniformly distributed on the subgraph $\{(y,t)\colon y\in B_x,0\le t\le ch(y)\}$ of the function $ch$ on $B_x$.

Now simulate a value $y$ of $Y$ using your two-step procedure, and then independently simulate a value $u$ of $U$.

Next, if $cuh(y)>f(y)$, discard the simulated value $y$ of $Y$ (as well as the simulated value $u$ of $U$). Otherwise, i.e. if $cuh(y)\le f(y)$, accept the simulated value $y$ of $Y$ as the simulated value $x$ of a random element $X$ of $B_x$. Then the random pair $(X,Uch(X))$ will be uniformly distributed on the subgraph $\{(y,t)\colon y\in B_x,0\le t\le f(y)\}$ of the function $f$ on $B_x$ and hence $X$ with have the desired density $f$.

The expected "waste" fraction due to the rejection of some realizations of $Y$ will then be $\int_{B_x}(h(y)-f(y)/c)\,dy=1-1/c$. So, if $h$ is not far from $f$, then we can take the bounding factor $c$ in (1) to be somewhat close to $1$, and then the expected "waste" fraction $1-1/c$ will be somewhat close to $0$.