%~Mouliné par MaN_auto v.0.34.0 (b0f8651d) 2025-06-24 17:00:25
\documentclass[CRMATH,Unicode,biblatex]{cedram}

\TopicFR{Probabilités}
\TopicEN{Probability theory}

\addbibresource{CRMATH_Nachmias_20250181.bib}

\usepackage[capitalize]{cleveref}
\usepackage{mathtools}

\DeclareMathOperator{\E}{\mathbb{E}}

\newcommand{\R}{\mathbb{R}}
\renewcommand{\P}{\mathbb{P}}
\newcommand{\DD}{\mathbb{D}}
\newcommand{\RR}{\mathbb{R}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\HH}{\mathbb{H}}

\newcommand{\pot}{\Psi}

\renewcommand{\o}{o}

\newcommand{\G}{{\sf G}}
\newcommand{\g}{{\sf g}}

%%%---------------------------------------------------------------------------

%%% ARROWS

%%% \to
\renewcommand*{\to}{\mathchoice{\longrightarrow}{\rightarrow}{\rightarrow}{\rightarrow}}
%% Remplacer \xrightarrow{#1} par \overset{#1}{\longrightarrow}. 

%%% \mapsto
\let\oldmapsto\mapsto
\renewcommand*{\mapsto}{\mathchoice{\longmapsto}{\oldmapsto}{\oldmapsto}{\oldmapsto}}

%%%---------------------------------------------------------------------------

%%% DELIMITERS

%\usepackage{mathtools}
\DeclarePairedDelimiter{\parens}{\lparen}{\rparen}
\DeclarePairedDelimiter{\braces}{\{}{\}}
\DeclarePairedDelimiter{\abs}{\lvert}{\rvert}
\DeclarePairedDelimiter{\bracks}{[}{]}

%%%---------------------------------------------------------------------------

%%% PACKAGE CLEVEREF
%%% English

%\usepackage[english,capitalize,nameinlink]{cleveref}
\newcommand*\claimref[1]{\hyperref[#1]{Claim~\ref*{#1}}}
\newcommand*\conjref[1]{\hyperref[#1]{Conjecture~\ref*{#1}}}
\newcommand*\cororef[1]{\hyperref[#1]{Corollary~\ref*{#1}}}
\newcommand*\defiref[1]{\hyperref[#1]{Definition~\ref*{#1}}}
\newcommand*\figureref[1]{\hyperref[#1]{Figure~\ref*{#1}}}
\newcommand*\lemmref[1]{\hyperref[#1]{Lemma~\ref*{#1}}}
\newcommand*\propref[1]{\hyperref[#1]{Proposition~\ref*{#1}}}
\newcommand*\subsectionref[1]{\hyperref[#1]{Section~\ref*{#1}}}
\newcommand*\theoref[1]{\hyperref[#1]{Theorem~\ref*{#1}}}
\newcommand*\remaref[1]{\hyperref[#1]{Remark~\ref*{#1}}}

%%%---------------------------------------------------------------------------

%%% VERTICAL BAR

\newcommand*{\cond}[1][]{\,#1\vert\,}

%%%---------------------------------------------------------------------------

\graphicspath{{./figures/}}

\newcommand*{\mk}{\mkern -1mu}
\newcommand*{\Mk}{\mkern -2mu}
\newcommand*{\mK}{\mkern 1mu}
\newcommand*{\MK}{\mkern 2mu}

\hypersetup{urlcolor=purple, linkcolor=blue, citecolor=red}

\newcommand*{\relabel}{\renewcommand{\labelenumi}{(\theenumi)}}
\newcommand*{\romanenumi}{\renewcommand*{\theenumi}{\roman{enumi}}\relabel}
\newcommand*{\Romanenumi}{\renewcommand*{\theenumi}{\Roman{enumi}}\relabel}
\newcommand*{\alphenumi}{\renewcommand*{\theenumi}{\alph{enumi}}\relabel}
\newcommand*{\Alphenumi}{\renewcommand*{\theenumi}{\Alph{enumi}}\relabel}
\let\oldhat\hat
\renewcommand*{\hat}[1]{\mathchoice{\widehat{#1}}{\widehat{#1}}{\oldhat{#1}}{\oldhat{#1}}}
\let\oldexists\exists
\renewcommand*{\exists}{\mathrel{\oldexists}}
\let\oldforall\forall
\renewcommand*{\forall}{\mathrel{\oldforall}}

\title{Every recurrent network has a potential tending to infinity}
\alttitle{Tout réseau récurrent a un potentiel tendant vers l'infini}

\author{\firstname{Asaf} \lastname{Nachmias}}
\address{Department of Mathematical Sciences, Tel Aviv University, Israel}
\email{asafnach@tauex.tau.ac.il}

\author{\firstname{Yuval} \lastname{Peres}}
\address{Beijing Institute of Mathematical Sciences and Applications, Beijing, China}
\email{yperes@gmail.com}

\thanks{This work was supported by ERC consolidator grant~101001124 (UniversalMap) as well as ISF grants~1294/19 and~898/23}
\CDRGrant[ERC]{101001124}
\CDRGrant[ISF]{1294/19}
\CDRGrant[ISF]{898/23}

\begin{abstract}
A rooted network consists of a connected, locally finite graph $G$, equipped with edge conductances and a distinguished vertex $o$. A nonnegative function on the vertices of $G$ which vanishes at $o$, has Laplacian~$1$ at $o$, and is harmonic at all other vertices is called a potential. We prove that every infinite recurrent rooted network admits a potential tending to infinity. This is an analogue of classical theorems due to Evans and Nakai in the settings of Euclidean domains and Riemannian surfaces.
\end{abstract}

\begin{altabstract}
Un réseau enraciné est un graphe $G$ localement fini et connexe, doté de conductances sur les arêtes et d'un sommet distingué $o$. Un potentiel est une fonction sur les sommets de $G$ qui est positive, s'annule en $o$, a un laplacien $1$ en $o$ et est harmonique en tous les autres sommets. Nous prouvons que tout réseau enraciné, récurrent et infini admet un potentiel tendant vers l'infini. Il s'agit d'un analogue de théorèmes classiques de Evans et Nakai dans le cadre des domaines euclidiens et des surfaces riemanniennes.
\end{altabstract}

\begin{document}

\maketitle

\section{Introduction}\label{sec:intro}

A \emph{rooted network} $(G,c,\o) $ consists of a connected, locally finite graph $G=(V,E)$, endowed with positive edge weights $c \colon E\to (0,\infty)$ and a distinguished vertex $\o \in V$. The corresponding \emph{network random walk} with transition probabilities $p(x,y)=c_{xy}/c_x$ is reversible, with reversing measure $c_x=\sum_{z\sim x}c_{xz}$. Define the network \emph{Laplacian} of a function $f \colon V\to\RR$ by
\[
\Delta f (v) = \sum_{x \sim v} c_{vx} \parens[\big]{f(x) - f(v)}.
\]

A \emph{potential} on $(G,c,\o)$ is a function $h \colon V\to [0,\infty)$ that is harmonic off $\o$ (i.e., $\Delta h(v) = 0$ for every vertex $v\neq \o$), normalized so that $h(\o)=0$ and $\Delta h(\o) =1$. In every infinite rooted network there is at least one potential, see \claimref{claim:compact}. Our focus is on recurrent networks.

We say that a function $h \colon V\to [0,\infty)$ \emph{tends to infinity} and write $h\to \infty$, if for all $M>0$ the set $\braces[\big]{v \in V : h(v) \leq M}$ is finite. Observe that on $\Z$, the potentials $h_1(n)=\max(n,0)$ for $n\in \Z$ and $h_2(n)=\max(-n, 0)$ do \emph{not} tend to infinity, but any non-trivial convex combination of them does. On $\Z^2$, on the other hand, it is well known that there is a unique potential $h$ with $h(v) = \Theta\parens[\big]{\log \abs{v}}$ as $v \to \infty$, see~\cite[Sections~12 and~31]{Spitzer}. Recently there has been renewed interest in recurrent potential theory, motivated by close connections to unimodular random networks and uniform spanning trees in work of Berestycki, van Engelenburg and Hutchcroft, see~\cite{BereEngel,EngelHutch}.

\begin{theo}\label{conj:main}
On any infinite recurrent rooted network there exists a potential which tends to infinity.
\end{theo}

The earliest theorem of this type is due to G.~C.~Evans~\cite{Evans36} who showed that every compact polar set $K$ in $\R^d$ supports a probability measure such that its Newtonian potential is infinite on $K$. Using Evans' approach, Nakai~\cite{Nakai62} proved that every parabolic noncompact Riemannian surface admits a function which is harmonic off a compact set and tends to infinity (i.e., its level sets are compact). In Nakai's proof, the set $K$ is replaced by the Stone--{\v Cech} boundary of the surface. Nakai's argument can be adapted to prove \theoref{conj:main}, but the use of the Stone--{\v Cech} compactification makes this argument non-constructive. Here we present a more constructive probabilistic approach, using the minimax theorem.

\begin{rema}
\theoref{conj:main} implies that if a rooted network admits a unique potential, then it must tend to infinity. This answers a question raised following~\cite[Proposition~5.1]{BereEngel}.
\end{rema}

\begin{rema}
It is well known that the existence of a potential tending to infinity implies recurrence. Indeed, let $h$ be a potential, let $\{X_t\}$ be the network random walk and consider the hitting time $\tau_\o=\min\braces[\big]{ n \geq 0 : X_n = \o}$. Then $h(X_{n\wedge \tau_\o})$ is a nonnegative martingale, whence it almost surely converges; this contradicts transience if $h\to \infty$.
\end{rema}

\vspace{-.75\baselineskip}

\section{Preliminaries}

\vspace{-.2\baselineskip}

\subsection{Dipoles and potentials}

The \emph{Green kernel}\/ $\G_\o(x,y)$ of the random walk $\{X_n\}_{n \geq 0}$ killed at $\o$ is defined by
\[
\G_\o(x,y) \coloneqq \sum_{n=0}^\infty \P_x \parens[\big]{X_n = y, \,\, \tau_\o > n}.
\]
The corresponding \emph{Green density},
\[
\g_\o (x,y) = \frac{\G_\o(x,y)}{c_y},
\]
is symmetric by reversibility. A \emph{dipole} from $\o$ to another vertex $y$ in a network $(G,c)$ is a function $f \colon V\to [0,\infty)$, for which $f(\o)=0$ and
\[
\forall v \in V \quad \Delta f (v) = \boldsymbol{1}_\o(v) - \boldsymbol{1}_y(v).
\]

\begin{enonce}{Claim}\label{claim:GreenIsDipole}
In a recurrent network, the Green density $g_\o(\,\cdot\,,y)$ for the killed random walk is a dipole from $\o$ to $y$. Moreover, $\sup_y g_\o(x,y)<\infty$ for each $x \in V$.
\end{enonce}
\begin{proof}
First observe that $g_\o(\,\cdot\,,y)$ is harmonic off $\{\o,y\}$ and satisfies $\g_\o(\o, y)=0$. Second, $\Delta \g_\o(\,\cdot\,,y) (y) =-1$, since
\begin{equation}\label{eq:laplace-y}
\sum_{x \sim y} c_{xy} \parens[\big]{\g_\o(y,y)-\g_\o(x,y)} = \G_\o(y,y) - \sum_{x \sim y} \frac{c_{xy}}{c_y} \G_\o(x,y) = 1.
\end{equation}
Also,
\begin{equation} \label{eq:dipole11}
\Delta \g_\o(\,\cdot\,,y)(\o) = \sum_{x\sim \o} c_{\o x} g_\o(x,y)= \sum_{x\sim \o} \G_o(y,x) \frac{c_{\o x}}{c_x} =1,
\end{equation} where the last equality is obtained by summing, over $n \ge 0$, the identity
\[
\sum_{x\sim \o} \P_y\parens[\big]{X_{n} = x, \ \tau_\o > n}\frac{c_{\o x}}{c_x} = \P_y \parens[\big]{X_{n+1} = \o, \ \tau_\o > n} = \P_y(\tau_\o =n+1) 
\]
and using recurrence. Thus, $g_\o(\,\cdot\,,y)$ is a dipole.

\goodbreak

Lastly, the identity~\eqref{eq:dipole11} implies that $\g_\o(x,y) \le c_{ox}^{-1}$ for every $x \sim \o$. More generally, since $\g_\o(\,\cdot\,,y)$ is superharmonic off $\o$, for any $x \ne \o$ we have $\g_\o(x,y) \le \prod_{i=1}^\ell c_{x_{i-1}x_i}^{-1}$, where $x_0,\dotsc,x_\ell$ is a simple path from $\o$ to $x$.
\end{proof}

\begin{enonce}{Claim}\label{claim:compact}
The space of potentials on a recurrent infinite rooted $(G,c,\o)$ is a nonempty, compact, convex subset of\/ $\R^V$ endowed with the product topology.
\end{enonce}
\begin{proof}
By \claimref{claim:GreenIsDipole}, for any sequence of vertices $y_n\to \infty$, Cantor diagonalization yields a subsequential pointwise limit of $\g_\o(\,\cdot\,, y_n)$, and any such limit is a potential. Next, for any potential $h$ we have $h(x)\leq \prod_{i=1}^\ell c_{x_{i-1}x_i}^{-1}$, where $x_0,\dotsc,x_\ell$ is a simple path from $\o$ to $x$, by the argument in the proof of \claimref{claim:GreenIsDipole}, so the set of potentials is a closed subset of a compact product space. Finally, convexity is obvious.
\end{proof}

\subsection{The Doob transform determined by a potential}

Any potential $h$ defines a Markov chain on the state space $S_h = \braces[\big]{v : h(v)>0}$ via the Doob $h$-transform that has transition probabilities
\[
p^h(x,y) = \frac{p(x,y) h(y)}{h(x)}.
\]
The corresponding Markov chain $\{Y_n\}_{n \geq 0}$ is called the \emph{$h$-process}. Write $\P^h_\mu$ for the law of the $h$-process with initial distribution $\mu$ and $\E^h_\mu$ for the corresponding expectation.

For any finite sequence $\gamma=(\gamma_1,\dotsc,\gamma_k)$ in $V$, we write $\P_{\gamma_1}(\gamma)\coloneqq \prod_{i=2}^k p(\gamma_{i-1},\gamma_i).$ If $\gamma$ is contained in $S_h$, we define $\P^h_{\gamma_1}(\gamma)$ similarly using $p^h(\gamma_{i-1},\gamma_i)$. We have the telescoping product
\begin{equation} \label{eq:hprocessvsSRWSimple}
\P^h_{\gamma_1}(\gamma) = \P_{\gamma_1}(\gamma) \frac{h(\gamma_k)}{h(\gamma_1)}.
\end{equation}
We will use the initial distribution $\mu_h$ defined by
\begin{equation}\label{def:mu}
\mu_h(v) = c_{\o v} h(v) \quad \text{for all} \ v \sim \o.
\end{equation} Observe that
\begin{equation} \label{eq:hprocessvsSRW}
\P^h_{\mu_h} (\gamma) = c_{\o \gamma_1} h(\gamma_1) \P^h_{\gamma_1}(\gamma) = c_{\o \gamma_1} \P_{\gamma_1}(\gamma) h(\gamma_k) = c_\o \P_\o(\o\gamma) h(\gamma_k).
\end{equation}

There is a standard relation between the Green kernels of the $h$-process and the network random walk killed at $\o$.

\begin{enonce}
{Claim} \label{claim:GhMu}
Let $h$ be a potential on a recurrent rooted network $(G,c,\o)$. Then the $h$-process $\{Y_n\}_{n \geq 0}$ is transient. Moreover, its Green kernel\/ $\G^h(x,y)=\sum_{k \geq 0} \P^h_x(Y_k = y) $, defined for $x,y\in S_h$, satisfies
\begin{equation}\label{eq:XvsY}
\G^h(x,y) = \G_\o(x,y) \frac{h(y)}{h(x)},\end{equation} and for all $v\in S_h$
\begin{equation}\label{eq:Gh}
\G^h({\mu_h},v) = h(v) c_v,\end{equation} where\/ $\G^h({\mu},v)\coloneqq \sum_x \mu(x) \G^h(x,v)$.
\end{enonce}

\begin{proof}
Transience will follow once we show $G^h(x,y)<\infty$. To prove~\eqref{eq:XvsY}, we sum~\eqref{eq:hprocessvsSRWSimple} over all paths from $x$ to $y$ that avoid $\o$. Note that by harmonicity of $h$ off $\o$, any such path is contained in $S_h$. Next, \eqref{eq:Gh} follows from~\eqref{eq:XvsY} by
\[
\G^h({\mu_h},y) =\sum_v c_{\o v} h(v) \G^h(v,y) = h(y) \sum_v c_{\o v} \G_\o(v,y) = h(y) c_y,
\]
using~\eqref{eq:dipole11} and the symmetry of $\g_\o(\,\cdot\,,\cdot\,)$ in the last step.
\end{proof}

\begin{enonce}{Claim}\label{lem:hProcessInfty}
Let $h$ be a potential for a recurrent rooted network $(G,c,\o)$ and consider the $h$-pro\-cess~$\{Y_n\}$ started at $v \in S_h$. Then for every $M >0$,
\[
\P^h_v \parens[\big]{h(Y_\ell) >M} \to 1 \quad \text{as} \ \ell \rightarrow \infty.
\]
\end{enonce}

This was also observed in~\cite[Lemma~5]{EngelHutch}.
\begin{proof}
Recall that $\{X_n\}$ is the network random walk. By~\eqref{eq:hprocessvsSRWSimple}, we have
\[
\P_v^h\parens[\big]{h(Y_\ell) \le M} = \E_v\bracks[\Bigg]{\frac{h(X_\ell)}{h(v)} \, \boldsymbol{1}_{\{h(X_\ell) \le M \ \text{and} \ \tau_\o \ge \ell\}}} \le \frac{M}{h(v)} \, \P_v(\tau_\o \ge \ell),
\]
which tends to $0$ as $\ell \rightarrow \infty$ by recurrence.
\end{proof}

\section{Proof of main theorem}\label{sec:MainProof}

Let $d(\,\cdot\,,\cdot\,)$ denote graph distance. For any integer $r>0$, we set
\[
B(\o,r) = \braces[\big]{ w: d(\o,w) < r} \qquad \text{and} \qquad \partial B(\o,r) = \braces[\big]{ w : d(\o,w)=r},
\]
Next we state a formally weaker version of \theoref{conj:main}, where we can choose a different potential for each radius, and show that it implies the theorem.

\begin{lemm}\label{lem:key}
Let $\pot$ be the set of potentials on a recurrent infinite rooted network $(G,c,\o)$. Then
\begin{equation}\label{eq:keylem}
M(r)\coloneqq \max_{\psi \in \pot} \min_{v \in \partial B(\o,r)} \psi(v) \to \infty \quad \text{as} \ r \rightarrow \infty.
\end{equation}
\end{lemm}

\begin{rema}\label{remark:MR}
For every integer $r>0$ and $\psi\in\pot$, the minimum of $\psi$ on $V \setminus B(\o,r)$ is attained on $\partial B(\o,r)$. Indeed, let $\{X_t\}$ be the network random walk started at $w \not \in B(\o,r)$ and let $\tau_r$ be the hitting time of $\partial B(\o,r)$. Then $\psi(X_{t\wedge \tau_r})$ is a positive martingale, so by recurrence and optional stopping,
\[
\psi(w) \geq \E_w \bracks[\big]{\psi(X_{\tau_r})} \geq \min_{v \in \partial B(\o,r)} \psi(v).
\]
Consequently, $M(r)=\max_{\psi \in \pot} \min_{w \in V\setminus B(\o,r)} \psi(w)$ is non-decreasing in $r$.
\end{rema}

\begin{proof}[Proof of \theoref{conj:main} given \lemmref{lem:key}]
For each integer $r$, let $\psi_r$ be a potential where the maximum in the definition~\eqref{eq:keylem} of $M(r)$ is attained.
For every $n\geq 1$, choose $r_n$ such that $M(r_n)\geq n2^n$. By \claimref{claim:compact},
\[
h \coloneqq \sum_{n=1}^\infty 2^{-n} \psi_{r_n}
\]
is a potential. Next, if $w\notin B(\o,r_n)$, then $h(w) \geq 2^{-n} \psi_{r_n}(w) \geq n$. Thus, for each $n$, the set $\braces[\big]{v \in V : h(v) < n}$ is finite.
\end{proof}

\subsection{Preliminary lemmas}

The following lemma shows that if the dipoles $\g_\o(\,\cdot\,,v_n)$ converge to a potential $h$, then the network random walks conditioned on $\tau_{v_n} < \tau_\o$ converge weakly to the $h$-process. We actually need this for dipole mixtures. Given a probability measure $\eta$ on $V$, write
\[
\g_\o(\,\cdot\,, \eta) \coloneqq \sum_v \eta(v) \g_\o(\,\cdot\,, v).
\]

\begin{lemm}\label{lem:PathsConverge}
Let $(G,c,\o)$ be a recurrent rooted network. Let $r_n\to \infty$ be a sequence of integers and for each $n$ let\/ $\eta_{r_n}$ be a probability measure supported on $\partial B(\o,r_n)$. Assume that the sequence\/ $\g_\o(\,\cdot\,,\eta_{r_n})$ converges pointwise to a potential $h$ as $n\to \infty$. Then for any finite path $\gamma$ in $S_h$ starting at a neighbor of $\o$, we have
\begin{equation}\label{eq:pathsConverge}
\sum_{v} \eta_{r_n}(v) \P_\o\parens[\big]{\o \gamma \cond[\big] \tau_{v} < \tau_\o^+} \to \P_{\mu_h}^h(\gamma) \quad \text{as} \ n \rightarrow \infty.
\end{equation}
\end{lemm}
\begin{proof}
First note that for $v,w$ different from $\o$, we have $\g_\o(w,v)=\P_w(\tau_v <\tau_\o)\g_\o(v,v)$ and by path reversal,
\[
c_\o\P_\o(\tau_v <\tau_\o^+)=
c_v \P_v(\tau_\o <\tau_v^+)= c_v \G_\o(v,v)^{-1} =\g_\o(v,v)^{-1}.
\]
Therefore, if $\gamma=(\gamma_1,\dotsc,\gamma_\ell)$ does not contain the vertex $v$, then
\begin{equation} \label{dipoledoob}
\P_\o\parens[\big]{\o \gamma \cond[\big] \tau_{v} < \tau_\o^+}=\P_\o(\o \gamma) \frac{ \P_{\gamma_\ell}(\tau_{v} < \tau_\o) }{\P_{\o}(\tau_{v} < \tau_\o^+)}= c_\o \P_\o(\o \gamma) \g_\o(\gamma_\ell,v).
\end{equation}
Integrating this with respect to $\eta_{r_n}$ gives
\[
\sum_v \eta_{r_n}(v)\P_\o\parens[\big]{\o \gamma \cond[\big] \tau_{v} < \tau_\o^+} = c_\o \P_\o(\o \gamma) \g_\o(\gamma_\ell,\eta_{r_n}) \to
c_\o \P_\o(\o \gamma) h(\gamma_\ell),
\]
as $n \rightarrow \infty$ by our hypothesis. This yields the desired result by~\eqref{eq:hprocessvsSRW}.
\end{proof}

Let $h$ be a potential and set $T_M = \inf \braces[\big]{t > 0: h(X_t) \geq M}$ where $\{X_t\}$ is the network random walk. Optional stopping for the nonnegative martingale $h(X_{t\wedge \tau_\o})$ gives $\P_v(T_M < \tau_\o)\leq h(v)/M$. Careful path reversal and conditioning yields the following.

\begin{lemm}\label{lem:dipolePotential}
Let $h$ be a potential for a recurrent rooted network $(G,c,\o)$ and let $v\neq \o$ be a vertex. Then the network random walk $\{X_t\}$ satisfies
\[
\P_\o\parens[\big]{h(X_\ell) \geq M \cond[\big] \tau_v < \tau_\o^+} \leq \frac{h(v)}{M},
\]
for all $M>0$ and integer $0<\ell< d(\o,v)$, where $\tau_\o^+=\min \braces[\big]{ t \geq 1 : X_t = \o }$.
\end{lemm}

\begin{proof}
We may assume that $h(v)< M$. Since $\ell< d(\o,v)$ we have
\begin{equation}\label{eq:beforeReversing}
\P_\o\parens[\big]{h(X_\ell) \geq M \cond[\big] \tau_{v} < \tau_\o^+} \leq \P_\o\parens[\big]{T_{M} < \tau_{v} \cond[\big] \tau_{v} < \tau_\o^+}.
\end{equation}
Recall that $c_\o\P_\o(\tau_{v} < \tau_\o^+) = {c_{v}}\P_{v}(\tau_\o < \tau_{v}^+)$ by path reversal. Similarly,
\begin{equation}\label{eq:onemore}
\begin{aligned}
	c_\o \P_\o(T_{M} < \tau_{v} < \tau_\o^+) & = c_v \P_{v}(T_{M} < \tau_{\o} < \tau_{v}^+),
\\ \text{so} \quad \P_\o\parens[\big]{T_{M} < \tau_{v} \cond[\big] \tau_{v} < \tau_\o^+} & = \P_{v}\parens[\big]{T_{M} < \tau_{\o} \cond[\big] \tau_{\o} < \tau_{v}^+}.
\end{aligned}
\end{equation}
Consider the random walk started at $v$ and write $L = \max\braces[\big]{t < \tau_\o : X_t = v}$. Then $X_{L},\dotsc, X_{\tau_\o}$ is distributed as a random walk started at $v$, conditioned on $\tau_\o < \tau_{v}^+$, and stopped at $\o$. Hence
\begin{equation}\label{eq:DPstep2}
\P_{v}\parens[\big]{T_M < \tau_{\o} \cond[\big] \tau_{\o} < \tau_{v}^+} = \P_{v}\parens[\big]{\exists s\in (L,\tau_\o) : h(X_s)\geq M} \leq \P_{v}(T_M < \tau_o).
\end{equation}
To bound the last probability we note that $S_t=h(X_{t \wedge \tau_o})$ is a non-negative martingale, so by optional stopping
\[
h(v) = \E_v S_0 \geq \E_v S_{T_M} \geq M \P_{v}(T_M < \tau_\o).
\]
Combining this with~\eqref{eq:beforeReversing}, \eqref{eq:onemore} and~\eqref{eq:DPstep2} concludes the proof.
\end{proof}

\subsection{Proof of \lemmref{lem:key}}

Recall that $\pot$ denotes the set of potentials on $(G,c,\o)$. Given an integer $r>0$, let $\Upsilon_r$ be the compact space of probability measures on $\partial B(\o,r)$. Observe that for every $\psi \colon V\to \R$
\begin{equation}\label{eq:trivial}
\min_{v \in \partial B(\o,r)} \psi(v) =\min_{\eta \in \Upsilon_r} \sum_v \eta(v) \psi(v).
\end{equation} 
Next, we will apply Sion's minimax theorem~\cite{Sion58} to the function $f_r \colon \pot\times \Upsilon_r\to \RR$, defined by
\[
f_r(\psi, \eta) = \sum _{v \in \partial B(\o,r)} \eta(v)\psi(v).
\]
As noted in \claimref{claim:compact}, the set $\pot$ is a convex subset of the linear space $\mathbb{R}^V$ endowed with the product topology. Additionally, it is clear that $f_r$ is continuous and bilinear and that $\Upsilon_r$ is a compact convex subset of the linear topological space $\mathbb{R}^{\partial B(\o,r)}$. Hence the assumptions of Sion's theorem hold, and we obtain, using~\eqref{eq:trivial}, that $M(r)$ defined in~\eqref{eq:keylem} satisfies
\begin{equation}\label{eq:minmax}
M(r) = \max_{\psi\in \pot} \min_{\eta \in \Upsilon_r} f_r(\psi, \eta)= \min_{\eta \in \Upsilon_r}\max_{\psi\in \pot}f_r(\psi, \eta).
\end{equation}
For each integer $r>0$, let $\eta_r \in \Upsilon_r$ denote a minimizer of the right-hand side of~\eqref{eq:minmax}. By \claimref{claim:GreenIsDipole}, there exists a sequence $r_n\to \infty$ such that $\g_\o(\,\cdot\,,\eta_{r_n})$ converges pointwise to a function $h \colon V\to[0,\infty)$. Clearly $h$ is a potential.

Fix $m>0$. By \claimref{lem:hProcessInfty}, there exists an integer $\ell$ such that $ \P_{\mu_h}^h\parens[\big]{h(Y_\ell) \geq 2m} \geq 1/2.$ We now apply \lemmref{lem:PathsConverge} and sum~\eqref{eq:pathsConverge} over all paths $\gamma=(\gamma_1,\dotsc,\gamma_\ell)\subset S_h$ such that $h(\gamma_\ell)\geq 2m$. We infer that
\[
\lim_{n\to \infty} \sum_v \eta_{r_n}(v) \P_\o\parens[\big]{h(X_\ell) \geq 2m \cond[\big] \tau_v < \tau_\o^+} = \P_{\mu_h}^h\parens[\big]{h(Y_\ell) \geq 2m} \geq 1/2.
\]
\lemmref{lem:dipolePotential} states that if $\ell < r_n$ and $v\in \partial B(\o,r_n)$, then
\[
\P_\o\parens[\big]{h(X_\ell) \geq 2m \cond[\big] \tau_v < \tau_\o^+} \leq \frac{h(v)}{2m}.
\]
Combining the last two inequalities yields that
\[
\liminf_{n \rightarrow \infty} f_{r_n}(h, \eta_{r_n}) = \liminf_{n \rightarrow \infty} \sum_v \eta_{r_n}(v) {h(v)} \geq m.
\]
In conjunction with~\eqref{eq:minmax}, this gives that $\liminf_n M(r_n) \geq m$ for every $m>0$. Since $M(r)$ is non-decreasing (\remaref{remark:MR}), it must tend to infinity as $r \rightarrow \infty$. \qed

\section*{Acknowledgments}

We thank Omer Angel, Ori Gurel-Gurevich and Fedja Nazarov for helpful discussions.

\section*{Declaration of interests}

The authors do not work for, advise, own shares in, or receive funds from any organization that could benefit from this article, and have declared no affiliations other than their research organizations.

\printbibliography

\end{document}