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.