<aside> 📌

By Dr. Nir Regev

</aside>

<aside> 📌

Sign up to Circuit of Knowledge blog for unlimited tutorials and content

</aside>

Video of this Tutorial

https://youtu.be/K3WkLUTL_I8?si=lCV65thcO_B6Qf7d

Introduction

In this tutorial, we will explore how to generate random variables from the distribution of the maximum of a large number of uniformly distributed random variables using the Inverse Transform Sampling (ITS) Method. We will focus on the case where we have 1000 uniformly distributed random variables and want to draw from the distribution of their maximum without actually generating all 1000 values and taking the maximum.

Mathematical Background

Let's start with some mathematical background. Suppose we have $n$ independent and identically distributed (i.i.d.) uniform random variables $U_1, U_2, \ldots, U_n$, each following a uniform distribution over the interval $[0, 1]$. We are interested in the distribution of the maximum of these random variables, denoted as $M_n = \max\{U_1, U_2, \ldots, U_n\}$.

The cumulative distribution function (CDF) of $M_n$ can be derived as follows:

$$ ⁍ $$

Since the random variables are independent, we can multiply their individual probabilities:

/mat$F_{M_n}(x) = P(U_1 \leq x) \cdot P(U_2 \leq x) \cdot \ldots \cdot P(U_n \leq x)$, and due to the i.i.d property we can write

$F_{M_n}(x) = [P( U \leq x)]^n,$ where $U$ denotes any $U_i$.

For a uniform distribution over $[0, 1]$, the CDF is given by $F_U(x) = x$ for $0 \leq x \leq 1$. Therefore,

$$ ⁍ $$

Inverse Transform Sampling Method

The ITS method is a technique for generating random variables from a given distribution by inverting its CDF. If we have a random variable $X$ with CDF $F_X(x)$, we can generate a random variable $X$ by following these steps:

1. Generate a random number $U$ from a uniform distribution over $[0, 1]$.
2. Compute $X = F_X^{-1}(U)$, where $F_X^{-1}$ is the inverse CDF of $X$.
3. X is now distributed with $F_X(x)$ as its CDF.