counting walks on a finite interval

Question

Find the number of random walks on the integers $\{1, 2, ... m\}$ of length $n$.

(For the purposes of this question a "random walk" is a sequence $\{a_i\}$ such that $a_i - a_{i+1} = \pm 1$.)

Answer 1

At this point I would like to remark that the solution $g_m(n)$ is given by $$g_m(n) = \sum_{i=1}^m c_m(i)\lambda_m(i)^n$$ where the $\lambda_m(i)$ are the eigenvalues of the $m\times m$ matrix $$A_m=\begin{bmatrix}0&1&0&0&0&...\\ 1&0&1&0&0&...\\0&1&0&1&0&...\\0&0&1&0&1&...\\0&0&0&1&0&...\\.&.&.&.&.&.\end{bmatrix}$$ and $c_m(i)$ are some recursion coefficients. This follows because the number of walks of length $n$ starting at $i$ and ending at $j$ is given by the $(i, j)$ element of $A^n$, and by the Cayley-Hamilton theorem this number satisfies the recurrence whose characteristic polynomial is $\text{Char}(A)$, so $g$, which is the sum over all $(i, j)$, satisfies this recurrence as well. The question then is, are the eigenvalues of $A$ in some way regular? Clearly we have $$\text{Char}(A_m) = -x \text{Char}(A_{m-1}) - \text{Char}(A_{m-2})$$and solving as a recurrence in $m$ with initial values $-x$ and $x^2-1$ gives $$\text{Char}(A_m) = \left( \frac{1}{2}+\frac{x}{2\sqrt{x^2-4}}\right)\left(\frac{-x-\sqrt{x^2-4}}{2}\right)^m+\left( \frac{1}{2}-\frac{x}{2\sqrt{x^2-4}}\right)\left(\frac{-x+\sqrt{x^2-4}}{2}\right)^m$$ which can be regarded as a generating function for the characteristic polynomial coefficients.$$$$ An alternative approach which avoids the necessity of computing recursion coefficients $c_m(i)$: directly sum elements of powers of $A$, by diagonalizing it. We notice that $A$ has distinct eigenvalues, and the eigenvector $v_i$ associated with the eigenvalue $\lambda_i$ is given by $$v_i=\begin{bmatrix}1\\\lambda_i\\\lambda_i^2-1\\\lambda_i^3-2\lambda_i\\.\\.\\.\end{bmatrix};$$ the $j$-th element being $(-1)^{j+1}\text{Char}(A_{j+1})(\lambda_i)$. Incidentally, the orthogonality of this eigenbasis leads to the additional conclusions that $\sum_{i=1}^m\lambda_i^k=0$ for odd $k$, $2m-2$ for $k=2$, $4m-4$ for $k=4$, and unknown things for higher even powers. $$$$ In conclusion, I am moderately satisfied with this problem. I thought at first because of the symmetry of $A$ there would be a really clean solution. That wasn't the case, but I think at least there was some slightly nontrivial content. A last remark: this should be equivalent to a modified Bertrand's ballot problem, where you ask for the probability that two candidates in an election always stay within $\frac{m}{2}$ votes of each other, instead of the probability that one of them always stays ahead. I wonder if there is anything to be said about it from this perspective.