Markov's inequality states that
Pr(X >= t*E(X)) <= 1/t. This is great for asking "What is the probability that we get more than t times our expected value". However, if rather than more, we want to ask what is the probability that we get LESS than our expected value, how is this handled?
Say our expected value is n/4. If we wanted to ask what the probability is that we'd get less than n/6, intuitively I'd say
"It is 1 - the probability that we get greater than or equal to n/6"
, but that doesn't seem to be working out for me. How is this accomplished with Markov's inequality?