How many Americans, randomly chosen, are needed to have a 50% chance two live in the same or adjacent states?

Question

Background

I'm studying common coincidences and "near" coincidences that nevertheless (unduly) impress the average person. The below question is an extension of the famous Birthday problem, which asks "How many people, randomly chosen, are needed for there to be a 50% chance two of them share the same birthday?" The answer is $23$. (It is actually a bit lower if one incorporates the fact that birthdays are not uniformly distributed throughout the year, but instead "clump" in certain months, thereby increasing the probability that two people share the same birthday.) If one relaxes the condition and allows the "near" coincidence of being the same birthday or differing by one day, the answer drops to just $14$, which many people find surprising.

The below is an extension of the birthday problem, but more interesting and complicated.

---

How many Americans, randomly chosen, are needed to have a 50% chance that two of them live in a) the same state or b) in the same or an adjacent state?

Assume we are given a list of the 50 states with their populations:

${\cal S} = \{ (AL, 4.803M), (AK, 0.738M), (AR, 2.978M), \ldots \}$

as well as an adjacency matrix ${\bf M}$ (or undirected graph $g$) containing the state-adjacency information (including self-adjacencies), i.e., share a border:

$\{ (CA, CA), (CA, WA), (CA, NV), (CA, AZ), (AK, AK), (ME, NH), \ldots \}$.

Note that we want to solve this problem by computation with conditional probabilities and without resort to stochastic simulations. Such a rigorous approach is principled and generalizes more naturally to very large problems.

The approach to a) will be a generalization of the Birthday problem, but the answer to b) seems a bit more complicated.

I'm seeking just the equations (and explanations). I can then compute the numerical values using census and geographic data.

I'll note here that through stochastic search, the answer to b) is a (perhaps surprising) just 3.5 people. With 4 people, the chances are nearly 60% at least two are from the same or neighboring states.

Answer 1

I'll answer question b) because it's more general, and question a) can just be thought of as a special case of b) where the adjacency matrix is simply the identity matrix. I'll give you the exact method, though approximate methods might be called for because the computation of the exact solution scales rapidly with number of people. I don't think there's a solution that scales better, but maybe someone can correct me.

It helps to look at it by doing the explicit case for a small number of people, adding more, and looking for the pattern.

Let's start with the probability of adjacent states for any two people. The probability that the first person is in state $i$, and the second person is in state $j$ is $$ P(i,j) = p_i p_j, $$ where $p_l = S_l/N,$ where $S_l$ is the number of people in state $l,$ and $N=\sum_l S_l.$ They are adjacent if $M_{i j} = 1,$ where $M_{i j}$ is the $i,j$th element of the adjacency matrix. Thus the probability they are adjacent is, $$ \begin{split} P_2 &= \sum_{i=1}^k \sum_{j=1}^k P(i,j) M_{i j} \\ &= 2 \sum_{i=1}^{k-1} \sum_{j=i+1}^k p_i p_j M_{i j} + \sum_{i=1}^k p_i^2, \end{split} $$ where I'm defining $P_m$ to be the probability that there's at least one adjacent pair in a group of $m$ people, and $k$ is the number of states. I'm also assuming that all diagonal elements of $M$ are one. As with the Birthday problem, however, it is more helpful to find the probability that they are not adjacent, which is, $$ Q_2 = 1-P_2 = 2 \sum_{i=1}^{k-1} \sum_{j=i+1}^k p_i p_j (1 - M_{i j}). $$

Let's look at it for $3$ people. It's easy to see that, $$ Q_3 = \sum_{i,j,l} p_i p_j p_l (1 - M_{i j}) (1 - M_{i l}) (1 - M_{j l}). $$ However, now it's also easy to see why this calculation can become intractable for a large number of people. The above cannot be factored in terms of $Q_2$ because $M_{i l}$ and $M_{j l}$ must appear in the $i,j$ sums, so an inductive process with which we determine $Q_{m+1}$ in terms of $Q_m$ seems to be out of the question. It must be solved explicitly for any value. However, as I did with the case of $2$ people, you can generally take the upper "right triangle" of the $m$-dimensional array of possible sets of people from mutually exclusive states, with the appropriate coefficient telling us how many ways that can happen. For example, in the case of three people where $i$, $j$, and $l$ are all different, there are $3! = 6$ ways that states $i$, $j$, and $l$ can appear through the three samples.

For $m$ people, $$ \begin{split} Q_m &= \sum_{i_1=1}^k \sum_{i_2=1}^k \cdots \sum_{i_m=1}^k \left( p_{i_m} \prod_{j=1}^{m-1} p_{i_j} \prod_{l=j+1}^m (1 - M_{i_j, i_l}) \right) \\ &= m! \sum_{i_1=1}^{k-m+1} \sum_{i_2=i_1+1}^{k-m+2} \cdots \sum_{i_m=i_{m-1}+1}^k \left( p_{i_m} \prod_{j=1}^{m-1} p_{i_j} \prod_{l=j+1}^m (1 - M_{i_j, i_l}) \right). \end{split} $$ The second line reduces it from a sum over $k^m$ terms to a sum over $k \choose m$ terms, which still scales very poorly. Also, each term involves a product over $m (m+1)/2$ factors. So overall, this is an $O({k \choose m} m^2)$ computation. If we ignore adjacency and answer question (a) then it becomes $O({k \choose m} m).$ But maybe you'll get lucky and the value of $m$ for which the probability first surpasses 50% will be very small.

Answer 2

It is possible to solve this using Markov Matrices to model the random process of selecting people. This approach requires quite a bet of effort to set up but it does have a structured way to get your answer.

Markov matrices are used to model a random process which can move between discrete "states" (to avoid confusion between US states and the markov states I will refer to markov states as "Phases").

In this context the markov phase is the list of all the states you chose Americans from. For example if the first american is from Washington the phase is {WA}, then if the next american is from Texas the phase is {TX,WA}. The order you chose people in is irrelevant so {TX, WA} is the same phase as {WA, TX}.

Before sampling begins we start in phase {0} where no Americans have been chosen. We define a single phase {E} (meaning "ending") where you have chosen two americans from adjacent states, the random process of choosing americans continues until {E} is reached. Continuing from phase {TX, WA}, if the next american is from Oregon then the phase transitions to {E} since Oregon is beside Washington.

{E} is known as an "absorbing state" because once the random process reaches {E} it cannot change to a different phase.

You must create a list of all possible phases which can occur before reaching {E}.

Now you need to calculate the Markov matrix $M$ for the probability of transitioning between states. First of all let $P$ be the vector of probabilities of sampling an American from a state. Then $P_{florida}$ is the chance of picking someone from Florida.

The entries in the Markov matrix $M_{ij}$ is the probability of transition from phase $i$ to phase $j$. For example, to transition from {WA} to {TX, WA} is $P_{Texas}$. The probability of transitioning from {WA} to {E} is $P_{Washington}+P_{Idaho}+P_{Oregon}$. And the probability of transitioning from {E} to {E} is 1.

You always start sampling from {0}. After 1 American has been sampled the probability of being in {E} is $M_{\{0\}\{E\}}$. After 2 Americans have been sampled then the probability of being in {E} is $(MM)_{\{0\}\{E\}}$ (The matrix M is multiplied by itself and then you get the probability from row {0} and column {E}).

Likewise after 3 Americans have been sampled the probability of being in {E} is $(MMM)_{\{0\}\{E\}}$. You need to keep multiplying M by itself until the probability is at least 50%

It takes a lot of effort to find $M$ but once you have that it's straightforward to get the result.