Suppose that among a group of $n$ people, some unknown number of people $K$ know a rumor. If someone knows the rumor, there is a probability $p$ that they will tell it to us if we ask. If they don't know the rumor they will always say they don't know it.

If I go around and ask each person if they know about the rumor, and $M$ people say they do, what does that tell me about the number of people who actually know the rumor?

In particular, what is the distribution $P(K=k|M=m)$ in terms of $P(K)$?


I've been able to show that


where $b(m,k,p)$ is the binomial density function (probability of $m$ successes out of $k$ trials with probability $p$ of success). Is it possible to take this any further?

  • 2
    $\begingroup$ Do you know what $p$ is? Do you have a prior distribution for $K$? $\endgroup$ – hmakholm left over Monica Apr 29 '16 at 21:18
  • $\begingroup$ As Henning wrote. Also, the formulation "if I ask someone about the rumor, there is a probability $p$ that they will tell me if they know it" is unclear. Do you mean that with probability $p$ a person will tell you whether they know the rumour and with probability $1-p$ they will refuse to tell you whether they know the rumour? Or do you mean that whoever doesn't know the rumour will tell you so and whoever does know the rumour will tell you so with probability $p$ and will deny it with probability $1-p$? $\endgroup$ – joriki Apr 29 '16 at 21:28
  • $\begingroup$ Sorry, edited to clarify. Someone who does not know will not lie. Only someone who knows the rumor might say they don't know it. $p$ and $n$ are known, fixed quantities. $\endgroup$ – Max Apr 29 '16 at 22:10
  • 2
    $\begingroup$ I've been giving this some more thought, and I must agree that it definitely depends on the prior distribution of $K$. $\endgroup$ – Max Apr 30 '16 at 1:31
  • $\begingroup$ If you want an estimator of $k$ without using a prior, you could take a maximum likelihood approach which might suggest rounding down $\lfloor m/p \rfloor$ (or $1$ less if this is an integer: there would then be two equal likelihoods), though if this is more than $n$ then take $n$ instead. $\endgroup$ – Henry May 24 '16 at 21:28

For the expected value/mean, we can ignore the people who haven't heard the rumor entirely. You should find that $M=pK$, which makes sense as the people who haven't heard of the rumor won't add anything to the number of people who tell you they have heard the rumor. This means that $K\approx\frac M p$. Unfortunately, this is only the mean, and not a distribution. Now, what we are going to do is rewrite $M$ as a Binomial Distribution, so $P(X=M)={K\choose M}\cdot p^M\cdot(1-p)^{K-M}$, where $M$ is the number of people who answer yes and $K$ is the total number of people who know the rumor. Now, we want to fix $M$ and let $K$ vary. First, we know that $M\leq K$, so $P(K=x)=0\quad(\forall x<M)$. For $x\geq M$, we can use $$P(X=K|M=m)=\frac{{K\choose M}\cdot p^M\cdot(1-p)^{K-M}}{\int_M^\infty {K\choose M}\cdot p^M\cdot(1-p)^{K-M} dK}$$ Simplifying by considering $p$ and $M$ are constants, we get $$\frac{{K\choose M}\cdot(1-p)^K}{\int_M^\infty{X\choose M}\cdot(1-p)^X dX}$$ We can make one last deduction to simplify this, namely $K\leq n$. This means that we can replace the $\infty$ with an $n$ to get $$\frac{{K\choose M}\cdot(1-p)^K}{\int_M^n{X\choose M}\cdot(1-p)^X dX}$$ I made it continuous, but you can make it discrete by replacing the integral with a summation. $$\frac{{K\choose M}\cdot(1-p)^K}{\sum_{X=M}^n{X\choose M}\cdot(1-p)^X}$$

In summary, I modeled the probability that you got $M$ people telling you if $K$ people knew and if they had a probability of $p$ of telling you using the binomial distribution. I then assumed that $M\leq K \leq n$ and had a uniform distribution because no distribution was specified. I then fixed $M$ since it was known and let $K$ vary. I then found the probability that $M$ out of $K$ people who knew the rumor told you and normalized it across all possible $K$s.

| cite | improve this answer | |

If you know the distribution of $K$ you can do the following.

Clearly, we have $m\leq k$ because you can't have more people telling you the rumor than those who actually know it (we assume people are honest here).

So for $$\forall k\lt m \space P[K=k \vert M=m] = 0$$

Next, we know that among the remaining $(n-m)$ people, some know the rumor and some don't.

Hence i can assert that $(k-m)$ people know the rumour and didn't tell me while the other $(n-k)$ just don't know.

Pleate note that $(n-m) \ge (k-m)$.

So $$P[K=k \vert M=m] = P[\{K=k-m\}\cap\{M=0\}]$$

$$P[M=0 \vert K=k-m]P[K=k-m] = (1-p)^{k-m}P[K=k-m]$$

I hope this is of any help.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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