combinatoricsprobability
I have one question popped in my head out of nowhere at 3AM.
If we pick two random people in the world, what's the probability of them knowing each other?
You can assume that there are 7 billion people in the world and the idea of Six Degrees of Separation is relevant, or maybe you can assume one person has a circle of friends up to 100 people. You can provide any other assumptions to make it simple.
Please help answer my 3AM thought so I can sleep peacefully.
After thinking for a while, it seems to me that part of the problem you're actually struggling with is how to state and specify the "real life" problem that you want to solve, rather than actually solving it. One way to state and solve the problem is addressed below, here I'd like to discuss about other ways to specify the problem.
In short, you may want to have a look at Markov chains, or even hidden Markov chains. One way to see Markov chains, is that you have a system that can evolve between certain states, with a certain probability. Here for example, person $A$ could be your system, and its state could be which city $A$ is currently in. You can make things non uniform by specifying the probabilities with which the system can transition from one state to another. Want to include $B$? Make the system pairs of cities. Don't want to make the decision of $A$ and $B$ independent? That's already built-in with the probability to transition from one state to another. Want to have time play a role? One transition can be equivalent to one time unit, and a state can transition into itself to simulate that $A$ and $B$ do not move. Want to simulate a 2-day vacation to another city (staying 2 days somewhere, coming back to hometown)? Make a special state that can only transition back to the state it came from...
I think you get the idea. To conclude, the approach below could be modeled by a Markov chain, but it would probably be very annoying. The more "natural" thing to do with Markov chain would be to have $N$ and $M$ as random variables, enforcing them to be constant would probably be annoying? (Not sure, I haven't done any Markov chain in ages.)
You need to specify in some way what the probabilities are when $A$ and $B$ move around... For instance for $A$, is $N$ fixed or a random variable? Assuming $N$ is fixed, $A$ will visit $N+1$ points, let $T_i$ be the number of days $A$ stay at the $i$-th point. Can the $i$-th point and the $(i+1)$-th point be the same? I'll assume that they must be distinct. I'll also assume that $T_i\ge 1$ for every $i$, and that every $T_i$ is an integer.
Just looking at the $T_i$, there is $364\choose N$ possible choices of them. This corresponds to all the ways $A$ can choose to move around, without specifying where.
When looking at the locations, $A$ can choose between $P-1$ destinations, so if we disregard the "when", we have a choice between $(P-1)^N$ trajectories. I ignored the starting point, but if this is also a variable make that $(P-1)^{N+1}$.
If you put those together, there are ${364\choose N}(P-1)^N$ ways for $A$ to move around in the span of one year. Are all of these ways equally probable? Or is there some specific process for $A$ to choose when and where he moves? Unless you specify this information, it will be difficult to solve your problem.
Ps: if $A$ and $B$ start on the same point, they will obviously be together on the same point on day 1... you may want to revise your problem statement.
Nick G was faster than me, but I want to add a few remarks to his approach (read his answer first).
When $A$ and $B$ move simultaneously, there are indeed $(p-1)^2$ possible pairs of destination, but only $p-2$ outcomes where $A$ and $B$ meet. Indeed $A$ can move to $p-1$ points, but that number includes the point where $B$ is currently at. Because they cannot meet there, only $p-2$ cities (and outcomes) remain. So the probability that they do not meet right after they both move is $$\frac{(p-1)^2-(p-2)}{(p-1)^2}$$ When $X=k$, the probability they do not meet during the course of one year then becomes $$ P(\text{$A$ and $B$ do not meet}\mid X=k)= \left(\frac{p-2}{p-1}\right)^{N+M-2X}\times \left(\frac{(p-1)^2-(p-2)}{(p-1)^2}\right)^X $$
The last remaining problem is how to determine $X$. Let $T^A_i$ be the number of days $A$ stays in the $i$-th city he visits, likewise for $T^B_i$. Given the values of $T^A_i$ and $T^B_i$ it is possible to compute $X$. You didn't provide any information on the probability of having one set of $T^A_i$, $T^B_i$ over another, so I'll just assume uniform distribution. Also dealing with the durations of the stay is annoying, so instead let $U^A_i$ be the night when $A$ travels from the $i$-th city to the $(i+1)$-th city. The sequence $(U^A_i)_{1\le i\le N}$ is strictly increasing and has integer values between $1$ and $364$ (inclusive). We have likewise a sequence $(U^B_i)_{1\le i\le M}$ for $B$.
Without loss of generality assume $N\le M$. For an integer $k$, $0\le k\le N$, we want to compute $P(X=k)$, the probability that $X$ is equal to $k$. Because we assume uniform distribution, it is the number of ways to draw both $(U^A_i)$ and $(U^B_i)$ such that they share exactly $k$ identical night values divided by the total number of ways to draw $(U^A_i)$ and $(U^B_i)$. There are $364\choose k$ ways to choose $k$ distinct nights on which $A$ and $B$ both move. Following this, $A$ still move $N-k$ times on the remaining $364-k$ nights, while $B$ move $M-k$ times. However, those $(N-k)+(M-k)$ nights must be distinct, there are $364-k\choose N+M-2k$ ways to chose the nights they move on, and ${N+M-2k\choose N-k} = {N+M-2k\choose M-k}$ ways to decide whether $A$ or $B$ is the one moving during those nights.
In the end there are $$ {364\choose k}\times{364-k\choose N+M-2k}\times{N+M-2k\choose N-k} =\frac{364!}{k!\,(364-N-M+k)!\,(N-k)!\,(M-k)!} $$ different ways to draw the nights $(U^A_i)$ and $(U_i^B)$ so that $A$ and $B$ move the same night exactly $k$ times. In total, there are ${364\choose N}\times{364\choose M}$ ways to draw the nights (without constraints). This means we can compute $P(X=k)$.
To conclude, $$ P(\text{$A$ and $B$ do not meet}) =\sum_{k=0}^N P(X=k)\times P(\text{$A$ and $B$ do not meet}\mid X=k) $$ and you want to take $1$ minus the above to answer your problem. I have no clue whether there is a nice simplification of the various formula, but at least a computer can do the work for you.
Also note that the assumption in this model are not very "realistic". As TMM pointed out, most people should have some kind of pattern when travelling. Uniform distribution on the $(U^A_i)$ and $(U^B_i)$ also means the below situations have the same likelihood:
Depending on the circumstances, those may not be desirable properties...
I'll assume that you intended the relation “$A$ knows $B$” to be symmetric, i.e. if $A$ knows $B$, then $B$ knows $A$.
Also, you didn't specify how the two people are chosen; I'll assume that a pair of people is uniformly randomly selected among all pairs of people (or equivalently, that two people are independently uniformly randomly selected without replacement).
I'll also assume that the only acquaintances there are are the ones you describe and the ones we can deduce from them (so most of the million people don't know anyone).
If so, the probability of choosing a pair of people is the number of pairs of people who know each other over the total number of pairs of people.
The total number of pairs of people is
$$ \binom{1000000}2=\frac{1000000\cdot999999}2=499999500000\;. $$
To determine the number of pairs of people who know each other, consider the subset of $2200$ people. You've specified how many people they know for $2199$ of them, and from that we can deduce how many people the remaining person knows. The person who knows all $2199$ must know the person who only knows $1$, and the person who only knows $1$ knows no one else, so that determines all acquaintances for those two people. If you subtract this $1$ acquaintance from everyone else's total, the remaining $2198$ people fulfill the same type of description: For each number from $1$ to $2197$, there's someone who knows that number of people. So we can continue in this manner, resolving the person with most and least acquaintances in each step.
If we do this for a subset of $n$ people, if $n$ is odd, the process will end after $\frac{n-1}2$ steps with the $1$ person whose number of acquaintances you didn't specify, and they will have been assigned $\frac{n-1}2$ acquaintances. If $n$ is even, the process will end after $\frac n2$ steps with no people, and the $1$ person whose number of acquaintances you didn't specify will have been assigned $\frac n2$ acquaintances. Thus, in either case there are
$$ \frac12\left(\sum_{k=1}^{n-1}k+\left\lfloor\frac n2\right\rfloor\right)=\frac12\left(\frac{n(n-1)}2+\left\lfloor\frac n2\right\rfloor\right)=\left\lfloor\frac{n^2}4\right\rfloor $$
acquaintances in the subset (where the factor $\frac12$ accounts for the fact that we counted each acquaintance twice, once from either side). In your case, with $n=2200$, this is
$$ \left\lfloor\frac{2200^2}4\right\rfloor=\frac{2200^2}4=1210000\;. $$
Thus, the probability of selecting two people who know each other is
$$ \frac{1210000}{499999500000}=\frac{11}{4545450}\approx2.42\cdot10^{-6}\;. $$
Best Answer
All you need to know is the average number of people the average person knows, plus the total population of the world. (By "knows" here, I am assuming a reciprocal relationship, discounting the fact that everyone "knows" lots of celebrities who don't know them from Adam.) If $K$ represents this average, and $P$ represents total population, then the answer is $K/(P-1)$.
To elaborate, just a bit, we have
$$K={1\over P}\sum_{i=1}^Pk_i$$
where $k_i$ is the (precise) number of people known to person $i$. When you pick two people at random, the first person will be person $i$ with probability $1/P$, and the second person will be known to person $i$ with probability $k_i/(P-1)$, and thus the probability the two people will know one another is $\sum_{i=1}^P{1\over P}{k_i\over(P-1)}=K/(P-1)$.
As a practical matter, the probability is pretty small, probably well under one in a million. Even if you restrict just to the U.S., the probability is likely to be around one in half a million: It has been estimated that the average American knows about $600$ people.
Note, the six-degrees-of-separation phenomenon and the Birthday Paradox play no role here. They would have role if we were assembling (at random) some medium-sized group of people and asking, for example, for the probability that some pair of them are connected by a chain entirely within the group.