7
$\begingroup$

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.

|cite|improve this question
$\endgroup$
  • 2
    $\begingroup$ Yes, 3.5 is a very surprising result I would have thought it would be an integer. $\endgroup$ – Mark L. Stone Jul 11 '17 at 22:19
  • $\begingroup$ I would expect the answer to be around $3$. The Birthday problem teaches us that it is on the order of $\sqrt{50}\approx 7$. The smaller states won't play much of a role, though, making the effective number of states only around $25$. Furthermore, we need to consider only blocks of contiguous states, which (depending on what you mean by "adjacent") might roughly be groups of $5$ states or so. That leaves us with approximately $10$ "effective" states, with a square root of $3$. $\endgroup$ – whuber♦ Jul 11 '17 at 22:28
  • $\begingroup$ @whuber: "Adjacent" is defined rigorously: Share a border. $\endgroup$ – David G. Stork Jul 12 '17 at 1:02
  • 3
    $\begingroup$ Personally, if I needed an answer more accurately than whuber's back of the envelope calculation, I would simply simulate. If the population and adjacency information is already to hand I could probably do a bunch of simulations before I had found my pen and paper to start trying to write equations for it. (The exact coincidence calculation is a fair bit easier but even in that case I'd probably just simulate anyway) $\endgroup$ – Glen_b♦ Jul 12 '17 at 2:48
  • 1
    $\begingroup$ @David That might sound rigorous, but it's ambiguous. What if the border is an imaginary one in the middle of the ocean? E.g., do Hawaii and Alaska "share a border". What if the "shared border" is a single point, as in the Four Corners area? As you nicely made clear in your original post, these details don't matter for the present discussion--but they do matter for any specific calculations. $\endgroup$ – whuber♦ Jul 12 '17 at 12:53
3
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ This seems correct (though a bit disappointing in its conclusion). Let me watch a while for other potential answers before judging or accepting.... Thanks! $\endgroup$ – David G. Stork Jul 11 '17 at 18:47
0
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ This approach seems horrendously difficult and scales terribly. To guarantee we have a termination we might need to include sequences of 20 or so "phases" (US states), of which there are 47 trillion sequences. Completely unrealistic. Moreover, one must test explicitly whether termination has been reached at each step. Isn't there a way, closer to the analytic solution of the "near adjacent" Birthday problem, that deals solely with probabilities and conditional probabilities? $\endgroup$ – David G. Stork Jul 11 '17 at 18:05
  • $\begingroup$ if in phase {TX,WA}, what is the probability of transitioning to {TX,NM}, which is absorbing, vs. transitioning to {WA,NM}, which is not? All of that needs to be disambiguated in the state (phase) space definition. Edit: perhaps @David G. Stork is making a similar point. $\endgroup$ – Mark L. Stone Jul 11 '17 at 18:05
  • $\begingroup$ @Hugh: Why is "The probability of transitioning from {WA} to {E} is $P_{Washington} + P_{Idaho} + P_{Oregon}$"? For instance, if you're already in {WA}, why does its probability $P_{Washington}$ matter at all? And why the summation, not product? $\endgroup$ – David G. Stork Jul 11 '17 at 18:23
  • $\begingroup$ @DavidG.Stork Your second question is presumably because those are the states bordering WA, and draws are independent, so if we pick any one of those states then we're done. But yes, the number of Markov phases here is going to be ridiculously large. $\endgroup$ – Dougal Jul 11 '17 at 18:34
  • $\begingroup$ @DavidG.Stork As Dougal says the sampling ends if you pick the second person from a state bordering the first (washington) so you sum together the probabilities of each individual state bordering washington. $\endgroup$ – Hugh Jul 11 '17 at 18:54

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.