wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> easy >> deduction
        
(Message started by: puzzlecracker on Feb 21^st, 2005, 12:41pm)

Title: deduction
Post by puzzlecracker on Feb 21^st, 2005, 12:41pm

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?

Title: Re: deduction
Post by Icarus on Feb 21^st, 2005, 3:01pm

By "connected", do you mean that "A is connected to Z if there is a sequence of people A, B, C, ..., Y, Z such that A knows B, B knows C, etc." (length of the chain is immaterial, as long as A and Z are the ends)?

Title: Re: deduction
Post by JocK on Feb 21^st, 2005, 3:03pm

If we don't know each other but you know someone I also know, we are connected? Well, in that case for large numbers of people the chance goes to unity.

Title: Re: deduction
Post by puzzlecracker on Feb 21^st, 2005, 3:56pm

Two people are connected if they know each other directly or through a chain friends who know each other.

EXAMPLE: If Bob knows Jim, Jim knows Lisa, and Lisa knows Jennie, then Bob, Jim, Lisa and Jennie are all connected

Title: Re: deduction
Post by towr on Feb 21^st, 2005, 11:04pm

The chance a given person is not connected is 1/2^(n-1)
The chance everyone is connected, disregarding dependence, is then (1-1/2^(n-1))^n (the real probability should be higher)
lim n -> [infty] (1-1/2^(n-1))^n = 1 I think..

I'm sure Icarus will make a stunning proof of the real answer any minute now.. :P

Title: Re: deduction
Post by JocK on Feb 22^nd, 2005, 3:16pm

on 02/21/05 at 15:56:32, puzzlecracker wrote:

OK, what I was hinting at is that a much stronger claim can be made:

1) The 'chain' can be limited to a chain of length one. (I.e. one can define two people to be 'connected' when they have at least one person in common they both know). Even in this case, for large groups of people the chance they are all connected approaches unity.

2) This even holds for any finite probability P that two persons (selected at random) know each other.

Title: Re: deduction
Post by puzzlecracker on Feb 22^nd, 2005, 5:16pm

intuitively it does approach one as limit goes to infinity

does anyone agree with my reply in 'truth' section... I don't know what came into me when I wrote. Unfortunately, I begin to agree with overrated claims.

Title: Re: deduction
Post by Icarus on Feb 22^nd, 2005, 6:05pm

on 02/21/05 at 23:04:02, towr wrote:

I'm sure Icarus will make a stunning proof of the real answer any minute now.. :P

1) You posted this at 1:04 AM my time, on a workday. The only reply I'm likely to make in minutes consists of only the letter "z"! :D

2) I only dabble in probability.

3) Of late, I've been more "stunned" than "stunning". :(

Title: Re: deduction
Post by Eigenray on Feb 22^nd, 2005, 9:41pm

on 02/21/05 at 23:04:02, towr wrote:

The chance a given person is not connected is 1/2^(n-1)

That doesn't appear to make any sense. What exactly does it mean for a given person to be connected?

Given two people x,y, they are in the same connected component if, in particular, there is some z such that x and y both know z. The probability that (x,y) are not connected is therefore no more than
(1-p²)^n-2.

So the probability that there exist such x,y not connected is no more than
n²(1-p²)^n-2,
which goes to 0 as n goes to infinity. Of course, tighter estimates are possible.

Title: Re: deduction
Post by towr on Feb 23^rd, 2005, 12:41am

on 02/22/05 at 21:41:42, Eigenray wrote:

That doesn't appear to make any sense. What exactly does it mean for a given person to be connected?

there are n people, so any one person can be connected to (n-1), so the probability he isn't (directly) linked to any of them is 1/2^(n-1)
Makes sense to me..

Quote:

Given two people x,y, they are in the same connected component if, in particular, there is some z such that x and y both know z.

There needn't be one person that links them both, it may be two, or three or any M < N-1

Title: Re: deduction
Post by Three Hands on Feb 23^rd, 2005, 6:09am

OK, given that the probability of any individual knowing another person in the company is 0.5:

n=1 - I assume the person is connected to themself...
n=2 - The probability that they know each other is 0.5
n=3 - A knows B = 0.5, A knows C = 0.5, B knows C = 0.5. Need any two of these to be true, so 4 out of the 8 equally likely possibilities produce complete connection, therefore probability of everyone connected = 0.5
n=4 - need 3 connections minimum for everyone connected, so for the 16 possibilities, 5 are successful, so the probability of everyone connected becomes 5/16...

In general, I'd put the probability of everyone being connected at (n+1)/(2^n), with the exception of n=2, but I may have missed something...

Title: Re: deduction
Post by Eigenray on Feb 23^rd, 2005, 6:13am

on 02/23/05 at 00:41:29, towr wrote:

there are n people, so any one person can be connected to (n-1), so the probability he isn't (directly) linked to any of them is 1/2^(n-1)
Makes sense to me..

I guess you're interpretting "everyone is connected" to mean there are no isolated vertices. I was taking it to mean the graph is connected.

Quote:

There needn't be one person that links them both, it may be two, or three or any M < N-1

Sure, but one person is sufficient for a lower bound on x,y being connected (upper bound on being disconnected).

Title: Re: deduction
Post by Eigenray on Feb 23^rd, 2005, 6:24am

on 02/23/05 at 06:09:10, Three Hands wrote:

n=4 - need 3 connections minimum for everyone connected, so for the 16 possibilities, 5 are successful, so the probability of everyone connected becomes 5/16...

For 4 people, there are 6 possible edges, so 64 possibilities. Count the configurations that don't work:
There is 1 with 0 edges, 6 with 1 edge, 15 = (6 choose 2) with 2 edges, and only 4 with 3 edges. The rest (64 - (1+6+15+4) = 38) work.
So the probability is 38/64.

Title: Re: deduction
Post by towr on Feb 23^rd, 2005, 12:54pm

on 02/23/05 at 06:13:41, Eigenray wrote:

I guess you're interpretting "everyone is connected" to mean there are no isolated vertices. I was taking it to mean the graph is connected.

No, that was just the first step.
For the graph to be connected, at the very least no vertex must be isolated. And then some.

Title: Re: deduction
Post by Three Hands on Feb 24^th, 2005, 10:06am

on 02/23/05 at 06:24:29, Eigenray wrote:

Meh. Thought it looked too easy...

Might take another run at this when my head's feeling a little clearer...

Title: Re: deduction
Post by Aryabhatta on Feb 24^th, 2005, 10:28am

on 02/24/05 at 10:06:15, Three Hands wrote:

Meh. Thought it looked too easy...

Might take another run at this when my head's feeling a little clearer...

Look at it this way. For p=1/2 every graph on n nodes is equally likely to occur. So just counting the fraction of graphs which are connected should give us the probabilty that a random graph formed by selecting edges with probability 1/2 is connected.