Consider the $\mathbb{Z}^2$-lattice and the $l^p$-Ball subgraph $\Lambda_r^p = (V_r^p, E_r^p)$ with $ V_r^p = \{v\in\mathbb{Z}^2 \colon \|v\|_p\leq r \}$ and $E_r^p = \{e = \{v,w\}\colon v,w \in V_r^p \text{ and } \|v-w\|_1 = 1\}$ ($1\leq p \leq \infty$, though the choice of $p$ should not be that important).
Now, let $(v_1,\ldots, v_R)$ be a random enumeration of $V_r$ (every such enumeration has probability $(R!)^{-1}$), and consider the sets
$$\Gamma_0 = \{(0,0)\}\,,\quad \Gamma_i =
\begin{cases}
\Gamma_{i-1} \cup \{v_i\} & \|v_i-w\|_1 = 1 \text{ for some }w\in \Gamma_{i-1}, \\
\Gamma_{i-1} & \text{else,}
\end{cases}$$
for $i=1,\ldots, R$.
The sets $\Gamma_i$ describe a growing cluster, and I am interested in the probability that $\Gamma_R$ contains a boundary node, i.e. a vertex in
$\partial V_r^p = \{v\in V_r^p \colon \|v-w\|_1 = 1 \text{ for some }w\in\mathbb{Z}^2 \setminus V_r^p\}$.
Question: Do constants $C,c>0$ exist such that $$\mathbb{P}[\Gamma_R \cap \partial V_r^p \neq \emptyset] \leq C\exp(-cr)\,? $$ Is this probability decaying even faster? I have the feeling that it should decay at least exponentially fast, and that $C,c$ can be chosen independently of $p$.
I think I found the answer myself. Let $v\in \partial V_r^p$ and consider the event $v\in \Gamma_R$. For this to happen, it is necessary that a path $v_{i(1)},\ldots, v_{i(n)}$ of adjacent vertices exists, where $v_{i(1)}$ is adjacent to the origin, $v_{i(n)}=v$ and $i(1)<\ldots<i(n)$. Call such a path $v$-path. The number of such paths of length $n$ can roughly be bounded by $4\cdot 3^{n-1}$ (selfavoiding paths starting at the 4 adjacent vertices to the origin, with $\leq 3$ choices at each crossing). The probability that for a fixed path, $i(1) < \ldots < i(n)$ happens is $(n!)^{-1}$. Therefore we get \begin{align*} \mathbb{P}[v\in \Gamma_R] & = & \mathbb{P}[\exists (v\text{-path})] \\ & \leq & \sum_n \sum_{(v\text{-paths}) \text{ of length }n} \frac{1}{n!} \\ & \leq & 4 \sum_{n=r}^\infty \frac{3^{n-1}}{n!}\,. \end{align*} The sum starts at $n=r$ because any $v$ on the boundary satisfies $\|v\|_1 \geq r$. This bound decays faster than any exponential function in $r$, i.e. we get $$\mathbb{P}[v\in\Gamma] \in \mathcal{O}(\exp(-cr)) $$ for any $c>0$. Because the number of boundary vertices grows linearly in $r$, we get $$ \mathbb{P}[\Gamma_R \cap \partial V_r^p \neq \emptyset] \in \mathcal{O}(\exp(-cr)) $$ for any $c>0$.
Please let me know in the comments if I made an obvious mistake.