Log-concavity in planar random walks

Swee Hong Chan Department of Mathematics, UCLA, Los Angeles, CA 90095. [email protected] , Igor Pak Department of Mathematics, UCLA, Los Angeles, CA 90095. [email protected] and Greta Panova Department of Mathematics, USC, Los Angeles, CA 90089. [email protected]

Abstract.

We prove log-concavity of exit probabilities of lattice random walks in certain planar regions.

1. Introduction

In the study of random walks, there is a fundamental idea based on its Markovian property: when some “life event” happens to the walk, the future trajectory of the walk can be changed, and this transformation can be exploited to obtain both quantitative and qualitative conclusions on the random walk distributions. These “life events” can be rather mundane, for example the first time when the walk returns to the starting point, crosses with some other random walk, enters an obstacle, etc. On the other hand, the conclusions can be quite remarkable and include the classical reflection principle, and the Karlin–McGregor formula also known as the Lindström–Gessel–Viennot lemma in the discrete setting, see $\S$ 5.3.

In this paper we use a variation on this approach for random walks in simply connected planar regions. The conclusion is qualitative in some sense that at the end we prove log-concavity of a certain natural exit probability distribution. We chose to present a discrete version of the result rather than the (somewhat cleaner) continuous version as the former is more powerful and amenable to generalizations (see Section 4), while the latter follows easily by taking limits.

Theorem 1 (Special case of Theorem 7).

Let $\Gamma\subset\mathbb{Z}^{2}$ be a simply connected region in the plane whose boundary $\partial\Gamma=\alpha\cup\eta_{+}\cup\eta_{-}\cup\beta$ is comprised of two vertical intervals $\alpha,\hskip 0.85355pt\beta$ , and two $x$ -monotone lattice paths $\eta_{+},\hskip 0.85355pt\eta_{-}$ , see Figure 1. We assume that $\alpha\subset\{x=0\}$ and $\beta\subset\{x=m\}$ for some $m>0$ .

Let $\{X_{t}\}$ be the nearest neighbor lattice random walk which starts at the origin $X_{0}=O\in\alpha$ , and is absorbed whenever $X_{t}$ tries to exit the region $\hskip 0.85355pt\Gamma$ . Denote by $T$ the first time $t$ such that $X_{t}\in\beta$ , and let $p(k)$ be the probability that $X_{T}=(m,k)$ . Then $\{p(k)\}$ is log-concave:

p(k)^{2}\,\geq\,p(k+1)\hskip 1.70709ptp(k-1)\qquad\text{for all \ $k\in\mathbb{Z}$, \ such that \ \ $(m,k\pm 1)\hskip 0.85355pt\in\beta$}.

Refer to caption — Figure 1. Random walk $X_{t}$ in a region $\Gamma$ as in the theorem.

In particular, the theorem implies that the sequence $\{p(k)\}$ is unimodal (see e.g. [Brä]). This also points to the difficulty of proving the result by a direct calculation, as in general there is no natural point at which the probability maximizes. We refer to $p(k)$ as exit probabilities, since one can think of them as probabilities the walks exits the region through different points on the interval $\beta$ .

Perhaps surprisingly, Theorem 1 is a byproduct of our recent work [CPP2] on the Stanley inequality for the case of posets of width two; in fact, we obtain the inequality as a corollary of the theorem (see $\S$ 5.1).

2. Proof of Theorem 1

We start with the following combinatorial result. Throughout this section, a lattice path is a path in $\mathbb{Z}^{2}$ , possibly self-intersecting along vertices and edges.

Lemma 2.

In the conditions of Theorem 1, let $A,B\in\alpha$ and $C,C^{\prime},D,D^{\prime}\in\beta$ be six points on the boundary of the region $\Gamma$ , such that

A=(0,a),\ B=(0,b),\ C=(m,c),\ C^{\prime}=(m,c-r),\ D^{\prime}=(m,d+r),\ D=(m,d),

and suppose $(a-b)\leq(c-d)-r$ , where $r>0$ . Then there is an injection

\Phi:\,\bigl{\{}(\xi_{AC},\xi_{BD})\bigr{\}}\,\longrightarrow\,\bigl{\{}(\xi_{AC^{\prime}},\xi_{BD^{\prime}})\bigr{\}},

where

$\circ$ $\xi_{AC}:A\to C$ , $\xi_{BD}:B\to D$ , $\xi_{AC^{\prime}}:A\to C^{\prime}$ , and $\xi_{BD^{\prime}}:B\to D^{\prime}$ are lattice paths which lie inside $\Gamma$ ,

$\circ$ the sum of numbers of horizontal edges in $\xi_{AC}$ and $\xi_{BD}$ which project onto $[i,i+1]$ , is equal to

the sum of numbers of horizontal edges in $\xi_{AC^{\prime}}$ and $\xi_{BD^{\prime}}$ which project onto $[i,i+1]$ , for all $0\leq i\leq m-1$ ,

$\circ$ the sum of numbers of vertical edges in $\xi_{AC}$ and $\xi_{BD}$ which project onto $j$ , is equal to

the sum of numbers of vertical edges in $\xi_{AC^{\prime}}$ and $\xi_{BD^{\prime}}$ which project onto $j$ , for all $0\leq j\leq m$ .

Here by project we mean the vertical projection onto the $x$ -axis. By adding the edge and vertex count equalities above over all $i$ and $j$ , we conclude that injection $\hskip 0.85355pt\Phi$ preserves the total length of these paths:

\bigl{|}\xi_{AC}\bigr{|}\hskip 1.70709pt+\hskip 1.70709pt\bigl{|}\xi_{BD}\bigr{|}\,=\,\bigl{|}\xi_{AC^{\prime}}\bigr{|}\hskip 1.70709pt+\hskip 1.70709pt\bigl{|}\xi_{BD^{\prime}}\bigr{|}\hskip 0.85355pt.

