wu :: forums - Print Page


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

        riddles >> medium >> "Erik's Puzzle" Probability
        
(Message started by: Eigenray on Jul 26^th, 2004, 3:46pm)

Title: "Erik's Puzzle" Probability
Post by Eigenray on Jul 26^th, 2004, 3:46pm

With the same rules as in "Erik's Puzzle" (Conway's Game of Life) (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_hard;action=display;num=1049135879):
"In a stripped-down version of Conway's game of life, cells are arranged on a square grid. Each cell is either alive or dead. Live cells do not die. Dead cells become alive if two or more of their immediate neighbours are alive. (Neighbours to north, south, east and west.)"

Start with an NxN grid of cells, each of which is randomly, independently, chosen to be alive with probability p.
Show that, for any fixed p > 0, the probability that the entire grid becomes alive goes to 1 as N [to] [infty].
[I saw this in this review (http://www.ams.org/notices/200302/fea-gray.pdf) of Wolfram's ANKS (beginning of page 10).]

Title: Re: "Erik's Puzzle" Probability
Post by Aryabhatta on Jul 27^th, 2004, 2:23am

The following argument seems to work,though I am not very sure as it is very late in the night :). I will hide this in case it turns out to be correct.

[]
[hide]

Given NxN grid and probability p > 0. Let q = 1-p.
Number the grid so that (1,1) is the top left corner.

Let us consider the probability that the square (1,1) is not alive after equilibrium. Now for (1,1) not to be alive, at least one its neighbours musn't have been alive to start with. Continuing this way I think we can show that for (1,1) not to be alive at least N cells should have been dead at the start.

So we have that the probability that (1,1) is dead after equilibrium is [le] q^N. We can show the same upper bound for cell (j,j) for any j [le] N.

Let A_i be the event that (i,i) is not alive after equilibrium. We have just shown that P(A_j) [le] q^N.

Let D = [cup]_{i = 1 to N}A_i.
(i.e. D is the event that at least one of the diagonal cells isn't alive at equilibrium)

Now P(D) [le] [sum]_{i= 1 to N}P(A_i) = [le] [sum]_{i = 1 to N}q^N = Nq^N

So P(D) [mapsto] 0 as N [mapsto] [infty]

This implies that with probability 1 all the cells in the diagonal will be alive, which implies that the whole grid will be alive with probability 1.
[/hide]
[]

Title: Re: "Erik's Puzzle" Probability
Post by Eigenray on Jul 27^th, 2004, 5:41am

Interesting approach... if it works, it would be simpler than the one I have.

on 07/27/04 at 02:23:41, Aryabhatta wrote:

Continuing this way I think we can show that for (1,1) not to be alive at least N cells should have been dead at the start.

So we have that the probability that (1,1) is dead after equilibrium is [le] q^N.

This you'd have to convince me of, because there are multiple ways to choose the cells that will start off dead.

Title: Re: "Erik's Puzzle" Probability
Post by Aryabhatta on Jul 27^th, 2004, 10:32am

on 07/27/04 at 05:41:06, Eigenray wrote:

... [le] q^N

This you'd have to convince me of, because there are multiple ways to choose the cells that will start off dead.

You are right!

I *should* get more sleep.

Maybe we can prove that the probability in question is [le] P(N)q^cN, where P(N) is a polynomial in N and c is some constant > 0. (my guess is c = 1/2)

Back to the board.

Title: Re: "Erik's Puzzle" Probability
Post by Aryabhatta on Jul 30^th, 2004, 11:31am

Ok. Here is another approach. I have a weird feeling about this one. So my guess is it might be wrong too. (I really need to read up on probability theory)

Let q = 1-p. We are looking at an nxn grid.
whp = with high probability means: probability [to] 1 as n [to] [infty].

Ok. Here is the basic idea. Suppose we can find a function f(n) such that f(n) [to] [infty] as n [to] [infty].

Now suppose we have a configuration with a live square of side f(n). Now the region R of f(n) side will not grow to fill the whole grid if at least one of the 'shells' around R contains a side with no live cells. The probabiltiy of this is [le] 4q^f(n) + 4q^f(n)+1 + ... + 4qⁿ = c(q^f(n) - qⁿ⁺¹) for some constant c.
So if we have a square R of side f(n), whp the region R will expand to fill the whole grid.

Now if we can show that whp we will always have a square of side f(n), then whp the whole grid will become alive.

let p = 1/M. (so M > 1)
Consider f(n) = logn (taken to the base M)
Consider the diagonals of the square.
For sufficiently large n we have at least nlogn disjoint segments of length log n.
Probability that at least one of the segments will be alive (ie. all the cells in that segment are alive) is 1 - (1 - p^logn)^nlogn.

Now (1 - p^logn)^nlogn = (1 - 1/n)^nlogn. Since (1-1/n)ⁿ tends to 1/e < 1, this sequence tends to 0.

Title: Re: "Erik's Puzzle" Probability
Post by Eigenray on Jul 30^th, 2004, 2:26pm

Well done. It looks good, except that you need to choose f(n) a bit smaller, because there are n/f(n) segments, not n*f(n).

A much more general result (http://www.math.ubc.ca/~holroyd/papers/boot.ps) is that the probability of the whole square becoming alive goes to 1 if liminf p log N > [lambda] = [pi]²/18, and goes to 0 if limsup p log N < [lambda] . . . but the proof is of course much harder.

Title: Re: "Erik's Puzzle" Probability
Post by Aryabhatta on Jul 30^th, 2004, 3:09pm

on 07/30/04 at 14:26:39, Eigenray wrote:

Well done. It looks good, except that you need to choose f(n) a bit smaller, because there are n/f(n) segments, not n*f(n).

If we consider all the possible diagonals with postive slope, we have at least Omega(n²/log n) disjoint segments of length which is at least Omega(nlogn) for sufficiently large n. No?

Quote:

A much more general result (http://www.math.ubc.ca/~holroyd/papers/boot.ps) is that the probability of the whole square becoming alive goes to 1 if liminf p log N > [lambda] = [pi]²/18, and goes to 0 if limsup p log N < [lambda] . . . but the proof is of course much harder.

Wow! I assume p is a function of n. What happens when the limit = [lambda]? is the probability 1/2 then? I would read the paper and try to find out, but it will probably take me days.

What proof did you have in mind for the fixed p case? If it is not a bother can you please post your solution?

Title: Re: "Erik's Puzzle" Probability
Post by Eigenray on Jul 30^th, 2004, 9:12pm

on 07/30/04 at 15:09:24, Aryabhatta wrote:

If we consider all the possible diagonals with postive slope, we have at least Omega(n²/log n) disjoint segments of length which is at least Omega(nlogn) for sufficiently large n. No?

Sorry, I misinterpreted what you were saying; I thought you were just talking about the main diagonal.

In my solution, I just broke up the square into (N/K)² KxK squares, and used basically the same argument. Except I had to choose N much bigger relative to K, because I was using lazier, weaker bounds on the probabilities.