Tag Archives: complexity

From Las Vegas to Monte Carlo with Markov’s Inequality

One of the basic results in probability theory tells us that it is unlikely a random event deviates from its expected value with high probability. Theorem 1. (Markov’s Inequality) For any non-negative real valued random variable , we have Proof. … Continue reading

Posted in Uncategorized | Tagged , , , , , , | Leave a comment