Proof of Lemma 2.

The proof is an explicit construction of the injection $\Phi$ , illustrated in Figure 2. See also Figure 3 in the next section for a detailed construction of each step.

$(0)$ We start with the lattice paths $\xi_{AC}$ and $\xi_{BD}$ drawn inside the region $\Gamma$ . Note that by the definition of the points in the lemma, we have $|CC^{\prime}|=|D^{\prime}D|=r$ .

$(1)$ Let $\ell:=b+c-d-r$ and let $B^{\prime}:=(0,\ell)$ . By the assumption in the lemma, $B^{\prime}$ lies above $A$ on the line spanned by $\alpha$ . Denote by $\widehat{\eta}_{-}$ the lattice path $B\to D$ formed by following interval $\alpha$ down from $B$ , then path $\eta_{-}$ and then interval $\beta$ up to $D$ . Let $\chi$ be the lattice path obtained by shifting $\eta_{-}$ up at distance $(\ell-b)$ . Similarly, let $\widehat{\chi}:B^{\prime}\to C^{\prime}$ be the lattice path obtained by shifting $\widehat{\eta}_{-}$ up at distance $(\ell-b)$ .

Note that the path $\xi_{AC}$ starts below $\widehat{\chi}$ and ends above $\widehat{\chi}$ . Thus $\xi_{AC}$ intersects $\widehat{\chi}$ at least once, where the intersection points could be multiple and include $A$ . Order these points of intersection according to the order in which they appear on $\hskip 0.85355pt\xi_{AC}$ , and denote by $E$ the last such point of intersection. Finally, denote by $\xi_{EC}$ the last part of the path $\xi_{AC}$ between $E$ and $C$ , and note that $\xi_{EC}$ lies above the $x$ -monotone lattice path $\widehat{\chi}$ .

$(2)$ Denote by $\widehat{\eta}_{+}$ the lattice path $A\to C$ , starting at $A$ , following $\alpha$ up, then $\eta_{+}$ and ending by following $\beta$ down to $C$ . Let $\zeta_{B^{\prime}C^{\prime}}:B^{\prime}\to C^{\prime}$ be the lattice path obtained by shifting $\xi_{BD}$ up at distance $\ell-b$ . By the same argument as above, path $\zeta_{B^{\prime}C^{\prime}}$ start above and ends below $\widehat{\eta}_{+}$ . Denote by $F$ the last point of intersection of $\widehat{\eta}_{+}$ and $\zeta_{B^{\prime}C^{\prime}}$ according to the order on which they appear on $\zeta_{B^{\prime}C^{\prime}}$ . Finally, denote by ${\zeta}_{FC^{\prime}}$ the last part of the path $\zeta_{B^{\prime}C^{\prime}}$ between $F$ and $C$ , and note that $\zeta_{FC^{\prime}}$ lies below the $x$ -monotone lattice path $\eta_{+}$ .

(3) Observe that $\zeta_{B^{\prime}C^{\prime}}$ lies above $\widehat{\chi}$ since shifting both paths down gives $\xi_{BD}$ lying above $\eta_{-}$ , respectively. Also, the path $\xi_{EC}$ lies below $\eta_{+}$ and above $\widehat{\chi}$ by definition. Since $C^{\prime}$ is below $C$ , we have that $E$ and $C$ lie on different sides of $\zeta_{FC^{\prime}}$ . Thus lattice paths $\xi_{EC}$ and $\zeta_{FC^{\prime}}$ must intersect in the connected component $\Lambda$ of the region between $\eta_{+}$ and $\widehat{\chi}$ that contains interval $[CC^{\prime}]\subset\beta$ . There could be many such intersections, of course, including multiple intersections when the paths form loops.

Lemma 3 (Fomin [Fom, Thm 6.1]).

Let $\gamma_{1}:E\to C$ and $\gamma_{2}:F\to C^{\prime}$ be two intersecting paths between boundary points of the simply connected region $\Lambda\subseteq\Gamma$ . Let $G\in\gamma_{1}\cap\gamma_{2}$ be an intersection point, and suppose

\gamma_{1}\hskip 1.70709pt:=\hskip 1.70709ptE\hskip 1.70709pt\to_{\gamma_{1}^{\prime}}\hskip 1.70709ptG\hskip 1.70709pt\to_{\gamma_{1}^{\prime\prime}}\hskip 1.70709ptC\qquad\text{and}\qquad\gamma_{2}\hskip 1.70709pt:=\hskip 1.70709ptF\hskip 1.70709pt\to_{\gamma_{2}^{\prime}}\hskip 1.70709ptG\hskip 1.70709pt\to_{\gamma_{2}^{\prime\prime}}\hskip 1.70709ptC\hskip 0.85355pt,

by which we mean that $G$ separates $\gamma_{i}$ into two paths: $\gamma_{i}^{\prime}$ and $\gamma_{i}^{\prime\prime}$ , where $i\in\{1,2\}$ . Then there is a well defined key intersection point $G$ as above, such that the map $\bigl{\{}(\gamma_{1},\gamma_{2})\bigr{\}}\to\bigl{\{}(\gamma_{1}^{\ast},\gamma_{2}^{\ast})\bigr{\}}$ is an injection, where the pair of paths $(\gamma_{1}^{\ast},\gamma_{2}^{\ast})$ is obtained from $(\gamma_{1},\gamma_{2})$ by a swap at $G$ :

