A note on absorption probabilities in one-dimensional random walk via complex-valued martingales

Let {Xn,n[greater-or-equal, slanted]1} be a sequence of i.i.d. random variables taking values in a finite set of integers, and let Sn=Sn-1+Xn for n[greater-or-equal, slanted]1 and S0=0 be a random walk on , the set of integers. By using the zeros, together with their multiplicities, of the rational function , we characterize the space U of all complex-valued martingales of the form {g(Sn),n[greater-or-equal, slanted]0} for some function . As an application we calculate the absorption probabilities of the random walk {Sn,n[greater-or-equal, slanted]0} by applying the optional stopping theorem simultaneously to a basis of the martingale space U. The advantage of our method over the classical approach via the Markov chain techniques (cf. Kemeny and Snell [1960. Finite Markov Chains. Van Nostrand, Princeton, NJ.]) is in the size of the matrix that is needed to be inverted. It is much smaller by our method. Some examples are presented.