Lower Bound on Binomial Distribution

[EngWiPy]

Hello all,

Is there any lower bound on the following Binomial distribution

\sum_{k=floor(N/2)+1}^N{N\choose k}\epsilon^k(1-\epsilon)^{N-k}

as N goes to infinity and where epsilon is less that or equal 10^-3?

Thanks

 

[mathman]

It looks like the expression -> 0, for \epsilon \lt \frac{1}{2}.

 

[EngWiPy]

It looks like the expression -> 0, for \epsilon \lt \frac{1}{2}.

What if N is finite?

 

[geoffrey159]

Hello all,

Is there any lower bound on the following Binomial distribution

\sum_{k=floor(N/2)+1}^N{N\choose k}\epsilon^k(1-\epsilon)^{N-k}

as N goes to infinity and where epsilon is less that or equal 10^-3?

Thanks

I believe your expression tends to 0 as $n \rightarrow \infty$, but I may be mistaking:

Since $0<\epsilon \le 0.001$, you get that $0 < \epsilon^k \le \epsilon^{floor(N/2)+1} \le \epsilon ^{N/2}$ and $0 < (1-\epsilon)^{N-k} \le 1$

So that $0\le \sum_{k=floor(N/2)+1}^N{N\choose k}\epsilon^k(1-\epsilon)^{N-k} \le (2\sqrt{\epsilon})^N \rightarrow 0$

 

[EngWiPy]

I believe your expression tends to 0 as $n \rightarrow \infty$, but I may be mistaking:

Since $0<\epsilon \le 0.001$, you get that $0 < \epsilon^k \le \epsilon^{floor(N/2)+1} \le \epsilon ^{N/2}$ and $0 < (1-\epsilon)^{N-k} \le 1$

So that $0\le \sum_{k=floor(N/2)+1}^N{N\choose k}\epsilon^k(1-\epsilon)^{N-k} \le (2\sqrt{\epsilon})^N \rightarrow 0$

The upper bound expression you reached is similar to something I have read. It was exactly:

\left[2\sqrt{\epsilon(1-\epsilon)}\,\right]^N\frac{1-\epsilon}{\epsilon}

However, the latter is not a tight upper bound. Would your upper bound be a tight upper bound? In my case, epsilon is a Gaussian Q function, so what I did is that I took only $\epsilon^L$ where $L=floor(N/2)+1$, and then used the Chernoff bound of the Q function as $Q(x)\le e^{-x^2/2}$. But as you can see, I used first lower bound but then upper bound, which isn't right. However, I have found that this upper bound is a better upper bound than the upper bound I provided earlier by simulations. I need to check if yours is yet better.

I need a lower bound for the Gaussian Q function then, or a new lower bound for the binomial distribution. Is there a simple one to find L or N in closed form given the lower bound, such that if the lower bound is $LP=f(x,L)$ I can find $L=f^{-1}(LP,x)$?

Thanks

 

[geoffrey159]

I am not competent to answer you about Chernoff bound, I don't know much about probabilities.
There is an easy lower bound that is $\epsilon^N$ since you are summing positive terms.

 

[EngWiPy]

I am not competent to answer you about Chernoff bound, I don't know much about probabilities.
There is an easy lower bound that is $\epsilon^N$ since you are summing positive terms.

I need a tight lower bound. $\epsilon^L$ is better than $\epsilon^N$ as a lower bound, since $\epsilon$ is small, and thus the terms with lower exponents dominate the result.

 

[mathman]

I am relying on the law of large numbers. If the mean < 1/2, then the probability of the average of N samples > 1/2 goes to 0, as N becomes infinite.

 

[EngWiPy]

I am relying on the law of large numbers. If the mean < 1/2, then the probability of the average of N samples > 1/2 goes to 0, as N becomes infinite.

I think, since $\epsilon$ is small, we can just take the first term ${N\choose L}\epsilon^L(1-\epsilon)^{N-L}$, which is approximated as a Gaussian random variable with mean $N\epsilon$ and variance $N\epsilon(1-\epsilon)$ as $N$ goes to $\infty$. But this approximation is not helpful for me to find $N$.

 

[mathman]

I think, since $\epsilon$ is small, we can just take the first term ${N\choose L}\epsilon^L(1-\epsilon)^{N-L}$, which is approximated as a Gaussian random variable with mean $N\epsilon$ and variance $N\epsilon(1-\epsilon)$ as $N$ goes to $\infty$. But this approximation is not helpful for me to find $N$.

What N are you looking for? The question is: what happens when as N\to \infty?

 

[EngWiPy]

I believe your expression tends to 0 as $n \rightarrow \infty$, but I may be mistaking:

Since $0<\epsilon \le 0.001$, you get that $0 < \epsilon^k \le \epsilon^{floor(N/2)+1} \le \epsilon ^{N/2}$ and $0 < (1-\epsilon)^{N-k} \le 1$

So that $0\le \sum_{k=floor(N/2)+1}^N{N\choose k}\epsilon^k(1-\epsilon)^{N-k} \le (2\sqrt{\epsilon})^N \rightarrow 0$

Why $(2\sqrt{\epsilon})^N \rightarrow 0$ as $N\rightarrow \infty$?

 

[mathman]

Why $(2\sqrt{\epsilon})^N \rightarrow 0$ as $N\rightarrow \infty$?

2\sqrt{\epsilon}&lt;1

 

[EngWiPy]

2\sqrt{\epsilon}&lt;1

You asked me why I need to find N. My actual problem is that I have a limit on $\sum_{k=floor(N/2)+1}^N{N\choose k}\epsilon^k(1-\epsilon)^{N-k}\leq \eta$. I have two variables here $\epsilon\leq 0.5$ and $N$, and $\epsilon$ is a function of $N$. In particular, $\epsilon=Q\left[\sqrt{\frac{2\,x/N}{y/N+1}}\right]$, where $x$ and $y$ are given, and $Q[.]$ is the $Q$ Gaussian function. I need to find $N$ such that the inequality holds. I said that $\epsilon\leq 10^{-3}$, but actually, I don't have control over $\epsilon$. All I know is that $\epsilon\leq 0.5$. I think in this case, the asymptote doesn't hold always, does it?

 

[mathman]

You asked me why I need to find N. My actual problem is that I have a limit on $\sum_{k=floor(N/2)+1}^N{N\choose k}\epsilon^k(1-\epsilon)^{N-k}\leq \eta$. I have two variables here $\epsilon\leq 0.5$ and $N$, and $\epsilon$ is a function of $N$. In particular, $\epsilon=Q\left[\sqrt{\frac{2\,x/N}{y/N+1}}\right]$, where $x$ and $y$ are given, and $Q[.]$ is the $Q$ Gaussian function. I need to find $N$ such that the inequality holds. I said that $\epsilon\leq 10^{-3}$, but actually, I don't have control over $\epsilon$. All I know is that $\epsilon\leq 0.5$. I think in this case, the asymptote doesn't hold always, does it?

You need \epsilon \lt 0.5, if = 0.5, it is ambiguous, since the law of large numbers requires an open interval <0.5 around \epsilon.

 

[EngWiPy]

You need \epsilon \lt 0.5, if = 0.5, it is ambiguous, since the law of large numbers requires an open interval <0.5 around \epsilon.

I think we can safely assume it is less than 0.5.

 

[mathman]

https://en.wikipedia.org/wiki/Law_of_large_numbers

I suggest you look at the above.