16 Jul 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
Video:
Poster:
