In a crowded room with 512 people, there are 9 different types of blood antigens. Each person has a blood type corresponding to a distinct subset of the antigens; the remaining of the antigens are foreign to them.

Matt the Mosquito flies around the room, picks a subset of the people uniformly at random, and bites the chosen people in a random order. After biting a person, Matt stores a bit of any antigens that person had. A person bitten while Matt had k blood antigens foreign to him or her will suffer for k hours. What is the expected total suffering of all 512 people in hours?

Let $n=9$ be the number of different antigens.

I think the linearity of expectation could be useful. Note that each person is bitten with probability 1/2. Consider a person P and an antigen a foreign to him/her. Assuming P has been bitten, it would be useful to find the probability P will suffer due to a. There are $2^{n-1}$ people with antigen a. But I'm not sure how to find the probability P will suffer due to a. Though with this given probability, it should be possible to use linearity over pairs (P,a) where P is a person and a is an antigen foreign to that person.

  • 1
    $\begingroup$ I suggest: do this for a smaller power of $2$ than $2^9$. Work it out for $2^n$, $n≤4$, say. If nothing else, that will let you test whatever formula you eventually find. $\endgroup$
    – lulu
    Mar 8 at 19:24
  • $\begingroup$ This problem seems tricky to me. Assume that Person-1 is bitten, and that Person-1 is not immune to Antigen-1. You can reason that of the $256$ people in the room that you expect to have Antigen-1, $128$ of them will be bitten. However, it is unclear to me whether you can conclude from this that Person-1's expectation of suffering from Antigen-1 specifically is $\dfrac{128}{129}.$ That is, of the $256$ people bitten by Matt, you might have (for example) that $129$ of them have Antigen-1, while only $127$ of them have Antigen-2. ...see next comment $\endgroup$ Mar 8 at 19:52
  • $\begingroup$ So, assuming that Person-1 is not immune to either Antigen-1 or Antigen-2, this would imply that Person-1's expected combined suffering from Antigen-1 and Antigen-2, based on the $(129,127)$ assumption would be $$\frac{129}{130} + \frac{127}{128} \color{red}{\neq} 2 \times \frac{128}{129}.$$ ...see next comment $\endgroup$ Mar 8 at 19:55
  • $\begingroup$ Because I am insecure that my intuition might lead to an inaccurate answer, I would consider the approach that the probability is $$\frac{\binom{512}{k}}{2^{512}},$$ that Matt bites $k$ people. Then, of these $k$ people, there must be an element $~a \in \{0,1,2,\cdots,k\}~$ such that exactly $~a~$ of these $~k~$ people have Antigen-1, and $~(k-a)~$ of these people do not have Antigen-1. So, I would compute $p(a,k)$, which is the probability that exactly $a$ of the bitten people have Antigen-1, under the assumption that $k$ people were bitten. ...see next comment $\endgroup$ Mar 8 at 20:13
  • $\begingroup$ This (very ugly, very inelegant, but doable) approach would allow me to compute all of the hours of suffering specifically caused by Antigen-1. Then, I would have to ponder whether Linearity of Expectation can be applied to each Antigen, so that I could simply take the Antigen-1 computation and multiply it by $9$. Personally, my intuition in this area is no where near developed enough to have any confidence that I can determine when the Linearity of Expectation shortcut can be applied. This is a tricky problem. $\endgroup$ Mar 8 at 20:16

1 Answer 1


I agree: linearity of expectation is a good approach here.

Notation setup

I'm going to treat the problem size as a parameter: Let's say there are $N$ types of antigens and $2^N$ people in the room. (Your statement is the special case $N=9$.)

Let $S$ be the total suffering across all people, $S_p$ be the total suffering for person $p$, and $S_{p,a}$ be the amount of suffering of person $p$ from antigen $a$. Let $P_{p,a}$ be the probability that person $p$ ends up suffering from antigen $a$. Thus $S_{p,a}$ will always be $1$ (with probability $P_{p,a}$) or $0$ otherwise.

Reducing using linearity of expectation

You're asking for $E[S]$, and we can write $$\begin{align} E[S] &= E\left[ \sum_{p} S_p \right] \\ &= E\left[ \sum_{p,a} S_{p,a} \right] \\ &= \sum_{p,a} E[S_{p,a}] \\ &= \sum_{p,a} P_{p,a} \end{align}$$ where I've used linearity to pull the sum outside the $E$.

Solving the reduced problem

Opening comment: Biting a uniform random subset of people is the same as flipping an independent fair coin to decide whether to bite each person. I find the second interpretation much more useful in terms of intuition and I recommend readers think about it this way.

