# Efficient random sampling from large discrete distribution

I have a random variable $$X$$ that can take finite values in $$\{X_1, ..., X_n\}$$ with probabilities $$\{p_1,..., p_n\}$$. Is there a computationally efficient way to sample a number from this set? My problem is that $$n$$ is very large $$2^{1000}$$. Also the distribution is quite arbitrary - not uniform or something nice.

Context: The probabilities are the path probabilities of a 2 state Markov Chain. So in time period $$n$$, there are $$2^n$$ paths and I need to sample 100 paths from this set when $$n = 1000$$

• Thanks @InuyashaYagami, I really did not know how large this number actually was. Now I am kind of hoping to work without having to store the probabilities at all. Basically, using the information that these are path probabilities of a 2 state Markov chain (I have added some context which I should have done earlier). Commented Sep 11, 2021 at 17:40
• Andysack, what prevents you from simulating the Markov chain for $1000$ steps? You can probably take some shortcuts such as sampling a geometric random variable do decide how many steps in the process are spent on the same state. Commented Sep 11, 2021 at 17:44
• Thanks for that suggestion! @Steven I guess I was so caught up in looking at the space of paths as the outcome of a random variable that it did not strike me I could just simulate it. Also even a O(n) algorithm would then need 2^1000 steps since number of elements = 2^1000. Commented Sep 11, 2021 at 18:33

## 1 Answer

If the probabilities are arbitrary I don't think you can get away with using less than $$\Omega(n)$$ space. Then there are solutions that use $$O(n)$$ space, require $$O(n)$$ preprocessing time, and can return an element selected according to the distribution in constant time.

Have a look at the Alias method.