Sampling from a discrete probability distribution using a discrete uniform probability distribution

Define the simulation of a fair m-sided die with a fair n-sided die as a process of obtaining a random integer from interval [1,m] using a fair n-sided die. Then one can simulate a 4-sided die with a 6-sided die as follows: Roll the 6-sided die. If the outcome is between 1 and 4 inclusive, select it as the result of the simulation. Otherwise roll the 6-sided die again. In a more general case the simulated die doesn’t have to be a fair one. In this work, I prove that a certain greedy algorithm minimizes the expected value of the required samples. It turns out, perhaps slightly surprisingly, that the greedy algorithm not only minimizes the expected value of the samples but is at least as good as any other algorithm in a certain sense explained in our main theorem.

Category: MATHEMATICS Country: FINLAND Year: 2020


Valtteri Aurela