Gambler's ruin problem in several dimensions (Q696849)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Gambler's ruin problem in several dimensions |
scientific article |
Statements
Gambler's ruin problem in several dimensions (English)
0 references
12 September 2002
0 references
Consider symmetric simple random walk on \(\{0,1, \dots,N\} \times\{0,1, \dots,M\}\) with absorbing boundaries \(x=0\), \(x=N\), \(y=0\), \(y=M\). Let \(a(i,j)\) be the expected time to absorption when starting in \((i,j)\), satisfying \[ 4a(i,j)= 4+a(i+1,j) +a(i-1,j)+ a(i,j+1)+a(i,j-1), \quad 1\leq i\leq N-1,\;1\leq j\leq M-1,\tag{*} \] with boundary conditions \(a(i,j)=0\) for \(i=0\), \(i=N\), \(j=0\), \(j=M\). According to \textit{C. R. Orr} and \textit{D. Zeilberger} [J. Symb. Comput. 18, No. 1, 87-90 (1994; Zbl 0832.65115)] probably no closed form solution of (*) exists. The authors give a solution procedure that for \(N= M\) consists in writing (*) as a matrix equation \(AD+DA=-4J\) with \(A\) the \(a(ij)\) matrix and \(D,J\) explicit simple matrices, \(D\) to be diagonalized with known eigenvalues and eigenvectors, giving \(a(i,j)\) as a double sum of trigonometric terms. For \(N=2^p\), \(p\) positive integer, there is a single sum. A solution method for the \(d\)-dimensional analogue is described. Asymptotics: When \(d=2\), \(M=N=2n\), then \(a(n,n)= cn^2+O(\log n)^2\). When \(N_i=2n\), \(i=1,\dots,d\), then \(a(n,n, \dots, n)\sim bn^2\). Here \(c\) and \(b\) are given explicitly.
0 references
simple random walk
0 references
absorbing boundary
0 references
solution procedure
0 references