Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

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

I'm hoping for some help with this excericse in probability.

Let $V$ be a set and let $V'$ be a randomly chosen subset of $V$ such that each element belongs to $V'$ with probability $p$.

Now, let $S \subset V$ such that $|S|= x$, what's the probability that $|V' \cap S|<x/3$?

It might be easier to assume that $p=1/2$.

Thanks a lot.

share|cite|improve this question
It's the probability of $<x/3$ successes in $x$ independent trials with probability of success $p$. – user31373 Jun 8 '12 at 18:36
It will depend on how $V'$ is chosen: if the inclusion/exclusion of each element of $V$ is independent of the others then you may get a different result compared with choosing a fraction $p$ of the elements of $V$. – Henry Jun 8 '12 at 20:05
up vote 0 down vote accepted

Community wiki answer so the question can be marked as answered:

As noted by user31373 in a comment, this is the probability of $\lt x/3$ successes in $x$ independent trials with probability of success $p$, which is

$$ \sum_{k=0}^{\left\lceil\frac x3\right\rceil-1}\binom xkp^k(1-p)^{x-k}\;. $$

share|cite|improve this answer

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.