Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Denote by $P_n$ the set of all subsets of $\lbrace 1,2,3, \ldots ,n \rbrace$. Obviously, the proportion of subsets in $P_n$ of size $\leq \frac{n}{2}$ tends to $\frac{1}{2}$. What about the proportion of subsets of size $\leq \frac{n}{3}$ ?

share|improve this question
    
Numerical computation would suggest it goes to $0$. But the naive bounds don't seem to give it to you. –  JSchlather Nov 13 '12 at 20:31
add comment

3 Answers 3

up vote 2 down vote accepted

The number of subsets of size $k$ is $n \choose k$. The first fact is true because the left half of a late row of Pascal's triangle (maybe you're missing the middle term) has roughly half the total (by symmetry). However, in late rows of Pascal's triangle, the middle third terms are far greater than the first third, so you should expect the proportion to tend to zero.

One quick and dirty way to make this formal is to use this mathoverflow bound on the sum of the first k terms in the nth row. Explicitly, if $n=3m$, then $2^{-n}\sum_{k=0}^{n/3}{n \choose k}\le2^{-3m}{3m \choose m}\frac{3m-\left(m-1\right)}{3m-\left(2m-1\right)}\to2^{1-3m}{3m \choose m}\to0$.

share|improve this answer
add comment

The law of large numbers says that for every $\epsilon>0$ the probability that you get less than a fraction ${1\over2}-\epsilon$ heads in $n$ tosses of a coin tends to $0$ when $n\to\infty$. This is true in particular for $\epsilon={1\over6}$.

share|improve this answer
add comment

The following heuristic argument may help in understanding the phenomenon. Let $X$ be the number of heads when a fair coin is tossed $n$ times. We want to estimate $$\Pr\left(X \le \frac{n}{3}\right).$$ This probability is well approximated by the probability that a normally distributed random variable with mean $\dfrac{n}{2}$ and standard deviation $\dfrac{\sqrt{n}}{2}$ is less than or equal to $\dfrac{n}{3}$.

That in turn is equal to the probability that a standard normal is $\gt \dfrac{\sqrt{n}}{3}$. This probability approaches $0$ rapidly as $n$ increases.

More formally, we can use the Central Limit Theorem to prove that the limit is $0$. There are good estimates available for the error in the normal approximation to the binomial. These can be used to get precise information about the speed of convergence to $0$.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.