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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $S$ be a random subset of $[n]=\{1,2,\ldots,n\}$ chosen uniformly from $[n]$'s subsets. How can I find a function $f(n)$ s.t. for any $\varepsilon \gt 0$,

$$\lim_{n \rightarrow \infty} P\left[(1- \varepsilon) f(n) \le \lambda (S) \le (1 + \varepsilon)f(n)\right]=1 ?$$

share|cite|improve this question
What is the purpose of these 2 links? – Did Feb 12 '13 at 20:52
What did you try to solve this question? – Did Feb 12 '13 at 20:52
@Did related material I found but didn't help me. may helps to other people. – mati Feb 12 '13 at 20:54
What did you try to solve this question? – Did Feb 12 '13 at 21:00

Here is the answer: $f(n)=\log_2n$. I hesitate to post a full proof, for the usual reasons.

share|cite|improve this answer
I didn't find How can I bound it using one of this equlities:, tried Chernoff's inequality, and Markov's – mati Feb 12 '13 at 21:31
Concerning the usual reasons: On MathOverflow, we're getting flags claiming that this user's questions come from a take-home exam that is in progress. – Scott Carnahan Feb 13 '13 at 1:15
@ScottCarnahan Thanks for the information. This is not what I was referring to but confirms my hesitations. – Did Feb 13 '13 at 6:00
And now the OP is seemingly covering their tracks. – Did Feb 13 '13 at 6:06

Your Answer


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.