\gamma_{1}^{\ast}\hskip 1.70709pt:=\hskip 1.70709ptE\hskip 1.70709pt\to_{\gamma_{1}^{\prime}}\hskip 1.70709ptG\hskip 1.70709pt\to_{\gamma_{2}^{\prime\prime}}\hskip 1.70709ptC^{\prime}\qquad\text{and}\qquad\gamma_{2}^{\ast}\hskip 1.70709pt:=\hskip 1.70709ptF\hskip 1.70709pt\to_{\gamma_{2}^{\prime}}\hskip 1.70709ptG\hskip 1.70709pt\to_{\gamma_{1}^{\prime\prime}}\hskip 1.70709ptC\hskip 0.85355pt.

The lemma is a special case of the (much more general) result by Fomin; below we include a proof sketch for completeness. Denote by $G$ the key intersection of paths $\xi_{EC}$ and $\zeta_{FC^{\prime}}$ defined by the lemma. Finally, denote by $\xi_{GC}$ the last part of the path $\xi_{EC}$ between $G$ and $C$ , and by ${\zeta}_{GC^{\prime}}$ the last part of the path $\zeta_{FC^{\prime}}$ between $G$ and $C$ .

(4) Denote by $\xi_{AG}:A\to G$ the lattice path $\xi_{AC}$ without the last part $\xi_{GC}$ . In the notation of the lemma, define $\xi_{AC^{\prime}}$ to be the path $\xi_{AG}$ followed by ${\zeta}_{GC^{\prime}}$ .

(5) Let $G^{\prime}$ be the point on $\xi_{BD}$ obtained by shifting $G$ down at distance $\ell$ , and denote by $\xi_{G^{\prime}D}$ the last part of the path $\xi_{BD}$ between $G$ and $D$ . Similarly, let $\mu_{G^{\prime}D^{\prime}}$ be the path obtained shifting down at distance $\ell$ the path ${\zeta}_{GC^{\prime}}\hskip 0.85355pt$ . Denote by $\xi_{BG^{\prime}}:B\to G^{\prime}$ the lattice path $\xi_{BD}$ without the last part $\xi_{G^{\prime}D}$ . In the notation of the lemma, define $\xi_{BD^{\prime}}$ to be the path $\xi_{BG^{\prime}}$ followed by $\mu_{G^{\prime}D^{\prime}}$ .

Claim: The map $\Phi:\hskip 0.85355pt\big{(}\xi_{AC},\xi_{BD}\big{)}\hskip 0.85355pt\to\hskip 0.85355pt\big{(}\xi_{AC^{\prime}},\xi_{BD^{\prime}}\big{)}$ constructed above is an injection.

To prove the claim, we consider the inverse of $\Phi^{-1}$ . Start with a pair of lattice paths $(\xi_{AC^{\prime}},\xi_{BD^{\prime}})$ and follow the steps as above after relabeling $C\leftrightarrow C^{\prime}$ , $D\leftrightarrow D^{\prime}$ . This construction will not work at all cases as the shifted paths are no longer guaranteed to intersect because of topological considerations. However, when $(\xi_{AC^{\prime}},\xi_{BD^{\prime}})=\Phi(\xi_{AC},\xi_{BD})$ , the construction will work for the same reason and produce the pair of lattice paths $(\xi_{AC},\xi_{BD})$ as in the steps $(0)$ – $(5)$ . Here we are using the key intersection point in step $(3)$ to ensure the construction is well defined and can be inverted at this step. We see that $\Phi$ is an involution between pairs of lattice paths $\bigl{\{}(\xi_{AC},\xi_{BD})\bigr{\}}$ and the pairs of paths $\bigl{\{}(\xi_{AC^{\prime}},\xi_{BD^{\prime}})\bigr{\}}$ , which intersect as in $(3)$ after the translations in $(1)$ and $(2)$ . The details are straightforward.

Finally, the projection conditions on $\Phi$ as in the lemma are straightforward. Indeed, we effectively swap parts of lattice paths: $\xi_{GC}$ with ${\zeta}_{GC^{\prime}}$ , and $\xi_{G^{\prime}D}$ with $\mu_{G^{\prime}D^{\prime}}$ . Since path $\xi_{GC}$ is shifted path $\mu_{G^{\prime}D^{\prime}}$ , and path $\xi_{G^{\prime}D}$ is shifted path ${\zeta}_{GC^{\prime}}$ , this implies both conditions. ∎

Proof of Theorem 1.

In the notation of Lemma 2, set $a=b=0$ , so both points $A=B$ lie at the origin. Further, set $r=1$ , $c=k+1$ and $d=k-1$ , so $C=(m,k+1)$ , $C^{\prime}=D^{\prime}=(m,k)$ and $D=(m,k-1)$ . In this case, the injection $\Phi$ shows that the number of pairs of lattice paths $O\to(m,k+1)$ and $O\to(m,k-1)$ , is less of equal than the number of lattice paths $O\to(m,k)$ , squared.

We are not done, however, as our paths overcount the paths implied by the probabilities in the theorem, since we consider only the first time by the lattice random walk $X_{t}$ is at $\beta$ . Recall that $\Phi$ preserves the number of horizontal edges which project onto point $m$ and onto $[m-1,m]$ . The assumption in the theorem that $T$ is the first time the walk is at $\beta$ can be translated as having exactly one of point $(m,\ast)$ and exactly one edge $(m-1,\ast)\to(m,\ast)$ corresponding to the last step of the walk $X_{t}$ . Therefore, this property is also preserved under $\Phi$ . This completes the proof. ∎

Remark 4.

The level of generality in Lemma 2 may seem like an overkill as we only use a special case in the proof of the theorem. In reality, explaining the special case needed for Theorem 1 is no easier than the general case in the lemma. In fact, setting $A=B$ only makes it more difficult to keep track of the paths. Furthermore, other properties in the lemma are used heavily in the next section.

Sketch of proof of Lemma 3.

