Say $\sigma_1, \sigma_2, \dots, \sigma_m$ are i.i.d distributed $\pm1$ variables. How do I show that for any choice of $S_1, S_2, \dots, S_d$ subsets of $\{1, 2, \dots, m\}$, the expectation of the supremum over $S_i$ of the absolute value of the sum of the $\sigma$'s with indices in $S_i$ is bounded above by $\sqrt{2m \log d}$?


closed as off-topic by Kaveh, Lev Reyzin Jun 5 '15 at 20:58

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Our site policy prohibits simultaneous crossposting: it duplicates effort and fractures discussion. Crossposting is permitted after a week has passed without a satisfying answer elsewhere. When crossposting please summarize the relevant discussions from other sites in your question and link between the copies in both directions." – Lev Reyzin
If this question can be reworded to fit the rules in the help center, please edit the question.


This is not a research-level question (is it homework?). Hint: See Massart's Finite Class Lemma, for example here: http://ttic.uchicago.edu/~tewari/lectures/lecture10.pdf


Some additional context would be nice and would help initiate a meaningful discussion, as well as make sure that the requirements to use some bound are fulfilled. Also, while related, the question at hand is strictly not TCS, although such lemmas are frequently used in proofs. Finally, it would be beneficial to acquire to research on your own an answer to your question, since i you are planning of conducting additional research in the future this knowledge will be extremely valuable.

I would suggest looking into the so-called "concentration inequalities", which with little modification should provide an answer to your question. If you are still having trouble finding with an answer after a week, I would also recommend cross-posting this question to math.SE, which seems more suited to give an answer. Make sure you indicate the question has already been posted elsewhere and provide a link to it, as is required by our site's policy.

Finally, I would suggest you read the relevant information on the help center, on what kind of questions are relevant for cstheory.

PS: Posted this as answer as it contains some relevant information and it was too long for a comment.


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