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

        riddles >> hard >> Random Graph Recursion
        
(Message started by: william wu on Oct 17th, 2008, 9:55am)
Title: Random Graph Recursion
Post by william wu on Oct 17th, 2008, 9:55am
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?
Title: Re: Random Graph Recursion
Post by towr on Oct 17th, 2008, 2:47pm
1:
[hide]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).
[/hide]

2:
[hide]I'm guessing 1, 0 or e [/hide] ;)
Title: Re: Random Graph Recursion
Post by 1337b4k4 on Oct 17th, 2008, 3:01pm
for 1: There are ways that neither of the two halves is connected but whole graph is.
Title: Re: Random Graph Recursion
Post by towr on Oct 17th, 2008, 3:12pm

on 10/17/08 at 15:01:25, 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]
Title: Re: Random Graph Recursion
Post by Hippo on Oct 18th, 2008, 5:02pm
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.
Title: Re: Random Graph Recursion
Post by Grimbal on Oct 19th, 2008, 3:08am

on 10/17/08 at 14:47:35, towr wrote:
[hide]I'm guessing 1, 0 or e [/hide] ;)

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.
[hide]n=20: 0.999960[/hide]
Title: Re: Random Graph Recursion
Post by william wu on Oct 19th, 2008, 5:41am
Some hints for developing the recursion:
[hideb]
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).
[/hideb]
Title: Re: Random Graph Recursion
Post by Grimbal on Oct 19th, 2008, 9:25am
A deterministic computation in C gives
  6: 1669/2048 = 0.814941
  7: 116641/131072 = 0.8899002075
  8: 15721787/16777216 = 0.9370915294
Title: Re: Random Graph Recursion
Post by Hippo on Oct 20th, 2008, 12:44am
Grimbal: Did you also think about the original problem with phttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ne.gif1/2? I am sure (for nhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/to.gifhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/infty.gif) 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?
Title: Re: Random Graph Recursion
Post by towr on Oct 20th, 2008, 2:17am
For p=1/2, we can use
http://www.research.att.com/~njas/sequences/A001187
divided by 2n*(n-1)/2, I think.
Title: Re: Random Graph Recursion
Post by Grimbal on Oct 20th, 2008, 4:57am
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.
Title: Re: Random Graph Recursion
Post by william wu on Oct 20th, 2008, 10:40am
OK another hint  ;)
[hideb]
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.
[/hideb]
Title: Re: Random Graph Recursion
Post by Hippo on Oct 20th, 2008, 12:34pm
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+http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/cdot.gifhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/cdot.gifhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/cdot.gif+ sk)!/(s1!http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/cdot.gifs2!http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/cdot.gifhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/cdot.gifhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/cdot.gifsk!)P(s1)http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/cdot.gifP(s2)http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/cdot.gifhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/cdot.gifhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/cdot.gifP(sk) ... if s1<s2<http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/cdot.gifhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/cdot.gifhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/cdot.gif<sk.
In case of size equivalences, we should further divide it by permutation of the components ...
Let the sizes are s1<s2<http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/cdot.gifhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/cdot.gifhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/cdot.gif<sk and let the size si appears ki times. ...
We get (s1http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/cdot.gifk1+s2http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/cdot.gifk2+http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/cdot.gifhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/cdot.gifhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/cdot.gif+skhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/cdot.gifkk)!/((s1!)k1k1!http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/cdot.gif(s2!)k2k2!http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/cdot.gifhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/cdot.gifhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/cdot.gif(sk!)kkkk!)P(s1)k1http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/cdot.gifP(s2)k2http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/cdot.gifhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/cdot.gifhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/cdot.gifP(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]
Title: Re: Random Graph Recursion
Post by william wu on Oct 27th, 2008, 11:28am

on 10/20/08 at 12:34:50, 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:
[hideb]
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?
[/hideb]
Title: Re: Random Graph Recursion
Post by Eigenray on Oct 27th, 2008, 2:31pm
Taking the hint, I made an animated gif showing the graphs of P(1), ..., P(50).


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board