# Discrete sampling from uniform sampling with Knuth-Yao algorithm The main idea is to generate a binary tree with leaves containing the possible outcome of the distribution. A leaf is associated with one outcome. An outcome will generally appear in multiple leaves. The total sum of path's lengths associated with specific outcome is proportional to the outcome probability in the distribution. Sampling is done by generating a uniform random walk along the tree and output the outcome associated with the leaf at the end of the walk. The tree is constructed by creating a list of all probabilities of the distribution in binary representation. For example: ``` P(A) = 0.1000... P(B) = 0.0100... P(C) = 0.0100... ``` Then, arrange it in a matrix: ``` bit 1 bit 2 bit 3 ... A 1 0 0 B 0 1 0 C 0 1 0 ``` start with a root node, scan the j-th column and if there is "1" add the outcome to the j-th level otherwise add "internal" node. ``` root / \ A * / \ B C ``` This induce the required structure above because reaching leaf in the j-th level has the probability $1/2^j$ . The probability of reaching a specific outcome leaf is the sum of the probability to reach every j-th levels it has "1" in it's probability binary representation. This sum is exactly the binary representation of the probability of that outcome. The size of the tree is approximately $O(m\cdot n)$ where $m$ is the number of outcomes and $n$ the bit precision of the probabilities fractions. An alternative discrete sampling can be done using an array that contains each outcome multiple times so each outcome will appear as it ration (probability) from the number of all outcomes. More specific, init array with $m\cdot 2^n$ cells filled with $m\cdot P(x_i)$ copies of the outcome $x_i$ where $P(x_i)$ is the probability of outcome $x_i$. To sample, you generate a random index in the array range and output the cell value. This solution is not practical e.g., for $m=32, n=32$. A disadvantage of this algorithm is that the sampling is not constant-time and so vulnerable to timing-side-channel-attacks.[^1] Reference: I could not find a link to the original Knuth and Yao 1976 paper. ## Created 2025-08-15 14:09 [^1]: https://www.esat.kuleuven.be/cosic/blog/constant-time-discrete-gaussian-sampling-for-lattice-based-cryptography/