Divisible sandpiles via random walks in random scenery

We analyze an optimal stopping problem for random walk in random scenery on general graphs, and determine when it has a finite optimum. We use this to extend a theorem of Levine, Murugan, Peres, and Ugurcan [2016]. They proved that on a vertex-transitive graph, the divisible sandpile with i.i.d. initial masses of mean $\mu$ stabilizes almost surely if $\mu <1$, explodes if $\mu >1$, and explodes if $\mu =1$ with positive finite variance. Their proofs rely on conservation of mean mass under toppling. This conservation extends to unimodular random graphs, but fails on general graphs. We prove explosion for all infinite bounded-degree graphs whenever $\mu \ge 1$, and stabilization for $\mu <1$ provided the initial masses have finite $p$-th moment for some $p>3$. Our conditions are nearly sharp: we exhibit unbounded-degree graphs on which sandpiles with $\mu >1$ stabilize, and for every $p<3$ we construct bounded-degree graphs on which sandpiles with~$\mu <1$ and finite $p$-th moment explode.