Let $\Omega\subset\mathbb{Z}^{2}$ be a simply connected region and let $\gamma:P\to Q$ be a lattice walk in $\Omega$ , where $P,Q\in\Omega$ . Define a loop-erased walk ${\text{\rm LE}}(\gamma)$ by removing cycles as they appear in $\gamma$ . Formally, take the first self-intersection point $X$ , where $\gamma:P\to_{\gamma^{\prime}}X\to_{\gamma^{\prime\prime}}X\to_{\gamma^{\prime\prime\prime}}Q$ , and remove part $\gamma^{\prime\prime}$ . Repeat this until the resulting path ${\text{\rm LE}}(\gamma)$ has no self-intersections.

Suppose $P_{1},Q_{1},Q_{2},P_{2}\in\partial\Omega$ are points on the boundary (oriented clockwise) and in this order. For a pair of paths $(\gamma_{1},\gamma_{2})$ , $\gamma_{1}:P_{1}\to Q_{2}$ , $\gamma_{2}:P_{2}\to Q_{1}$ , note that $\gamma_{1}$ and $\gamma_{2}$ intersect by planarity, and so do ${\text{\rm LE}}(\gamma_{1})$ and $\gamma_{2}$ . Let $X$ be the intersection point of $\gamma_{2}$ and ${\text{\rm LE}}(\gamma_{1})$ which lies closest to $P_{1}$ along the path ${\text{\rm LE}}(\gamma_{1})$ . Note that point $X$ can appear multiple times on $\gamma_{1}\supseteq{\text{\rm LE}}(\gamma_{1})$ .

Consider the point $X\in\gamma_{1}$ such that the edge $Y\to X$ in $\gamma_{1}$ is not deleted in ${\text{\rm LE}}(\gamma_{1})$ . Similarly, choose the first $X$ on $\gamma_{2}$ . This defines the key intersection of paths $\gamma_{1}$ and $\gamma_{2}$ . As in the lemma, swap the future of these paths to obtain paths $(\gamma_{1}^{\ast},\gamma_{2}^{\ast})$ . To see that the map $(\gamma_{1},\gamma_{2})\hskip 0.85355pt\to\hskip 0.85355pt(\gamma_{1}^{\ast},\gamma_{2}^{\ast})$ in an injection, note that it is invertible on all pairs $(\gamma_{1}^{\ast},\gamma_{2}^{\ast})$ such that ${\text{\rm LE}}(\gamma_{1}^{\ast})$ intersects $\gamma_{2}^{\ast}$ . We omit the details. ∎

Remark 5.

There is a much larger probabilistic context in which the loop-erased random walk plays a prominent role, see e.g. [LL, $\S$ 11] and $\S$ 5.3.

3. Large example and subtleties in the proof

The construction in the proof above may seem excessively complicated at first, given that the map $\Phi$ is easy to define in the example in Figure 2. Indeed, in that case one can simply shift $\xi_{BD}$ up to define path $\zeta_{B^{\prime}D^{\prime}}$ , find the last (only in this case) intersection point $G$ with $\xi_{AC}$ , and swap the futures of these paths as we do in $(4)$ and $(5)$ . Voila!

Unfortunately, this simplistic approach does not work for multiple reasons. Let’s count them here:

(i) Path $\zeta_{GC^{\prime}}$ does not have to be inside $\Gamma$ . This is why we defined point $F$ in $(2)$ .

(ii) Path $\zeta_{G^{\prime}D^{\prime}}$ does not have to be inside $\Gamma$ . This is why we defined path $\chi$ and point $E$ in $(1)$ .

(iii) Paths $\chi$ and $\xi_{AC}$ do not have to intersect at all. This is why we defined path $\widehat{\chi}$ in $(1)$ .

(iv) Paths $\zeta_{B^{\prime}C^{\prime}}$ and $\xi_{AC}$ do have to intersect for geometric reason, since $(a-b)\leq(c-d)-r$ . On the other hand, paths $\xi_{EC}$ and $\zeta_{FC^{\prime}}$ intersect for topological reasons. This is why in $(3)$ we consider a connected component of $\Lambda$ between paths $\eta_{+}$ and $\widehat{\chi}$ . Note that the latter can in fact intersect, possibly multiple times.

(v) Paths $\zeta_{B^{\prime}C^{\prime}}$ and $\xi_{AC}$ can have multiple loops intersecting each other in multiple ways. There is no natural way to define the “last intersection” which would be easy to reverse. This is why in $(3)$ we invoked Lemma 3, whose proof requires loop-erased walk and symmetry breaking.¹¹1In the first draft of the paper we were not aware of the issue (v), only to discover it when lecturing on the result.

To help the reader understand the issues (i), (ii) and (iv), consider a large example in Figure 3. Here paths $\xi_{AC}$ and $\chi$ intersect multiple times in step $(1)$ defining $E$ . Then, in step $(2)$ , path $\zeta_{B^{\prime}C^{\prime}}$ intersects the boundary $\eta_{+}$ multiple times. Note that $F$ is defined as the last intersection along path $\zeta_{B^{\prime}C^{\prime}}$ , not along $\eta_{+}$ . The same property applies to $E$ , even if in the example it is the last intersection on both paths.

What exactly goes wrong in (v) in the definition of $G$ is rather subtle and we leave this as an exercise to the reader. Note that there is no issue similar to (v) in the definition of points $E$ and $F$ , since the boundaries $\eta_{\pm}$ are $x$ -monotone.

Remark 6.

Note that we explicitly use $x$ -monotonicity of the boundary paths $\eta_{\pm}$ . In $\S$ 4.5 below, we address what happens when the boundary is not $x$ -monotone.

4. Generalizations and applications

4.1. General transition probabilities

In the notation of the introduction, consider a more general random walk $X_{t}$ which moves to neighbors with general (not necessarily uniform) transition probabilities:

{\text{\bf P}}\bigl{[}(i,j)\to(i\pm 1,j)\bigr{]}\hskip 1.70709pt=\hskip 1.70709pt\pi_{\pm}(i,j),\qquad{\text{\bf P}}\bigl{[}(i,j)\to(i,j\pm 1)\bigr{]}\hskip 1.70709pt=\hskip 1.70709pt\omega_{\pm}(i,j),

with obvious constraints $\pi_{\pm}(i,j),\hskip 0.85355pt\omega_{\pm}(i,j)\geq 0$ , and

\pi_{+}(i,j)\hskip 1.70709pt+\hskip 1.70709pt\pi_{-}(i,j)\hskip 1.70709pt+\hskip 1.70709pt\omega_{+}(i,j)\hskip 1.70709pt+\hskip 1.70709pt\omega_{-}(i,j)\,=1,

for all $(i,j)\in\Gamma$ . We say these transition probabilities are $y$ -invariant if they are translation invariant with respect to vertical shifts:

\pi_{\pm}(i,j)\hskip 1.70709pt=\pi_{\pm}(i,j^{\prime}),\quad\omega_{\pm}(i,j)\hskip 1.70709pt=\hskip 1.70709pt\omega_{\pm}(i,j^{\prime})\quad\text{for all \, $i,\hskip 0.85355ptj$ \hskip 1.70709ptand \hskip 1.70709pt$j^{\prime}$.}

Theorem 7.

Let $\Gamma\subset\mathbb{Z}^{2}$ be the lattice region as in Theorem 1. Let $\{X_{t}\}$ be the lattice random walk which starts at the origin $X_{0}=O\in\alpha$ , moves according to $y$ -invariant transition probabilities $\pi_{\pm}(i,j)$ , $\omega_{\pm}(i,j)$ as above, and is absorbed whenever $X_{t}$ tries to exit the region $\hskip 0.85355pt\Gamma$ . Denote by $T$ the first time $t$ such that $X_{t}\in\beta$ , and let $p(k)$ be the probability that $X_{T}=(m,k)$ . Then $\{p(k)\}$ is log-concave:

p(k)^{2}\,\geq\,p(k+1)\hskip 1.70709ptp(k-1)\qquad\text{for all \ $k\in\mathbb{Z}$, \ such that \ \ $(m,k\pm 1)\hskip 0.85355pt\in\beta$}.

The proof of the theorem follows verbatim the proof of Theorem 1 in the previous section, since $y$ -invariance is exactly the property preserved by the injection $\Phi$ in Lemma 2. $\square$

4.2. Monotone walks

Let $\{X_{t}\}$ be a random walk as above with $y$ -invariant transition probabilities. We say that the walk is monotone if $\pi_{-}(i,j)=\omega_{-}(i,j)=0$ for all $(i,j)\in\Gamma$ .

Corollary 8.

Let $\Gamma\subset\mathbb{Z}^{2}$ be the lattice region as in Theorem 1, and let $\gamma=\{x=\ell\}\cap\Gamma$ be a vertical interval, $0<\ell<m$ . Fix points $A=(0,a)\in\alpha$ and $B=(m,b)\in\beta$ . Let $\{X_{t}\}$ be a monotone lattice random walk which starts at point $X_{0}=A\in\alpha$ , moves according to $y$ -invariant transition probabilities $\pi_{+}(i,j)$ , $\omega_{+}(i,j)$ as above, is absorbed whenever $X_{t}$ tries to exit the region $\hskip 0.85355pt\Gamma$ , and arrives at $B$ at time $u=(m+b-a)$ : $X_{u}=B$ . Denote by $T$ the first time $t$ such that $X_{t}\in\gamma$ , and let $q(k)$ be the probability that $X_{T}=(\ell,k)$ . Then $\{q(k)\}$ is log-concave:

q(k)^{2}\,\geq\,q(k+1)\hskip 1.70709ptq(k-1)\qquad\text{for all \ $k\in\mathbb{Z}$, \ such that \ \ $(\ell,k\pm 1)\hskip 0.85355pt\in\gamma$}.

Proof.

Define two regions: $\Gamma_{1}:=\{(i,j)\in\Gamma~{}:~{}0\leq i\leq\ell\}$ and $\Gamma_{2}:=\{(i,j)\in\Gamma~{}:~{}\ell-1\leq i\leq m\}$ . Note that the regions are overlapping along interval $\gamma$ and interval $\gamma^{\prime}:=\{(\ell-1,j)\in\Gamma\}$ , see Figure 4. Suppose $(\ell-1,k)\to(\ell,k)$ is the unique edge of the lattice path $A\to B$ which projects onto $[\ell-1,\ell]$ . In the notation of Theorem 7, we have

q(k)\hskip 1.70709pt=\hskip 1.70709ptp_{1}(k)\hskip 1.70709ptp_{2}(k),

where $p_{1}(k)$ and $p_{2}(k)$ are the exit probabilities in the region $\Gamma_{1}$ and in the region $\Gamma_{2}$ rotated $180^{\circ}$ . Since $\{p_{i}(k)\}$ are log-concave by Theorem 7, so is $\{q(k)\}$ , as desired. ∎

4.3. General lattices

One can further generalize random walks from $\mathbb{Z}^{2}$ to general lattices. For example, we can include steps $\pm(1,1)$ and $y$ -invariant transition probabilities

{\text{\bf P}}\bigl{[}(i,j)\to(i\pm 1,j\pm 1)\bigr{]}\hskip 1.70709pt=\hskip 1.70709pt\nu_{\pm}(i,j),

