# Rejection sampling A method for sampling from distribution $g(x)$ but the sampling will be according to a different distribution $f(x)$. Here is an algorithm from[^2] for sampling Gaussian distribution from uniform distribution: first you sample the outcome x uniformly , then you sample a probability r. check if r is in the CDF i.e., if r< real probability of x. If yes return x otherwise repeat. ![[Pasted image 20250829142459.png|415]] ## Lazy Rejection Sampling The above can be optimized[^3] by using two floating number precisions. As most of the values are decided by the MSB - we can check if the sample is in the small precision delta around the probability. if it is smaller and not in the delta then return the sample otherwise extend the sample probability that is now in low precision to be in higher precision and check if it is below the probability in high precision as before. nice trick. see code below: ![[Pasted image 20250829150031.png|427]] ## Distribution in distribution we first sample $x$ from $g(x)$, then we accept with probability $f(x)/(M\cdot g(x))$ where $M$ is real. If it is not accepted then we repeat the process. It can be shown that if $f(x)\le M\cdot g(x)$ for all $x$ then the rejection sampling produce exactly the distribution of $f(x)$. The expected number of repetition before acceptance is $M$ so it is crucial to have small $M$. Another way to view this method, is by sampling uniformly a point $(x_i,y_i)$ under the graph of $M\cdot g(x)$ and accept only if $y_i\le f(x_i)$ A more accurate way to compute this: 1) generate a sample $x$ from g 2) generate a sample u from the uniform distribution $Uniform(0, M\cdot g(x))$ 3) accept a sample if $u\le f(x)$ A proof for this algorithm exist in this [blog](https://medium.com/@msuhail153/rejection-sampling-6c4510da24f8) . The following is from [^1] ![[Pasted image 20241213142440.png]] ![[Pasted image 20241213142450.png|528]] Reference: - [[@Lattice Signatures and Bimodal Gaussians]], section 1.2 - [youtube video](https://www.youtube.com/watch?v=pJZNQBOB_JQ&ab_channel=MeerkatStatistics) - [[Conditional Probability]] Tag: #tech ## Created 2023-10-03 16:01 [^1]: [https://link.springer.com/content/pdf/10.1007/978-3-319-72634-2_3.pdf?pdf=inline%20link] [^2]: GAUSSIAN SAMPLING IN LATTICE BASED CRYPTOGRAPHY, J ́anos Foll ́ath [^3]: Ducas, Léo, and Phong Q. Nguyen. "Faster Gaussian lattice sampling using lazy floating-point arithmetic."