Skip to main content
Bounty Ended with 50 reputation awarded by Y. Yang
Erroneously used wrong value of $\alpha$ previously (for self-avoiding walks instead of lattice animals)
Source Link
Ronnie Pavlov
  • 2.6k
  • 10
  • 15

So the following is a bit naive, but perhaps can be a starting point and an actual percolation theorist can do more.

The event you're considering is $E(n,p)$ = there exists a connected component $C$ containing the origin and some site on the boundary of $[-n,n]^2$ whose sum is positive. (This seems equivalent to your formulation since repeated visits don't count further towards score, and so for any connected component your walker can visit every site and the net score is just the sum of the numbers in $C$.

Clearly $E(n,p)$ is contained in the union over all such components $C$ of $E(C,p)$, the event that $C$ has positive sum. We can further simplify by just counting all connected components (often called lattice animals) containing the origin of size at least $k$, even though some of those won't touch the boundary. The number of those is roughly (up to a subexponential factor, which again won't matter) $\alpha^k$, where. Unfortunately I don't know how well $\alpha$ is bounded; I erroneously first thought it was the connectiveso-called connectivity constant ofon the square lattice (approx, which is known to a couple of decimals, but this constant I'm having more trouble searching for. A $2.64$(probably bad) bound is that $\alpha < 4.65$.

But for any $C$ of size $k$, this is just the event that a binomial RV with mean    $kp$ and variance $kp(1-p)$ is greater than $k/2$ (i.e. that more than half of the trials are successes/positive). The probability of this is asympotically something like

$P(X > k/2) \approx P(Z > \frac{k/2 - kp}{\sqrt{kp(1-p)}})$ for a standard normal $Z$. And this probability is (up to a polynomial, which won't matter)

$exp(-(\frac{k/2 - kp}{\sqrt{kp(1-p)}})^2/2) = exp(-\frac{k(1-2p)^2}{8p(1-p)})$.

So, we see that if $\frac{(1-2p)^2}{8p(1-p)} > \log \alpha$, then $P(E(C,p))$ will decay exponentially more quickly than $\alpha^k$, meaning that a union bound over all $C$ of size at least $k$ will give an exponentially decaying geometric series as an upper bound for $f(n,p) = P(E(n,p))$.

I was too lazy to exactly solve the quadratic, but graphing indicates that this happens when $p < .0938$$p < .065$ (using the $4.65$ upper bound for $\alpha$). So, it should be the case that your infimum is at least $.0938$. This is close enough to your calculations that it seems plausible; probably the game is solvable for $n = 200$ for smaller $p$ because of the polynomial factors that I ignored above$.065$.

Upper bounds for critical thresholds are traditionally much harder; again, probably a percolation theorist might see a good way to go here.

So the following is a bit naive, but perhaps can be a starting point and an actual percolation theorist can do more.

The event you're considering is $E(n,p)$ = there exists a connected component $C$ containing the origin and some site on the boundary of $[-n,n]^2$ whose sum is positive. (This seems equivalent to your formulation since repeated visits don't count further towards score, and so for any connected component your walker can visit every site and the net score is just the sum of the numbers in $C$.

Clearly $E(n,p)$ is contained in the union over all such components $C$ of $E(C,p)$, the event that $C$ has positive sum. We can further simplify by just counting all connected components containing the origin of size at least $k$, even though some of those won't touch the boundary. The number of those is roughly (up to a subexponential factor, which again won't matter) $\alpha^k$, where $\alpha$ is the connective constant of the square lattice (approx. $2.64$).

But for any $C$ of size $k$, this is just the event that a binomial RV with mean  $kp$ and variance $kp(1-p)$ is greater than $k/2$ (i.e. that more than half of the trials are successes/positive). The probability of this is asympotically something like

