Author |
Topic: deduction (Read 617 times) |
|
puzzlecracker
Senior Riddler
Men have become the tools of their tools
Gender: 
Posts: 319
|
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?
|
|
 IP Logged |
While we are postponing, life speeds by
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
 |
Re: deduction
« Reply #1 on: Feb 21st, 2005, 3:01pm » |
 Quote  Modify
|
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)?
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
JocK
Uberpuzzler
Gender:
Posts: 877
|
|
Re: deduction
« Reply #2 on: Feb 21st, 2005, 3:03pm » |
Quote Modify
|
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.
|
| « Last Edit: Feb 21st, 2005, 3:05pm by JocK » |
IP Logged |
solving abstract problems is like sex: it may occasionally have some practical use, but that is not why we do it.
xy - y = x5 - y4 - y3 = 20; x>0, y>0.
|
|
|
puzzlecracker
Senior Riddler
Men have become the tools of their tools
Gender:
Posts: 319
|
|
Re: deduction
« Reply #3 on: Feb 21st, 2005, 3:56pm » |
Quote Modify
|
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
|
|
IP Logged |
While we are postponing, life speeds by
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: deduction
« Reply #4 on: Feb 21st, 2005, 11:04pm » |
Quote Modify
|
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.. 
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
JocK
Uberpuzzler
Gender:
Posts: 877
|
|
Re: deduction
« Reply #5 on: Feb 22nd, 2005, 3:16pm » |
Quote Modify
|
on Feb 21st, 2005, 3:56pm, puzzlecracker wrote: 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 |
|
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.
|
|
IP Logged |
solving abstract problems is like sex: it may occasionally have some practical use, but that is not why we do it.
xy - y = x5 - y4 - y3 = 20; x>0, y>0.
|
|
|
puzzlecracker
Senior Riddler
Men have become the tools of their tools
Gender:
Posts: 319
|
|
Re: deduction
« Reply #6 on: Feb 22nd, 2005, 5:16pm » |
Quote Modify
|
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.
|
|
IP Logged |
While we are postponing, life speeds by
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: deduction
« Reply #7 on: Feb 22nd, 2005, 6:05pm » |
Quote Modify
|
on Feb 21st, 2005, 11:04pm, towr wrote:| I'm sure Icarus will make a stunning proof of the real answer any minute now.. |
|
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"! 
2) I only dabble in probability.
3) Of late, I've been more "stunned" than "stunning". 
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: deduction
« Reply #8 on: Feb 22nd, 2005, 9:41pm » |
Quote Modify
|
on Feb 21st, 2005, 11:04pm, 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-p2)n-2.
So the probability that there exist such x,y not connected is no more than
n2(1-p2)n-2,
which goes to 0 as n goes to infinity. Of course, tighter estimates are possible.
|
| « Last Edit: Feb 23rd, 2005, 6:06am by Eigenray » |
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: deduction
« Reply #9 on: Feb 23rd, 2005, 12:41am » |
Quote Modify
|
on Feb 22nd, 2005, 9:41pm, 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
|
| « Last Edit: Feb 23rd, 2005, 12:43am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Three Hands
Uberpuzzler
Gender:
Posts: 715
|
|
Re: deduction
« Reply #10 on: Feb 23rd, 2005, 6:09am » |
Quote Modify
|
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...
|
|
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: deduction
« Reply #11 on: Feb 23rd, 2005, 6:13am » |
Quote Modify
|
on Feb 23rd, 2005, 12:41am, 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).
|
| « Last Edit: Feb 23rd, 2005, 6:17am by Eigenray » |
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: deduction
« Reply #12 on: Feb 23rd, 2005, 6:24am » |
Quote Modify
|
on Feb 23rd, 2005, 6:09am, 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.
|
| « Last Edit: Feb 23rd, 2005, 6:25am by Eigenray » |
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: deduction
« Reply #13 on: Feb 23rd, 2005, 12:54pm » |
Quote Modify
|
on Feb 23rd, 2005, 6:13am, 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.
|
| « Last Edit: Feb 23rd, 2005, 12:57pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Three Hands
Uberpuzzler
Gender:
Posts: 715
|
|
Re: deduction
« Reply #14 on: Feb 24th, 2005, 10:06am » |
Quote Modify
|
on Feb 23rd, 2005, 6:24am, Eigenray wrote:
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. |
|
Meh. Thought it looked too easy...
Might take another run at this when my head's feeling a little clearer...
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: deduction
« Reply #15 on: Feb 24th, 2005, 10:28am » |
Quote Modify
|
on Feb 24th, 2005, 10:06am, 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.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print