1
$\begingroup$

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.

$\endgroup$
8
  • $\begingroup$ The answer would be a random variable. Are you looking for its probability distribution? $\endgroup$ Jan 21, 2019 at 22:19
  • 1
    $\begingroup$ If divided by the total number of walks of length $n$, namely $3^n$, yes. $\endgroup$
    – user76284
    Jan 21, 2019 at 22:21
  • 1
    $\begingroup$ Yes, since I'm just counting the number of walks. $\endgroup$
    – user76284
    Jan 21, 2019 at 22:28
  • 1
    $\begingroup$ 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. $\endgroup$
    – user76284
    Jan 21, 2019 at 22:32
  • 1
    $\begingroup$ 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. $\endgroup$
    – user76284
    Jan 22, 2019 at 2:17

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .