A combinatorial approach to the two-sided exit problem for left-continuous random walks (Q2731586)

Let \(X(n)\), \(n= 0,1,2,\dots\), be a random walk on \(\mathbb{Z}\) with steps \(\geq -1\) and let \(Y(n)\) be \(X(n)\) killed at the first exit from \(V= \{0,1\dots, N\}\). Put \(M\) for the restriction of the transition matrix of \(X(n)\) to \(V\times V\). Then NEWLINE\[NEWLINE\sum_n P_i(Y(n)= j)t^n= \sum_n t^n(M^n)_{ij}= (I- tM)^{- 1}(i, j)= \text{cof}_{ji}(I- tM)/\text{Det}(I- tM),NEWLINE\]NEWLINE \(t\in V\), \(j\in V,\) by Cramer's rule. To find this generating function the author applies a general combinatorial theorem on inversion of a matrix \(I- tB\) on the vertex set of a directed graph defined by a valuation on the edges. This theorem shows that \(\text{Det}(I- tM)= D_N(t)\), which is a sum over simple cycles in \(V\) traversable by \(X(n)\). The study of these cycles gives a recursion for \(D_N(t)\) and then a generating function w.r.t. \(N\). The combinatorial theorem expresses \(\text{cof}_{ji}(I- tM)\) in terms of the \(D_k(t)\), \(k\leq N\). This leads to the joint distribution of \(T\), the first exit time of \(X(n)\) from \(V\), and \(X(T)\) in terms of generating functions w.r.t. \(N\). Classically \(\lambda^n M^n\) converges as \(n\to\infty\). Here \(\lambda> 0\) is the smallest zero of \(\text{Det}(I- tM)\). The limiting matrix is expressed in the \(D_k(t)\), \(k\leq N\). Specialization to simple random walk and its range process is given. The above combinatorial theorem is also applied to the birth and death process on \(V\) and the simple random walk on \(\mathbb{Z}/\mathbb{N}\).