$P(X > k/2) \approx P(Z > \frac{k/2 - kp}{\sqrt{kp(1-p)}})$ for a standard normal $Z$. And this probability is (up to a polynomial, which won't matter)

$exp(-(\frac{k/2 - kp}{\sqrt{kp(1-p)}})^2/2) = exp(-\frac{k(1-2p)^2}{8p(1-p)})$.

So, we see that if $\frac{(1-2p)^2}{8p(1-p)} > \log \alpha$, then $P(E(C,p))$ will decay exponentially more quickly than $\alpha^k$, meaning that a union bound over all $C$ of size at least $k$ will give an exponentially decaying geometric series as an upper bound for $f(n,p) = P(E(n,p))$.

I was too lazy to exactly solve the quadratic, but graphing indicates that this happens when $p < .0938$. So, it should be the case that your infimum is at least $.0938$. This is close enough to your calculations that it seems plausible; probably the game is solvable for $n = 200$ for smaller $p$ because of the polynomial factors that I ignored above.

Upper bounds for critical thresholds are traditionally much harder; again, probably a percolation theorist might see a good way to go here.

So the following is a bit naive, but perhaps can be a starting point and an actual percolation theorist can do more.

The event you're considering is $E(n,p)$ = there exists a connected component $C$ containing the origin and some site on the boundary of $[-n,n]^2$ whose sum is positive. (This seems equivalent to your formulation since repeated visits don't count further towards score, and so for any connected component your walker can visit every site and the net score is just the sum of the numbers in $C$.

Clearly $E(n,p)$ is contained in the union over all such components $C$ of $E(C,p)$, the event that $C$ has positive sum. We can further simplify by just counting all connected components (often called lattice animals) containing the origin of size at least $k$, even though some of those won't touch the boundary. The number of those is roughly (up to a subexponential factor, which again won't matter) $\alpha^k$. Unfortunately I don't know how well $\alpha$ is bounded; I erroneously first thought it was the so-called connectivity constant on the square lattice, which is known to a couple of decimals, but this constant I'm having more trouble searching for. A (probably bad) bound is that $\alpha < 4.65$.

But for any $C$ of size $k$, this is just the event that a binomial RV with mean  $kp$ and variance $kp(1-p)$ is greater than $k/2$ (i.e. that more than half of the trials are successes/positive). The probability of this is asympotically something like

$P(X > k/2) \approx P(Z > \frac{k/2 - kp}{\sqrt{kp(1-p)}})$ for a standard normal $Z$. And this probability is (up to a polynomial, which won't matter)

$exp(-(\frac{k/2 - kp}{\sqrt{kp(1-p)}})^2/2) = exp(-\frac{k(1-2p)^2}{8p(1-p)})$.

So, we see that if $\frac{(1-2p)^2}{8p(1-p)} > \log \alpha$, then $P(E(C,p))$ will decay exponentially more quickly than $\alpha^k$, meaning that a union bound over all $C$ of size at least $k$ will give an exponentially decaying geometric series as an upper bound for $f(n,p) = P(E(n,p))$.

I was too lazy to exactly solve the quadratic, but graphing indicates that this happens when $p < .065$ (using the $4.65$ upper bound for $\alpha$). So, it should be the case that your infimum is at least $.065$.

Upper bounds for critical thresholds are traditionally much harder; again, probably a percolation theorist might see a good way to go here.

Source Link
Ronnie Pavlov
  • 2.6k
  • 10
  • 15

So the following is a bit naive, but perhaps can be a starting point and an actual percolation theorist can do more.

The event you're considering is $E(n,p)$ = there exists a connected component $C$ containing the origin and some site on the boundary of $[-n,n]^2$ whose sum is positive. (This seems equivalent to your formulation since repeated visits don't count further towards score, and so for any connected component your walker can visit every site and the net score is just the sum of the numbers in $C$.

Clearly $E(n,p)$ is contained in the union over all such components $C$ of $E(C,p)$, the event that $C$ has positive sum. We can further simplify by just counting all connected components containing the origin of size at least $k$, even though some of those won't touch the boundary. The number of those is roughly (up to a subexponential factor, which again won't matter) $\alpha^k$, where $\alpha$ is the connective constant of the square lattice (approx. $2.64$).

But for any $C$ of size $k$, this is just the event that a binomial RV with mean $kp$ and variance $kp(1-p)$ is greater than $k/2$ (i.e. that more than half of the trials are successes/positive). The probability of this is asympotically something like

$P(X > k/2) \approx P(Z > \frac{k/2 - kp}{\sqrt{kp(1-p)}})$ for a standard normal $Z$. And this probability is (up to a polynomial, which won't matter)

$exp(-(\frac{k/2 - kp}{\sqrt{kp(1-p)}})^2/2) = exp(-\frac{k(1-2p)^2}{8p(1-p)})$.

So, we see that if $\frac{(1-2p)^2}{8p(1-p)} > \log \alpha$, then $P(E(C,p))$ will decay exponentially more quickly than $\alpha^k$, meaning that a union bound over all $C$ of size at least $k$ will give an exponentially decaying geometric series as an upper bound for $f(n,p) = P(E(n,p))$.

I was too lazy to exactly solve the quadratic, but graphing indicates that this happens when $p < .0938$. So, it should be the case that your infimum is at least $.0938$. This is close enough to your calculations that it seems plausible; probably the game is solvable for $n = 200$ for smaller $p$ because of the polynomial factors that I ignored above.

Upper bounds for critical thresholds are traditionally much harder; again, probably a percolation theorist might see a good way to go here.