Random movement and knowledge-swapping Suppose you have N people and N rooms. Everyone starts knowing their own name, but no-one else's. Every timestep, everyone goes to a random room then swaps all the names they know with everyone in the said room.
What's the mean (and ideally, probability distribution of the) number of timesteps before everyone knows everyone's name?
(In particular, I'm interested in the asymptotic behavior for large N.)
With $2$ people in $2$ rooms, the problem is simple. Every timestep there is a $50\%$ chance of the two people ending up in the same room, so it's a geometric distribution with $p=1/2$ or mean of $2$.
Ditto, there's always a $\frac{1}{{N}^{N-1}}$ chance that everyone happens to pick the same room in the first timestep. (Which also, given that everyone happening to pick the same room always will mean everyone knows everyone's name, imposes a trivial upper bound on the mean number of timesteps, namely ${N}^{N-1}$. I suspect this is a wildly-weak upper bound, however.)
With more people / more rooms it gets complex very quickly, though.
 A: I'm not sure if you care too much about the constant factor in the end; if you do, the analysis gets hairy.
The big picture should be that for most names, the number of people that know the name approximately doubles at each step, at least initially, and so it takes around $\log_2 N$ steps before a constant fraction of people know the name, for pretty much any constant fraction you like. However, there are going to be a few people remaining who take a $\mathcal O(\log N)$ more steps to reach. The reason is that any given person, at any given moment, doesn't talk to anyone for the next $t$ timesteps with probability roughly $e^{-t}$: so with a linear number of people left to reach, we expect the loneliest one of them to stay lonely for $\ln N$ timesteps (by which time we expect that everyone else knows the name, and the last remaining person does learn it).
In addition, a few names get slowed down at the beginning. Once again, we expect that the "shyest" person out of $N$ to avoid being in the same room with anyone for about $\ln N$ timesteps, so that nobody else learns their name. A similar but less extreme thing can happen with $2$ people, or with $3$, but the more people know a name, the more momentum it has.
So overall, we still expect $\mathcal O(\log N)$ timesteps until everybody knows everybody's name, and if you don't care about the constant on that, then this is not too hard to prove.

The idea is that you can chop up the process of advancing from $1$ to $N$ people knowing a given name into $\mathcal O(\log N)$ stages: increasing by a factor of $1+\epsilon$ until the number reaches $\frac N2$, then decreasing the number of people that don't know the name by a factor of $1-\epsilon$ until no such people are left.
For sufficiently small $\epsilon$, we advance by at least one stage in each timestep with a probability of at least $\frac12$. This takes some work and presumably some Chernoff bounds, but it is actually only tight for the very first few stages and the very last few - and at those, you're only trying to gain one new "convert", which happens with probability roughly $1-\frac1e$ in both cases.
Say there are $W = \mathcal O(\log N)$ stages, with $W \ge 36\log N$ (If $W$ is too small, just chop up the range more finely.) Then the probability that any given name takes more than $3W$ timesteps to traverse all stages can also be bounded by the Chernoff bound:
$$\Pr[\text{Bin}(3W,\tfrac12) < W] \le \exp(-\tfrac1{18}W) \le \exp(-2\log N) =N^{-2}$$
and so by the union bound, with probability $1 - \frac1N$ no name takes more than $3W$ steps to traverse all the stages, which gives means that in $\mathcal O(\log N)$ steps everyone knows everybody's name.
