1

I am trying to establish the behavior of the cdf as the number of trials tend to infinity. With a certain probability of success and K number of successes, if we increase the number of trials to infinity, what would happen to the cdf plot. I have tried this in Matlab to observe the behavior. If I fix the number of successes and the probability of success, and start increasing the number of trials, the cdf plot shifts to the right side. My intuition is that if I increase the number of trials, the CDF (P{X>K} would increase. If the number of trials go to infinity, then I can conclude that P{X>K} would be 1 for any K. I want to prove this from the formula of binomial distribution. In the figure below, I am increasing M towards infinity and I want guidance to prove that as M goes to infinity, P{X>K} for all K would be 1.

enter image description here

Waqas
  • 83

1 Answers1

1

In Hoeffding inequality, if we take $\epsilon = p - k/M$ (equivalently, $(p-\epsilon)M=k$) and assume $k<Mp$ so that $\epsilon>0$, we get:

$$ P(X\leq k)\leq \exp (-2(p - k/M)^2M). $$

As the right hand expression goes to $0$ when $M$ goes to $\infty$ (and $p$ and $k$ are fixed), this inequality should justify your observations.

ir7
  • 6,249