• Support PF! Buy your school textbooks, materials and every day products Here!

Probability problem: upper bounds on binomial CDF

  • Thread starter simba31415
  • Start date
  • #1
13
0

Homework Statement


Hi all, just a quick question here - the setup is as follows: X is a random variable, [itex]X \sim \operatorname{Bin}(m,p)[/itex] where [itex]p=2^{-\sqrt{\log n}}(\log n)^2[/itex] and [itex]m \geq 2^{\sqrt{\log n}}c[/itex] for constants c, n (n "large" here). I wish to show that [itex]\mathbb{P}(X < c) \leq e^{-(\log n)^2 c/3}[/itex]. I've been told to use "Chernoff-esque bounds" here; however, after teaching myself a little about Chernoff bounds I haven't found a way to make this work - I can see that the multiplicative form could be useful but I haven't yet figured out how to translate the bounds which I've found online into a workable form for this problem.

I'm told observing the fact that [itex]\mu = \mathbb{E}(X) \geq (\log n)^2 c = \mu '[/itex] should also help, so I suspect maybe what we really need is to show is [itex]\mathbb{P}(X < c) = \mathbb{P}(X < \frac{\mu'}{(\log n) ^2}) < \mathbb{P}(X < \frac{\mu}{(\log n) ^2}) \leq ^{(*)} e^{- \mu / 3} \leq e^{-\mu ' /3}[/itex] but as I said, no luck so far since I can't prove step [itex](*)[/itex] if indeed that is the way to do it. I suspect that this result only needs a few lines of work once you have the bound you require from Chernoff, so if anyone could show me how to do this I'd be very grateful! -S
 

Answers and Replies

  • #2
13
0
No thoughts anyone? Sorry to bump but I could really use some help with this, any thoughts at all please respond!
 

Related Threads on Probability problem: upper bounds on binomial CDF

  • Last Post
Replies
2
Views
2K
Replies
0
Views
697
  • Last Post
Replies
4
Views
2K
  • Last Post
Replies
6
Views
1K
  • Last Post
Replies
1
Views
922
Replies
11
Views
2K
  • Last Post
Replies
7
Views
17K
Replies
2
Views
984
  • Last Post
Replies
3
Views
3K
  • Last Post
Replies
1
Views
4K
Top