Welcome to Randal Douc's wiki

A collaborative site on maths but not only!

User Tools

Site Tools


world:ratio-of-uniform

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revision Previous revision
Next revision
Previous revision
Last revision Both sides next revision
world:ratio-of-uniform [2023/04/05 17:59]
rdouc
world:ratio-of-uniform [2023/04/20 08:57]
rdouc [The idea]
Line 1: Line 1:
 {{page>:​defs}} {{page>:​defs}}
  
 +====== The idea ======
  
-If $ (X,Y) \sim \unif\set{(x,​y)}{0\leq x\leq M f(y)}$, then $Y \sim f$. 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$. ​+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$.  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)]}$+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]] +  * [[https://​dl.acm.org/​doi/​pdf/​10.1145/​355744.355750|ratio-of-uniform ​method]] 
-  * {{ :​mynotes:​bf01889987.pdf | Generalisation}}+  * {{ :​mynotes:​bf01889987.pdf | Generalisation ​of the ratio-of-uniform method}}
world/ratio-of-uniform.txt · Last modified: 2023/04/20 08:57 by rdouc