# Range of one-dimensional lattice paths of a given length

How many lattice paths in $$\mathbb{Z}$$ of length $$n$$ with steps in $$\{-1,0,+1\}$$ visit $$m$$ distinct points?

Notice that this is just the number of lattice paths $$P$$ such that $$\max P - \min P + 1 = m$$. If this helps, the generating function for the set of paths $$P$$ such that $$\max P = k$$ seems to be

$$(M(z) z)^k (M(z) z)^* M(z)$$

where

$$M(z) = \frac{2}{1 - z + \sqrt{(1 - 3 z) (1 + z)}}$$

is the generating function for the Motzkin numbers. The interpretation of this generating function is that one takes a left-leaning Motzkin path, moves right, takes a left-leaning Motzkin path, moves right, and so on $$k$$ times. Finally, one takes a left-leaning Motzkin path, moves left, takes a left-leaning Motzkin path, moves left, and so on an arbitrary number of times. Thus the final position can be anywhere to the left of the maximum.

• The answer would be a random variable. Are you looking for its probability distribution? Jan 21, 2019 at 22:19
• If divided by the total number of walks of length $n$, namely $3^n$, yes. Jan 21, 2019 at 22:21
• Yes, since I'm just counting the number of walks. Jan 21, 2019 at 22:28
• Because if each step is equally likely, the probability of any walk of length $n$ is just $3^{-n}$, and thus the probability of a set of walks is just its cardinality divided by $3^n$. I've edited the question to clarify this. Jan 21, 2019 at 22:32
• I believe the number of distinct points visited by a path $P$ is the size of the interval $[\min P, \max P]$, since it traverses every point in-between. Jan 22, 2019 at 2:17

According to The Range of a Simple Random Walk on $$\mathbb{Z}$$ by Bernhard Moser, the number of lattice paths in $$\mathbb{Z}$$ of length $$n$$ and range $$d$$ is
\begin{align} a_{n,d} &= (\mathbf{1}^\mathrm{T} \mathbf{Q}_d^n \mathbf{1} - \mathbf{1}^\mathrm{T} \mathbf{Q}_{d-1}^n \mathbf{1}) - (\mathbf{1}^\mathrm{T} \mathbf{Q}_{d-1}^n \mathbf{1} - \mathbf{1}^\mathrm{T} \mathbf{Q}_{d-2}^n \mathbf{1}) \\ &= \mathbf{1}^\mathrm{T} \mathbf{Q}_d^n \mathbf{1} - 2 \cdot \mathbf{1}^\mathrm{T} \mathbf{Q}_{d-1}^n \mathbf{1} + \mathbf{1}^\mathrm{T} \mathbf{Q}_{d-2}^n \mathbf{1} \end{align}
where $$\mathbf{1} =(1, \dots, 1)^\mathrm{T}$$ is a vector of ones and $$\mathbf{Q}_d$$ is the $$d \times d$$ band matrix $$(\mathbf{Q}_d)_{ij} = [i - 1 \leq j \leq i + 1]$$
I include the main diagonal since I have steps $$\{-1,0,+1\}$$ rather than $$\{-1, +1\}$$ as in the paper. I've checked $$a_{n,d}$$ numerically and this expression seems correct.