Vtyjkyuk

Question:

Suppose that $NinmathbbN$ immigrants (nodes) are connected by an Erdős–Rényi random graph and that the average degree is $lambda$. The graph is fixed at the beginning of time (before anyone has immigrated).

One by one, all $N$ immigrants move to a new country. As they move to the country, they make native acquaintances according to the following timeline (the acquaintances are not incorporated into the graph):

1. A new immigrant arrives.


2. The immigrant randomly meets one native, who becomes an acquaintance.


3. The immigrant talks to all the immigrants in his neighborhood who have already arrived in the country. All of their native acquaintances become his acquaintances (but not vice-versa).


4. The next immigrant arrives.

Assume that the native population is large so that the chance that two immigrants randomly meet the same native is 0.

As $Nto infty$, what is the distribution of acquaintances over immigrants, $A_n_ninmathbbN$?

Notes:

• An immigrant will only acquire acquaintances between when he arrives and the next immigrant arrives.


• The first immigrant will always only have a single acquaintance.


• Any immigrant who is not connected will always only have a single acquaintance.


• An immigrant connected to $k$ other immigrants who have already immigrated must have at least $k+1$ acquaintances.


• If the network has no edges ($lambda=0$), then all immigrants will only have a single friend.


• Since this is a limit, the distribution should be supported over the natural numbers: $A_n>0$ for all $n in mathbbN$, as long as $lambda>0 $


• A well-known property of Erdős–Rényi graphs, is that the degree distribution, $d_n_ninmathbbN$, converges to a Poisson distribution as the number of nodes, $N$, becomes large.

Progress:

So far, I have been thinking about this a series of differential equations $A_n(t)_ninmathbbN cup 0$. Then $alpha_n(t)$ is the share of immigrants with $n$ acquaintances after fraction $t$ of the immigrants have moved to the new country. Then $alpha_n(1)=A_n $. Here's what I know so far:

• $alpha_0=1-t$ is simply the share who have not moved.


• $dotalpha_1=sum_nin mathbbNd_ncdot (1-t)^n$. I only have a single acquaintance if none of my neighborhood has immigrated.


• Things get quite complicated after that.