With the L.o.E. reduction in mind, the problem is reduced to finding $P_{p,a}$. If person $p$ already has antigen $a$, or if $p$ never gets bitten, then they certainly won't suffer from $a$. So let's focus on the case where person $p$ does not have antigen $a$ and does get bitten. In that case, there are $2^{N-1}$ other carriers who do have antigen $a$. Some number of those carriers will be bitten; the probability of exactly $k$ carriers being bitten is $\binom{2^{N-1}}{k} / 2^{\left(2^{N-1}\right)}$.

Given that exactly $k$ carriers are bitten, the probability of person $p$ catching disease $a$ is exactly $\frac{k}{k+1}$, since if we ignore everyone except those $k$ carriers and $p$, they'll escape the disease only if they are the first one bitten out of these $k+1$ people.

The probability that person $p$ gets bitten is $\frac 1 2$, so we can write (assuming $p$ does not start out with antigen $a$) $$\begin{align} P_{p,a} &= \frac 1 2 \left[ \frac{1}{2^{\left(2^{N-1}\right)}} \sum_{k=0}^{2^{N-1}} \binom{2^{N-1}}{k} \frac{k}{k+1} \right] \\ &= \frac 1 2 \left(\frac{1}{2^{\left(2^{N-1}\right)}} \right) \left(\frac{1 - 2^{\left(2^{N-1}\right)} + 2^{\left(2^{N-1}\right)} 2^{N-1}}{2^{N-1}+1}\right) \\ &= \frac 1 2 \left[ \frac{1}{2^{\left(2^{N-1}\right)}\left(2^{N-1} + 1\right)} + \frac{2^{N-1}-1}{2^{N-1}+1} \right] \end{align}$$

I'm omitting proof of the step where I replace the $\sum_k$ with a closed form. It can be shown by combinatorics or by induction, but easiest is by WolframAlpha. I used this query and got these results:

enter image description here

Anyway, now we can put the subanswers together to answer the full problem. For each $a$, exactly $2^{N-1}$ people start out with the disease (hence have no chance of catching it) and the other $2^{N-1}$ people start without the disease (hence their chance of catching it is given by the messy formula above). So our final answer is:

$$\begin{align} E[S] &= \sum_a \sum_p P_{p,a} \\ &= \sum_a 2^{N-1} \frac 1 2 \left[ \frac{1}{2^{\left(2^{N-1}\right)}\left(2^{N-1} + 1\right)} + \frac{2^{N-1}-1}{2^{N-1}+1} \right] \\ &= \boxed{N 2^{N-2} \left[ \frac{1}{2^{\left(2^{N-1}\right)}\left(2^{N-1} + 1\right)} + \frac{2^{N-1}-1}{2^{N-1}+1} \right]} \end{align}$$

Intuition and double-checking

Intuitively, unless $N$ is tiny, if person $p$ starts out without antigen $a$ and gets bitten then I would pretty much expect them to catch $a$. Like if $N = 100$, there are just so so many infected people that had a chance to get bitten first; it seems pretty unlikely that person $p$ will avoid infection. This is borne out by the boxed formula above: all the stuff inside $\left[ \cdots \right]$ will be pretty close to $1$ for large $N$ (or really for any $N$ bigger than like $2$ or $3$), so the answer will be pretty close to $N 2^{N-2}$ which is what we'd get if every bitten person catches every disease they don't start with.

We can also double-check the exact formula using a Python simulation. I used this code:

# use the formula we derived
def exact(N):
    return N*2**(N - 2)*(1/(2**(2**(N - 1))*(2**(N - 1) + 1)) + (2**(N - 1) - 1)/(2**(N - 1) + 1))

import random
# simulate a bunch of times to get an approximate answer
def sim(N, NUM_TRIALS):
    total_suffering = 0
    for trial_num in range(NUM_TRIALS):
        current_suffering = 0

        # decide who gets bitten
        bitten = []
        for p in range(2**N):
            if random.randint(0,1) == 1: bitten.append(p)
        # random bite order
        diseases = 0  # track which diseases the fly is carrying
        for p in bitten:
            diseases |= p  # fly catches all of p's diseases
            current_suffering += diseases.bit_count() - p.bit_count()  # suffer 1 hour per disease that the fly has but p didn't have before
        total_suffering += current_suffering
    return total_suffering / NUM_TRIALS

for n in range(0, 10):
    ex = exact(n)
    si = sim(n, 10**5)
    print(n, ex, si, sep='\t')

and I got these printouts:

