Enumeration of Random Walk Positions in $L_1$-norm ball in ${\mathbb{Z}}^d$

Abstract

In this paper, we mainly concerned about deriving the general formula to count the possible positions of $n$ step random walk in ${\mathbb{Z}}^d$ with unit length in each step, which we denoted as $|P_n^d|$. For our results, we firstly propose a recurrence relation of the counting formula: $|P_n^{d+1}|=|P_n^d|+2{\sum }_{k=0}^{n-1}|P_k^d|$. Next, we propose two methods in deriving the explicit formula of $|P_n^d|$ using generating functions and Faulhaber's formula. Finally, we reached our main theorem in the matrix representation of our formula.

13 pages, 2 figures