Probabilistic Method – 5

Q.1. Prove that {2m \choose m} \geq \frac{2^{2m}}{4 \sqrt{m} + 2}.

Solution.

Toss an unbiased coin 2m times with the coin tosses being independent. Let X denote the number of heads in the coin tosses.

\therefore E[X] = m; \mbox{ } Var [X] = m/2.

Pr[ | X - E[X] | < \sqrt{m} ] \geq 1 - 1/2 = 1/2. (using Chebyshev’s inequality) \ldots (1)

Also, Pr[ \mbox{ exactly k heads occur} ] = { 2m \choose k} 2^{-2m} \leq {2m \choose m} 2^{-2m}. (because {2m \choose m} \geq { 2m \choose k} for all possible k )

\therefore Pr[ | X - E[X] | < \sqrt{m} ] \leq (2 \sqrt{m} + 1) { 2m \choose m} 2^{-2m}. \ldots (2)

Combine (1) and (2) to get the desired result.

-

2 Responses to Probabilistic Method – 5

  1. Caitlin says:

    Nice words about the eternal cosmic law. Thanks for sharing. Be blessed!

  2. This is such an intesting post, certainly something to think about.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: