Welcome to Randal Douc's wiki

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.

{{page>:defs}}

====== The ratio of uniform method ======

The rejection algorithm is based on the following property: 
  * $ (X,Y) \sim \unif\set{(x,y)}{0\leq x\leq M f(y)}$ if and only if $Y \sim f$ and $X|_{Y=y} \sim \unif[0,Mf(y)]$. 

The idea of the ratio-of-uniform method is based on the following property: if $ (U,V) \sim \unif\set{(u,v)}{0\leq u\leq  \sqrt{M f(v/u)}}$, then $V/U \sim f$. This can be shown from the change of variable $x=u$, $y=v/u$, i.e. $u=x$, $v=xy$. 

A simple generalisation of this result is: if $ (U,V) \sim \unif\set{(u,v)}{0\leq u\leq  G^{-1}\lr{M f\lr{\frac { v} {g(u)}}}}$, then $V/g(U) \sim f$ where $g: \rset^+ \to \rset^+_*$ and $G(x)=\int_0^x g(u) \rmd u$. 

As far as I can see, these methods can only be interesting if $V=Y g(X)$ or $U=X$ are easy to simulate when $Y \sim f$ and $X|_Y \sim \unif\lrcb{[0,f(Y)]}$. This is very linked to rejection algorithm...

  * [[https://dl.acm.org/doi/pdf/10.1145/355744.355750|ratio-of-uniform method]]
  * {{ :mynotes:bf01889987.pdf | Generalisation of the ratio-of-uniform method}}

Welcome to Randal Douc's wiki

User Tools

Site Tools

Page Tools