such that $\nu_{\pm}(i,j)\hskip 0.85355pt=\hskip 0.85355pt\nu_{\pm}(i,j^{\prime})$ , for all $i,j$ and $j^{\prime}$ . One can view this result as a random walk on the triangular lattice instead, see Figure 4. Both the statement and the proof of Theorem 7 extend verbatim once the reader observes that all lattice paths which must intersect for topological reasons do in fact intersect at lattice points.

Similarly, one can use this approach and general transition probabilities to set some of them zero and obtain random walks on other lattices. For example, one can obtain the square–octagon lattice as in the figure by restricting the walks to vertices of the lattice. Theorem 7 applies to this case then. We omit the details.

4.4. Dyck and Schröder paths

In the context of enumerative combinatorics, it is natural to consider lattice paths with steps $(1,1)$ and $(1,-1)$ . Such paths are called Dyck paths. When step $(2,0)$ is added, such paths are called Schröder paths.

Fix two points $A=(0,0)$ and $B=(m,b)\in\mathbb{Z}^{2}$ and two nonintersecting Dyck paths $\eta_{\pm}:A\to B$ . Note that $m+b\equiv 0\pmod{2}$ , since otherwise there are no such paths. Denote by $\Gamma$ the region between these paths. Let $0<\ell<m$ , and denote by $\textrm{N}(k)$ the number of Dyck paths $\zeta:A\to B$ which lie inside $\Gamma$ and contain point $(\ell,k)$ .

Corollary 9.

In the notation above, the sequence $\{\textrm{\em N}(k)\}$ is log-concave:

\textrm{\em N}(k)^{2}\,\geq\,\textrm{\em N}(k+2)\hskip 1.70709pt\textrm{\em N}(k-2)\qquad\text{for all \ $k\in\mathbb{Z}$, \ such that \ \ $(\ell,k\pm 2)\hskip 0.85355pt\in\gamma$}.

Proof sketch.

The proof follows verbatim the proof of Corollary 8 via two observations. First, the vertical translation and topological properties used in the proof of Lemma 2 work with diagonal steps. Second, the intersection points of the paths are at the ends of the steps, not midway, because the Dyck paths here have endpoints on the underlying grid spanned by $(1,1)$ and $(1,-1)$ which is invariant under the $(0,2)$ translation. ∎

Similarly, fix two nonintersecting Schröder paths $\eta_{\pm}:A\to B$ , and denote by $\Gamma$ the region between these paths. Let $0<\ell<m$ , and denote by $\textrm{F}(k)$ the number of Schröder paths $\zeta:A\to B$ which lie inside $\Gamma$ and contain point $(\ell,k)$ . The same argument as above gives the following.

Corollary 10.

In the notation above, the sequence $\{\textrm{\em F}(k)\}$ is log-concave:

\textrm{\em F}(k)^{2}\,\geq\,\textrm{\em F}(k+2)\hskip 1.70709pt\textrm{\em F}(k-2)\qquad\text{for all \ $k\in\mathbb{Z}$, \ such that \ \ $(\ell,k\pm 2)\hskip 0.85355pt\in\gamma$}.

Remark 11.

Note that this result does not directly apply to the, otherwise similar, Motzkin paths, with steps $(1,1)$ , $(1,-1)$ and $(1,0)$ . The reason is that the intersection points used in the injection $\Phi$ in Lemma 2 might no longer be on the underlying lattice points and appear in the middle of the steps, e.g. at $(\frac{1}{2},\frac{1}{2})$ .

Example 12.

Take $A=(0,0)$ , $B=(2n,0)$ , so $m=2n$ . Fix maximal and minimal Dyck paths

	$\displaystyle\eta_{+}:$	$\displaystyle(0,0)\hskip 1.70709pt\to\hskip 1.70709pt(1,1)\hskip 1.70709pt\to\hskip 1.70709pt\ldots\hskip 1.70709pt\to\hskip 1.70709pt(n,n)\hskip 1.70709pt\to\hskip 1.70709pt(n+1,n-1)\hskip 1.70709pt\to\hskip 1.70709pt\ldots\hskip 1.70709pt\to\hskip 1.70709pt(2n,0),$
	$\displaystyle\eta_{-}:$	$\displaystyle(0,0)\hskip 1.70709pt\to\hskip 1.70709pt(1,-1)\hskip 1.70709pt\to\hskip 1.70709pt\ldots\hskip 1.70709pt\to\hskip 1.70709pt(n,-n)\hskip 1.70709pt\to\hskip 1.70709pt(n+1,-n+1)\hskip 1.70709pt\to\hskip 1.70709pt\ldots\hskip 1.70709pt\to\hskip 1.70709pt(2n,0).$

Set $\ell:=n$ , which makes the picture symmetric. Then Corollary 9 implies log-concavity of binomial coefficients $\bigl{\{}\binom{n}{k},\hskip 0.85355pt0\leq k\leq n\}$ . On the other hand, for the Schröder paths $A\to B$ , Corollary 10 implies log-concavity of Delannoy numbers $\bigl{\{}{\text{\rm D}}(k,n-k),\hskip 0.85355pt0\leq k\leq n\}$ , see [OEIS, A008288], a new enumerative result, see $\S$ 5.5.

Finally, let $\eta_{+}$ be as above and let

\eta_{-}:\hskip 1.70709pt(0,0)\hskip 1.70709pt\to\hskip 1.70709pt(1,1)\hskip 1.70709pt\to\hskip 1.70709pt(2,0)\hskip 1.70709pt\to\hskip 1.70709pt(3,1)\hskip 1.70709pt\to\hskip 1.70709pt\ldots\hskip 1.70709pt\to\hskip 1.70709pt(2n,0).

