What's the minimum ratio of positive cells such that the player has a positive probability to reach the boundary of a large random map?

Question

A map with $(2n-1)$ rows and $(2n-1)$ columns of square cells is generated randomly as follows: the value of each cell is chosen from {1, -1} randomly and independently with probability {$p$, $1-p$}. The starting position of the player is at the center (i.e. at the $n$th row and the $n$th column) of the map. For each step, the player can choose a cell next to him (i.e. choose one of the four neighbour cells) and go there. Once the player goes to a new cell with value 1 (resp. -1), the score of the game will increase (resp. decrease) by 1. If the player goes to a cell that has already been visited before, then the score does not change. The initial score is 0 and the goal of the game is to reach the boundary of the map with a positive score. For the above setting, the probability that there exists a strategy to achieve the goal of the game is denoted as $f(n,p)$.

Q1: What's the infimum of $p$ such that $\lim_{n\rightarrow\infty}f(n,p)>0$?

A quick answer is $0.089\pm0.002$ because I played the game and achieved the goal of the game for $n=200,p=1/11$ but unable to achieve the goal for $n=200,p=2/23$. I need some references for a more acurate answer.

Q2: If the value of each cell is chosen from {1, $-x$} instead and the other conditions remains the same, then the answer of Q1 is a function of $x$ (denoted as $p(x)$) instead. Have anyone found the function $p(x)$ till now?

A quick answer for $x\rightarrow\infty$ is $p(\infty)=0.592746050792...$ because this case is a percolation problem and have been solved by many researchers. But I haven't got the answer for a finite $x$ yet. Is there any references for this problem?

Answer 1

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.