### Inversion with Discrete Variables Suppose $X$ is discrete with pmf $p(x)$ and cdf $F(x)$. A natural way of sampling $X$ is by dividing $[0,1]$ into segments equal to $p(x_{1}),p(x_{2}),\dots$ - For example, a $\mathrm{Poisson}(5)$ distribution can be represented as the following, where the intervals represents $p(0),p(1),\dots$. ![[InversionSampling.png#invert|center|w60]] Having those segments, we then sample a $U[0,1]$ point, and if it falls in the segment representing $p(x_{i})$, return $X=x_{i}$. To formulate the idea into an algorithm, let the cdf of $X$ be $F(x)$, and define its "inverse" as $F^{(-1)}:u \mapsto \min_{x}: F(x-1)<u \le F(x) $That is, increasing $x$ (the vertical red line), and stopping as soon as $F(x)$ exceeds $u$ (the horizontal red line). This function essentially finds which segment $U$ falls into. ![[DiscreteInversion.png#invert|center]] > [!algorithm] Inversion Sampling (Discrete Distributions) > (1) invert $F$ to get $F^{(-1)}$. > > (2) sample $U \sim[0,1]$. > > (3) return $X=F^{(-1)}(U) \sim p,F$. ### General Inversion Sampling The algorithm in the previous section is a special case of **inversion sampling** -- finding some inverse of the cdf, then plugging a $U[0,1]$ variable into it. This method works for invertible cdf $F$: with $U \sim [0,1]$, setting $F^{-1}(U)\equiv X$ gives $X \sim F$, a sample from the distribution. > [!proof]- > For any sample $U=u$, $\mathbb{P}[X \le x]=\mathbb{P}[F^{-1}(U) \le x]=\mathbb{P}[U \le F(x)]=F(x)$Hence $X \sim F$. For more general distributions, $F$ is not be invertible: it might be stationary in some places, or even be a step function (when $X$ is discrete). > [!definition|*] Generalized Inverse of CDFs > The **generalized inverse** of $F$ is $F^{(-1)}:[0,1] \to \mathbb{R}$: $F^{(-1)}(u)=\inf\{ x:F(x) \ge u \}$which is well-defined even for a discrete and/or non-strictly increasing cdf. - The "inverse" defined in the previous section is just the discrete version of the generalized inverse. With the generalized inverse, $F^{(-1)}(U) \equiv X$ still follows $F$. > [!proof]- > Note that $\{ x: F(x)\ge u \}=[F^{(-1)}(u),\infty)$ by monotonicity of $F$. Then $\begin{align*} \mathbb{P}[X \le x]=\mathbb{P}[F^{(-1)}(U) \le x]&= \mathbb{P}[x \in \{ x:F(x)\ge U \}]\\ &= \mathbb{P}[U \le F(x)]\\ &= F(x) \end{align*}$Hence $X \sim F$. > [!algorithm] Inversion Sampling (General Distributions) > - (1) Invert $F$ to get $F^{-1}$ (or $F^{(-1)}$). > - (2) Sample $U \sim[0,1]$. > - (3) Return $X=F^{-1}(U) \sim F$.