Then Corollary 9 implies log-concavity of ballot numbers $\bigl{\{}{\text{\rm B}}(k,n-k),\hskip 0.85355ptn/2\leq k\leq n\}$ , where

{\text{\rm B}}(k,n-k)\,=\,\hskip 1.70709pt\frac{2k-n+1}{k+1}\hskip 0.85355pt\binom{n}{k}.

4.5. Boundary matters

First, let us note that both Theorem 1 and Theorem 7 easily extend to regions without either or both of the boundaries $\eta_{\pm}$ . In this case the vertical boundaries $\alpha,\beta$ become either rays of lines, and the region $\Gamma$ is an infinite strip in one or two directions, see Figure 5.

Corollary 13.

In the notation of Theorem 1, let $\hskip 0.85355pt\Gamma$ be an infinite strip with one or two ends. Then the exit probability distribution $\{p(k)\}$ is log-concave.

The proof follows immediately from Theorem 1 by taking a sequence $\{\Gamma_{n}\}$ of regions where the boundary goes to infinity, i.e. $\Gamma_{n}\to\Gamma$ , and noting that log-concavity is preserved in the limit. Alternatively, one can easily modify the proof of Lemma 2 to work for unbounded regions; in fact the construction simplifies in that case. We omit the details.

One can also ask whether the $x$ -monotonicity assumption in the theorem can be dropped. Note that the proof of Lemma 2 breaks in step $(2)$ as the shifted path $\zeta_{B^{\prime}C^{\prime}}$ no longer has to lie inside $\Gamma$ , see Figure 5. Although we do not believe that Theorem 1 extends to non-monotone boundaries, it would be interesting to find a formal counterexample.

Example 14.

In the notation above, let $m=1$ and consider an infinite strip between two lines which forms a ladder graph $G$ as in Figure 5. When restricted to $G$ , the nearest neighbor random walk moves along $\alpha$ with equal probability $\frac{1}{3}$ of going up or down, until it eventually moves to the right, at which point it stops. In this case the exit probabilities can be calculated explicitly:

p(\pm 2r)\,=\,\sum_{n=0}^{\infty}\hskip 1.70709pt\frac{1}{3^{2n+1}}\hskip 1.70709pt\binom{2n}{n-r}\,,\qquad p(2r+1)\,=\,p(-2r-1)\,=\,\sum_{n=0}^{\infty}\hskip 1.70709pt\frac{1}{3^{2(n+1)}}\hskip 1.70709pt\binom{2n+1}{n-r}\,,

for all $r\geq 0$ . A direct calculation gives:

p(\pm k)\,=\,\frac{1}{\phi^{2k}\hskip 0.85355pt\sqrt{5}}\quad\text{for all \, $k\geq 0$}\hskip 0.85355pt,\quad\text{where}\ \ \phi\hskip 1.70709pt=\hskip 1.70709pt\frac{\sqrt{5}+1}{2}\ \ \text{is the \emph{\color[rgb]{0.0,0,0.7}\definecolor[named]{pgfstrokecolor}{rgb}{0.0,0,0.7}golden ratio}}.

Thus, log-concavity is an equality at all $k\neq 0$ . We leave it as an exercise to the reader to give a direct bijective proof of this fact. Note that these equalities disappear for $m\geq 2$ , cf. $\S$ 5.7.

5. Final remarks

5.1.

Log-concavity of the number of monotone lattice paths as in Corollary 8 is equivalent to the Stanley inequality for posets of width two, as noted in [CFG, GYY]. For general posets, the Stanley inequality was proved in [Sta1]. An explicit injection in the width two case was given in [CFG] and generalized by the authors [CPP1, CPP2]. The construction in [CPP2] was the basis of this paper.

5.2.

Except for the special case of monotone lattice paths and monotone boundary discussed above, we are not aware of the problem even being considered before. The generality of our results is then rather surprising given that even simple special cases appear to be new (see below).

5.3.

The reflection principle is due to Mirimanoff (1923), and is often misattributed to André, see [Ren]. It is described in numerous textbooks, both classical [Fel, Spi] and modern [LL, MP]. For the Karlin–McGregor formula (1959) and its generalizations, including the Brownian motion version of Fomin’s result (Lemma 3), see e.g. [LL, Ch. 9]. For the Lindström–Gessel–Viennot lemma and applications to enumeration of lattice paths, see the original paper [GV] and the extensive treatment in [GJ, $\S$ 5.4]. It is also related to a large body of work on tilings in the context of integrable probability, see [Gor]. For the algebraic combinatorics context of Fomin’s result in connection with total positivity, see [Pos, $\S$ 5].

5.4.

Note also that the log-concavity of exit probabilities does not seem to be a consequence of any standard non-combinatorial approaches. For example, the real-rootedness fails already for Delannoy numbers $\bigl{\{}{\text{\rm D}}(k,8-k),\hskip 0.85355pt0\leq k\leq 8\}$ , see $\S$ 4.4. We refer to [Bre, Sta2] for surveys of classical methods on unimodality and log-concavity, and to [Pak] for a short popular introduction to combinatorial methods. See also surveys [Brä, Huh] for more recent results and advanced algebraic and analytic tools.

5.5.

In the context of Example 12, Dyck, Schröder and Motzkin paths play a fundamental role in enumerative combinatorics in connection with the Catalan numbers [OEIS, A000108], Schröder numbers [OEIS, A006318] and Motzkin numbers [OEIS, A001006], respectively. Ballot numbers and Delannoy numbers appear in exactly the same context. We refer to [Sta3, Ch. 5] for numerous properties of these numbers.

While binomial coefficients and ballot numbers are trivially log-concave via explicit formulas, the log-concavity of Delannoy numbers appears to be new. Non-real-rootedness in this case suggests that already this special case is rather nontrivial. It would be interesting to see if log-concavity of Delannoy numbers can be established directly, in the style of basic combinatorial proofs in [Sag].

