0
$\begingroup$

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$

$\endgroup$
3
  • $\begingroup$ 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). $\endgroup$
    – andysark
    Sep 11 at 17:40
  • 1
    $\begingroup$ 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. $\endgroup$
    – Steven
    Sep 11 at 17:44
  • $\begingroup$ 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. $\endgroup$
    – andysark
    Sep 11 at 18:33
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.