Author |
Topic: Random Graph Recursion (Read 4875 times) |
|
william wu
wu::riddles Administrator
Gender: 
Posts: 1291
|
 |
Random Graph Recursion
« on: Oct 17th, 2008, 9:55am » |
 Quote  Modify
|
Random Graph Recursion
================
We construct a graph with n nodes in the following manner:
- Between every pair of nodes, we flip a (biased) coin, and an edge will exist between them with probability p.
- Whether one edge exists is independent of whether another edge exists.
Let G(n,p) refer to the graph that is produced by this experiment. Let P(n) denote the probability that G(n,p) is connected.
1. Derive a recursion formula for P(n).
2. As n tends to infinity, what does P(n) converge to?
|
|
 IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Random Graph Recursion
« Reply #1 on: Oct 17th, 2008, 2:47pm » |
Quote Modify
|
1:
P(1)=1
P(k+l) = P(k)*P(l)*(1 - (1-p)k*l)
i.e. it's connected if when dividing the graph into two parts, the two parts are internally connected, and there isn't no interconnection between the two parts (mind the double negation there).
2:
I'm guessing 1, 0 or e 
|
| « Last Edit: Oct 17th, 2008, 2:48pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
teekyman
Full Member
Gender:
Posts: 199
|
|
Re: Random Graph Recursion
« Reply #2 on: Oct 17th, 2008, 3:01pm » |
Quote Modify
|
for 1: There are ways that neither of the two halves is connected but whole graph is.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Random Graph Recursion
« Reply #3 on: Oct 17th, 2008, 3:12pm » |
Quote Modify
|
on Oct 17th, 2008, 3:01pm, 1337b4k4 wrote:| for 1: There are ways that neither of the two halves is connected but whole graph is. |
|
Damn, you're right.
Still, it must be true that you can divide it in two halves that are both connected.
I suppose the solution is to just not take large steps, and take l=1; it almost looks like a 1 anyway.
[edit]Hmm, that doesn't quite solve it either, does it? If at one point it's disconnected, it may get reconnected again later on.[/edit]
|
| « Last Edit: Oct 17th, 2008, 3:14pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: Random Graph Recursion
« Reply #4 on: Oct 18th, 2008, 5:02pm » |
Quote Modify
|
Yes, the problem seems to be more complicated ... I don't thing there is a simple recursion, but I would happily look at it if anybody finds one.
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Random Graph Recursion
« Reply #5 on: Oct 19th, 2008, 3:08am » |
Quote Modify
|
on Oct 17th, 2008, 2:47pm, towr wrote:| I'm guessing 1, 0 or e |
|
I bet the probability won't be e. 
OK, I computed the probabilities by hand up to 5 nodes:
1: 1
2: 1/2 = 0.5
3: 1/2 = 0.5
4: 19/32 = 0.5937
5: 91/128 = 0.7109
I then wrote a program (montecarlo method) that confirmed these values.
I ran it up to size 20 and I got.
n=20: 0.999960
|
|
IP Logged |
|
|
|
william wu
wu::riddles Administrator
Gender:
Posts: 1291
|
|
Re: Random Graph Recursion
« Reply #6 on: Oct 19th, 2008, 5:41am » |
Quote Modify
|
Some hints for developing the recursion:
| hidden: |
1. To develop a recursion, it may be easier to consider the complementary probability.
2. The recursion writes P(n) in terms of all past values P(1), P(2), ..., P(n-1).
|
|
| « Last Edit: Oct 19th, 2008, 5:41am by william wu » |
IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Random Graph Recursion
« Reply #7 on: Oct 19th, 2008, 9:25am » |
Quote Modify
|
A deterministic computation in C gives
6: 1669/2048 = 0.814941
7: 116641/131072 = 0.8899002075
8: 15721787/16777216 = 0.9370915294
|
| « Last Edit: Oct 19th, 2008, 2:40pm by Grimbal » |
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: Random Graph Recursion
« Reply #8 on: Oct 20th, 2008, 12:44am » |
Quote Modify
|
Grimbal: Did you also think about the original problem with p 1/2? I am sure (for n  ) the graf G(n,0) would not be connected. What is the treshold p the probability of G(n,p) beeing connected is above 0 and under 1?
|
| « Last Edit: Oct 20th, 2008, 12:46am by Hippo » |
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Random Graph Recursion
« Reply #10 on: Oct 20th, 2008, 4:57am » |
Quote Modify
|
I did not investigate p!=1/2 or a p that varies with n. Indeed, if p = 1/n, we might end up with something like 1/e.
|
|
IP Logged |
|
|
|
william wu
wu::riddles Administrator
Gender:
Posts: 1291
|
|
Re: Random Graph Recursion
« Reply #11 on: Oct 20th, 2008, 10:40am » |
Quote Modify
|
OK another hint
| hidden: |
Write 1 - P(n) in terms of P(1), P(2), ...., P(n-1). That is, write the probability of the size n graph being disconnected in terms of the probabilities of smaller graphs being connected. Think combinatorially about it.
|
|
|
IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: Random Graph Recursion
« Reply #12 on: Oct 20th, 2008, 12:34pm » |
Quote Modify
|
The probability to have a graph consisitng of components of sizes s1,s2,...,sk can be expressed using P(i), but summing that together would be very complicated.... (s1+s2+ + sk)!/(s1!s2!sk!)P(s1)P(s2)P(sk) ... if s1<s2<<sk.
In case of size equivalences, we should further divide it by permutation of the components ...
Let the sizes are s1<s2<<sk and let the size si appears ki times. ...
We get (s1k1+s2k2++skkk)!/((s1!)k1k1!(s2!)k2k2!(sk!)kkkk!)P(s1)k1P(s2)k2P(sk)kk.
[edit] Noone complains  , but the factor (1-p)E should be part of the expression, where E is the number of pairs of vertices from different components.[/edit]
|
| « Last Edit: Oct 23rd, 2008, 10:52pm by Hippo » |
IP Logged |
|
|
|
william wu
wu::riddles Administrator
Gender:
Posts: 1291
|
|
Re: Random Graph Recursion
« Reply #13 on: Oct 27th, 2008, 11:28am » |
Quote Modify
|
on Oct 20th, 2008, 12:34pm, Hippo wrote:| The probability to have a graph consisitng of components of sizes s1,s2,...,sk can be expressed using P(i), but summing that together would be very complicated.... |
|
Hint:
| hidden: |
Pick a certain vertex; call it v. Rather than thinking about all the possible mixtures of components, we will consider only the component that v resides in. Suggestion is to write 1-P(n), the probability of being disconnected, in terms of {P(i) : i < n}. How can a disconnected graph look like from the perspective of v?
|
|
|
IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
Taking the hint, I made an animated gif showing the graphs of P(1), ..., P(50).
|
| « Last Edit: Oct 27th, 2008, 2:34pm by Eigenray » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print