5.6.

There is a large literature on exact and asymptotic counting of various walks in the quarter plane with small steps, see e.g. [Bou, BM]. Most notably, both Kreweras walks (1965) and Gessel walks (2000) fit our framework, while some others do not. It would be interesting to further explore this connection.

5.7.

In the context of $\S$ 4.5 and Example 14, consider a simple random walk constrained to a strip $0\leq x\leq m$ , reflected at $x=0$ , and with no top/bottom boundaries. This special case is especially elegant. The exit probabilities $p(mt)$ , as $m\to\infty$ , converge to the hyperbolic secant distribution, which is log-concave in $t$ .²²2See the MathOverflow answer: https://mathoverflow.net/a/395065/4040. This is in sharp contrast with the case of a simple random walk which starts at the origin, but is not constrained to be in the $x\geq 0$ halfplane. Denote by $q(k)$ the hitting probabilities of the point $(k,m)$ on the line $x=m$ . In this case it is well known that hitting probabilities $q(mt)$ , as $m\to\infty$ , converge to the Cauchy distribution, see e.g. [Spi, p. 156], which is not log-concave (in $t$ ).

Acknowledgements

We are grateful to Robin Pemantle for interesting discussions on the subject, and to Timothy Budd for his help resolving the MathOverflow question. Nikita Gladkov pointed out a subtle issue in step $(3)$ of the construction in the previous version of this paper, necessitating the addition of Lemma 3. We are also thankful to Per Alexandersson and Cyril Banderier for helpful remarks on the paper. We also thank the anonymous referees for useful comments to improve presentation. The last two authors were partially supported by the NSF.

References

[Bou] M. Bousquet-Mélou, Counting walks in the quarter plane, in Trends Math., Birkhäuser, Basel, 2002, 49–67.
[BM] M. Bousquet-Mélou and M. Mishna, Walks with small steps in the quarter plane, in Contemp. Math. 520, AMS, Providence, RI, 2010, 1–39.
[Brä] P. Brändén, Unimodality, log-concavity, real-rootedness and beyond, in Handbook of enumerative combinatorics, CRC Press, Boca Raton, FL, 2015, 437–483.
[Bre] F. Brenti, Unimodal, log-concave and Pólya frequency sequences in combinatorics, Mem. AMS 81 (1989), no. 413, 106 pp.
[CPP1] S. H. Chan, I. Pak and G. Panova, The cross–product conjecture for width two posets, preprint (2021), 30 pp; arXiv: 2104.09009.
[CPP2] S. H. Chan, I. Pak and G. Panova, Extensions of the Kahn–Saks inequality for posets of width two, preprint (2021), 24 pp.; arXiv:2106.07133.
[CFG] F. R. K. Chung, P. C. Fishburn and R. L. Graham, On unimodality for linear extensions of partial orders, SIAM J. Algebraic Discrete Methods 1 (1980), 405–410.
[Fel] W. Feller, An introduction to probability theory and its applications, vol. I (Third ed.), John Wiley, New York, 1968, 509 pp.
[Fom] S. Fomin, Loop-erased walks and total positivity, Trans. AMS 353 (2001), 3563–3583.
[GV] I. M. Gessel and X. Viennot, Binomial determinants, paths, and hook length formulae, Adv. Math. 58 (1985), 300–321.
[Gor] V. Gorin, Lectures on random tilings, monograph draft, Nov. 25, 2019, 191 pp.; https://tinyurl.com/w22x6qq .
[GJ] I. P. Goulden and D. M. Jackson, Combinatorial enumeration, Wiley, New York, 1983, 569 pp.
[GYY] R. L. Graham, A. C. Yao and F. F. Yao, Some monotonicity properties of partial orders, SIAM J. Algebraic Discrete Methods 1 (1980), 251–258.
[Huh] J. Huh, Combinatorial applications of the Hodge–Riemann relations, in Proc. ICM Rio de Janeiro, Vol. IV, World Sci., Hackensack, NJ, 2018, 3093–3111.
[LL] G. F. Lawler and V. Limic, Random walk: a modern introduction, Cambridge Univ. Press, Cambridge, UK, 2010, 364 pp.
[MP] P. Mörters and Y. Peres, Brownian motion, Cambridge Univ. Press, Cambridge, UK, 2010, 403 pp.
[Pak] I. Pak, Combinatorial inequalities, Notices AMS 66 (2019), 1109–1112; an expanded version of the paper is available at https://tinyurl.com/py8sv5v6.
[Pos] A. Postnikov, Total positivity, Grassmannians, and networks, preprint (2006), 79 pp.; arXiv:math/0609764.
[Ren] M. Renault, Lost (and found) in translation, Amer. Math. Monthly 115 (2008), 358–363.
[Sag] B. E. Sagan, Inductive and injective proofs of log concavity results, Discrete Math. 68 (1988), 281–292.
[OEIS] N. J. A. Sloane, The online encyclopedia of integer sequences, oeis.org.
[Spi] F. Spitzer, Principles of random walk (Second ed.), Springer, New York, 1976, 408 pp.
[Sta1] R. P. Stanley, Two combinatorial applications of the Aleksandrov--Fenchel inequalities, J. Combin. Theory, Ser. A 31 (1981), 56--65.
[Sta2] R. P. Stanley, Log-concave and unimodal sequences in algebra, combinatorics, and geometry, in Graph theory and its applications, New York Acad. Sci., New York, 1989, 500--535.
[Sta3] R. P. Stanley, Enumerative Combinatorics, vol. 1 (Second ed.) and vol. 2, Cambridge Univ. Press, 2012 and 1999.