Author |
Topic: "Erik's Puzzle" Probability (Read 923 times) |
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender: 
Posts: 1948
|
 |
"Erik's Puzzle" Probability
« on: Jul 26th, 2004, 3:46pm » |
 Quote  Modify
|
With the same rules as in "Erik's Puzzle" (Conway's Game of Life):
"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 of Wolfram's ANKS (beginning of page 10).]
|
|
 IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: "Erik's Puzzle" Probability
« Reply #1 on: Jul 27th, 2004, 2:23am » |
Quote Modify
|
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.
[]
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] qN. We can show the same upper bound for cell (j,j) for any j [le] N.
Let Ai be the event that (i,i) is not alive after equilibrium. We have just shown that P(Aj) [le] qN.
Let D = [cup]i = 1 to N Ai.
(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(Ai) = [le] [sum]i = 1 to NqN = NqN
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.
[]
|
|
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: "Erik's Puzzle" Probability
« Reply #2 on: Jul 27th, 2004, 5:41am » |
Quote Modify
|
Interesting approach... if it works, it would be simpler than the one I have.
on Jul 27th, 2004, 2:23am, 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] qN. |
|
This you'd have to convince me of, because there are multiple ways to choose the cells that will start off dead.
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: "Erik's Puzzle" Probability
« Reply #3 on: Jul 27th, 2004, 10:32am » |
Quote Modify
|
on Jul 27th, 2004, 5:41am, Eigenray wrote:
... [le] qN
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)qcN, where P(N) is a polynomial in N and c is some constant > 0. (my guess is c = 1/2)
Back to the board.
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: "Erik's Puzzle" Probability
« Reply #4 on: Jul 30th, 2004, 11:31am » |
Quote Modify
|
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] 4qf(n) + 4qf(n)+1 + ... + 4qn = c(qf(n) - qn+1) 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 - plogn)nlogn.
Now (1 - plogn)nlogn = (1 - 1/n)nlogn. Since (1-1/n)n tends to 1/e < 1, this sequence tends to 0.
|
|
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: "Erik's Puzzle" Probability
« Reply #5 on: Jul 30th, 2004, 2:26pm » |
Quote Modify
|
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 is that the probability of the whole square becoming alive goes to 1 if liminf p log N > [lambda] = [pi]2/18, and goes to 0 if limsup p log N < [lambda] . . . but the proof is of course much harder.
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: "Erik's Puzzle" Probability
« Reply #6 on: Jul 30th, 2004, 3:09pm » |
Quote Modify
|
on Jul 30th, 2004, 2:26pm, 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(n2/log n) disjoint segments of length which is at least Omega(nlogn) for sufficiently large n. No?
Quote:
A much more general result is that the probability of the whole square becoming alive goes to 1 if liminf p log N > [lambda] = [pi]2/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?
|
|
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: "Erik's Puzzle" Probability
« Reply #7 on: Jul 30th, 2004, 9:12pm » |
Quote Modify
|
on Jul 30th, 2004, 3:09pm, Aryabhatta wrote:| If we consider all the possible diagonals with postive slope, we have at least Omega(n2/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)2 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.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print