Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

In a certain company with n people, any two people know each other randomly with probability 0.5. As n gets bigger, what happens to the probability that everyone is connected?

goes to 0 goes to 1 goes to a different constant does not converge

share|improve this question

closed as off-topic by Jonas Meyer, Claude Leibovici, Yiorgos S. Smyrlis, N. F. Taussig, kjetil b halvorsen Apr 25 at 10:58

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Jonas Meyer, Claude Leibovici, Yiorgos S. Smyrlis, N. F. Taussig
If this question can be reworded to fit the rules in the help center, please edit the question.

I am confused by your question. When you say that two people are "connected," does that mean that one directly knows the other or that there exists a sequence of acquaintances which links one person to every other person in the company. If this sequence can be of arbitrary length, then it is almost certain that everyone is "connected" to everyone else, even as n increases. –  analysisj Nov 11 '11 at 2:39
Not just "even as $n$ increases". It becomes more probable the higher $n$ is. If the company is already connected, then the probability that adding a new employee is disconnected is only $2^{-n}$. On the other hand if it is disconnected, then every new employee has a fair chance of randomly knowing people in more than one connected component, thus reducing the number of connected component. –  Henning Makholm Nov 11 '11 at 2:41

1 Answer 1

This particular case of Erdős–Rényi model was invented by Edgar Gilbert. In Erdős–Rényi model, the probability that two people know each other is $p_n$ instead of $.5$. Then the probability that the graph with $n$ vertices is connected goes to $1$ when $n\to\infty$ as soon as there exists $c\gt1$ such that $p_n\gt c\log(n)/n$. (And much more is known about the asymptotic behaviour of this random graph when $n\to\infty$.)

In particular (to answer specifically your question), the probability that the graph is connected goes to $1$ when $n\to\infty$ if $p_n$ is independent on $n$ and positive, for example if $p_n=.5$ for every $n$.

A simple proof in your case begins as follows. Call $c_n$ the probability that the graph on $n$ vertices is connected. If the graph on $n$ vertices is connected, adding another vertex and at least one edge between this new vertex and the $n$ others yields a connected graph on $n+1$ vertices. Adding no edge at all has probability $(1-p)^n$ hence $c_{n+1}\geqslant c_n(1-(1-p)^n)$.

This proves that $c_n\geqslant\gamma$ for every $n$, with $\gamma=\prod\limits_{n=1}^{+\infty}(1-(1-p)^n)$ and $\gamma\gt0$ for every $p\gt0$. In particular $c_n$ does not go to $0$. To prove that $c_n$ actually converges to $1$ requires some additional work.

share|improve this answer

Not the answer you're looking for? Browse other questions tagged or ask your own question.