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
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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