0   0.0 0.0
1   0.125   0.12479
2   0.8333333333333333  0.83008
3   3.675   3.67416
4   12.45138888888889   12.44043
5   35.29415355009191   35.31057
6   90.1818181824955    90.21302
7   217.1076923076923   217.13148
8   504.06201550387595  504.04763
9   1143.035019455253   1142.75689

That's enough accuracy to make me feel mostly convinced that the formula is right. I also tried running with more trials for some of the smaller $N$ values and confirmed that the simulation results got a little closer to the exact answers.

Additional confirmation: Full brute force for small $N$

A skeptical commenter suggested using a full brute force solver to confirm the exact answer for small $N$. Here's some Python code:

import itertools
import math
import fractions
def count_suffering(bitten):
    suffering = 0
    diseases = 0
    for p in bitten:
        diseases |= p  # fly catches all of p's diseases
        suffering += diseases.bit_count() - p.bit_count()  # suffer 1 hour per disease that the fly has but p didn't have before
    return suffering

def bruteforce(N):
    total_suffering = fractions.Fraction(0)
    for num_bitten in range(2**N+1):
        for bitten in itertools.combinations(range(2**N), num_bitten):
            current_suffering = fractions.Fraction(0)
            for bitten_ordered in itertools.permutations(bitten):
                current_suffering += count_suffering(bitten_ordered)
            total_suffering += current_suffering / math.factorial(num_bitten)
    bitten_options = 2**(2**N)  # total number of subsets we could have picked
    expected_suffering = total_suffering / bitten_options
    return expected_suffering

for n in range(4): print(bruteforce(n))

and the output:


I've confirmed that these are the same as my formula's output for $N=0, 1, 2, 3$. If I really cared I could code this in C++ and then the $N=4$ case would also finish in a reasonable amount of time. I'm not bothering because I honestly just feel sufficiently convinced that the formula is correct already, and I think Python is a better language to post here since more people can read it.

Bonus notes

The exact answer to the specific version you asked ($N = 9$) is: $$\frac{265742844799640668497095410594938748523254614807645094470555155298160632523653129}{232488804171798923623888618337756189986643641086481444985473430390888080605184}$$

Viewing the answer as a function $S(N)$, it turns out that $\tilde S(N) = N 2^{N-2} - N$ is an extremely close approximation. The first several values of $S(N) - \tilde S(N)$ are:

0   0.
1   0.625
2   0.833333
3   0.675
4   0.451389
5   0.294154
6   0.181818
7   0.107692
8   0.0620155
9   0.0350195
10  0.0194932

So for most practical purposes you'd be fine using that much simpler formula instead.

  • $\begingroup$ "The probability that person p gets bitten is $~\dfrac{1}{2}$" : strangely enough, I think that this is invalid, since you have committed to analysis based on associating a certain probability to the event that exactly $~k~$ people are bitten. Inside this case, when $~k~$ people are bitten, the probability that Person-1 is bitten is $$\frac{k}{2^N}.$$ $\endgroup$ Mar 9 at 6:54
  • $\begingroup$ @user2661923 I'm not talking about the probability of $k$ people being bitten, but rather about the probability of $k$ carriers of antigen $a$ being bitten. That's what creates the discrepancy between our formulas: I have $2^{N-1}$ (the number of people carrying antigen $a$) where you have $2^N$ (the total number of people). Thanks again for your careful checking though! $\endgroup$ Mar 9 at 6:54
  • $\begingroup$ I was responding to your first comment, but my response addresses your second comment. Person $p$ being bitten is independent from how many $a$-carriers are bitten, since $p$ was assumed not to be an $a$-carrier. (Probably this is clear to you though, and the misunderstanding in my comment above would make you satisfied.) $\endgroup$ Mar 9 at 6:56
  • $\begingroup$ I think my math is correct, at least on the points you're bringing up. I'm happy to explain a bit more in the comments (or maybe edit the post if the discussion brings up points that I think could likely help others too). I would suggest against deleting your comments even if you later think they're wrong, since someone else might go down the same wrong path; personally I'd rather just make a later comment explaining why you were wrong before, so that a later reader could benefit from what you learned. $\endgroup$ Mar 9 at 7:03
  • $\begingroup$ No, I deleted my comments, which I think is best. Initially, I strongly suspected that you had made a mistake. Now that you have explained your thinking, given my lack of intuition around linearity of expectation problems, I make it at least 50-50 that I am wrong, and that you are right. Given that, I don't think it is appropriate to leave my comments. $\endgroup$ Mar 9 at 7:06

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .