For \(m \in \N_+\), let \(\N_m = \{0, 1, \ldots, m\}\), and define the relation \(\lfrta\) on \(\N_m\) by \(x \lfrta x + 1\) for \(x \in \{0, 1, \ldots m - 1\}\) and \(x \lfrta x - 1\) for \(x \in \{1, 2, \ldots m\}\).
So the graph \((\N_m, \lfrta)\) is the symmetric (undirected) simple path \((0, 1, \ldots, m)\) (with no loops). Since the graph is discrete, we have our reference measure space \((\N_m, \ms P(\N_m), \#)\) in the background. All of our objects of study depend on \(m\), but we will surpress this from the notation unless necessary. Given the symmetry of the graph, it's not surprising that various functions on the domain will be symmetric about the midpoint.
A function \(\varphi\) defined on \(\N_m\) is symmetric if \(\varphi(x) = \varphi(m - x)\) for \(x \in \N_m\).
The path function \(\gamma_n\) of order \(n \in \N\) for \((\N_m, \lfrta)\) is symmetric and is given as follows: \(\gamma_0(x) = 1\) for \(x \in \N_m\) and then recursively, \begin{align*} \gamma_{n + 1}(0) &= \gamma_n(1)\\ \gamma_{n + 1}(x) &= \gamma_n(x - 1) + \gamma_n(x + 1), \quad x \in \{1, 2, \ldots, m - 1\} \\ \gamma_{n + 1}(m) &= \gamma_n(m - 1) \end{align*}
By definition, \(\gamma_0(x) = 1\) for \(x \in \N_m\) and \(\gamma_{n + 1} = \gamma_n L\) where as ususal, \(L\) is the adjacency matrix of \((\N_m, \lfrta)\). In this case, for \(u: \N_m \to \R\), \begin{align*} u L(0) &= u(1)\\ u L(x) &= u(x - 1) + u(x + 1), \quad x \in \{1, 2, \ldots, m - 1\}\\ u L(m) &= u(m - 1) \end{align*} So the result follows.
The coefficients \(\gamma_n(x)\) for \(m \in \N_+\), \(n \in \N\), and \(x \in \N_m\) are interesting, and are objects of study in graph theory. By definition, \(\gamma_n(x)\) is the number of paths of length \(n\) terminating in \(x \in \N_m\) in the graph \((\N_m, \lfrta)\). By symmetry, \(\gamma_n(x)\) is also the number of paths of length \(n\) starting at \(x\). For most values of \(m\) and \(x\), it seems difficult to give a closed-form expression for \(\gamma_n(x)\) for \(n \in \N\) and \(x \in \N_m\). The path generating function \(\Gamma\) for \((\N_m, \lfrta)\), which encodes the same information, is easier to study.
For \(x \in \N_m\), the path generating function \(\Gamma(x, t)\) is defined for \(|t| \lt \frac{1}{2}\). The function \(x \mapsto \Gamma(x, t)\) is symmetric and is given by \begin{align*} \Gamma(0, t) &= 1 + t \Gamma(1, t) \\ \Gamma(x, t) &= 1 + t \Gamma(x - 1, t) + t \Gamma(x + 1, t), \quad x \in \{1, 2, \ldots, m - 1\} \end{align*}
Recall that \(\gamma_n(x)\) can be interpreted as the number of paths of length \(n \in \N\) starting from \(x \in S\). Since there are at most 2 neighbors of each state, \(\gamma_n(x) \le 2^n\). So the reuslts follow from the definition of the generating function \[\Gamma(x, t) = \sum_{n = 0}^\infty \gamma_n(x) t^n, \quad x \in S\] and from .
So \(\Gamma\) satisfies the relation given in Section 2 for the infinite path, but only for \(x \in \N_m\).
Consider the case \(m = 2\) so that \((\N_2, \lfrta)\) is the undirected simple path \((0, 1, 2)\). Find each of the following explicitly:
Consider the case \(m = 3\) so that \((\N_3, \lfrta)\) is the undirected simple path \((0, 1, 2, 3)\). Find each of the following explicitly:
Consider the case \(m = 4\) so that \((\N_4, \lfrta)\) is the undirected simple path \((0, 1, 2, 3, 4)\). Find each of the following explicitly:
Recall that the \(\sigma\)-algebra associated with a graph is the \(\sigma\)-algebra generated by the neighbor sets.
For \(m \in \N_+\) and \(m \ne 2\), the \(\sigma\)-algebra associated with \((\N_m, \lfrta)\) is \(\ms P(\N_m)\). The case \(m = 2\) is exceptional and in this case, the associated \(\sigma\)-algebra is \[\sigma(\{1\}) = \{\emptyset, \{1\}, \{0, 2\}, \{0, 1, 2\}\}\]
Let \(A_x = \{y \in \N_m: x \lfrta y\}\) denote the neighbor set of \(x \in \N_m\) so that \(\ms A = \sigma(\{A_x: x \in \N_m\})\) is the associated \(\sigma\)-algebra. The case \(m = 1\) is trivial since the neighbor sets are \(A_0 = \{1\}\) and \(A_1 = \{0\}\). When \(m = 2\) the neighbor sets are \(A_0 = A_2 = \{1\}\) and \(A_1 = \{0, 2\}\). Suppose that \(m \ge 3\). Then \(A_x \cap A_{x + 2} = \{x + 1\}\) for \(x \in \{0, 1, \ldots, m - 2\}\). Hence \(\{x\} \in \ms A\) for \(x \in \{1, 2, \ldots, m - 1\}\). But also \(\{0\} = A_1 \setminus A_3\) and \(\{m\} = A_{m - 1} \setminus A_{m - 3}\). Hence \(\ms A = \ms P(\N_m)\).
Our next goal is to identify the (right) eigenvalues and eigenfunctions of \((\N_m, \lfrta)\), and once again, the polynomials in Section 1 will play a critical role.
The characteristic polynomial of \((\N_m, \lfrta)\) is \(P_{m+1}\). If \(\beta \in \R\) is an eigenvalue, then an eigenfunction \(g\) is given by \(g(x) = P_x(\beta)\) for \(x \in \N_m\).
Let \(L\) denote the adjacency matrix of \((\N_m, \lfrta)\) as usual. Then \(\beta \in \R\) is an eigenvalue and \(g: \N_m \to \R\) a corresponding eigenfunction if \(g\) is nonzero and \(L g = \beta g\), or equivalently,
Equivalently, we can consider functions \(g: \N \to \R\) satisfying (a) and (b) above, but with the boundary condition \(g(m + 1) = 0\) which then gives (c). But by the results in Section 2, the solution of (a) and (b) is given by \(g(x) = g(0) P_x(\beta)\) for \(x \in \N\), and the requirement that \(g(m + 1) = 0\) means that \(\beta\) is a root of \(P_{m + 1}\).
The eigenvalues of \((\N_m, \lfrta)\) are \[\beta_k = 2 \cos\left(\frac{k}{m + 2} \pi\right), \quad k \in \{1, 2, \ldots, m + 1\}\] The eigenvalues are simple and for \(k \in \{1, 2, \ldots, m + 1\}\), an eigenfunction \(g_k\) corresponding to \(\beta_k\) is given by \[g_k(x) = \frac{1}{\sin\left(\frac{k}{m + 2}\right)} \sin\left[\frac{(x + 1) k}{m + 2} \pi\right], \quad x \in \N_m\]
These results follow from Proposition and results in Section 1.
Suppose now that \(X\) is a random variable in \(\N_m\) with density function \(f\) so that \(f(x) = \P(X = x)\) for \(x \in \N_m\).
The reliability function \(F\) of \(X\) for \((\N_m, \lfrta)\) is given by \begin{align*} F(0) &= f(1)\\ F(x) &= f(x - 1) + f(x + 1), \quad x \in \{1, 2, \ldots, m - 1\}\\ F(m) &= f(m - 1) \end{align*}
As usual, our support assumption that \(F(x) \gt 0\) for \(x \in \N_m\) is in effect.
The rate function \(r\) of \(X\) for \((\N_m, \lfrta)\) is given by \begin{align*} r(0) &= \frac{f(0)}{f(1)}\\ r(x) &= \frac{f(x)}{f(x - 1) + f(x + 1)}, \quad x \in \{1, 2, \ldots, m - 1\}\\ r(m) &= \frac{f(m)}{f(m - 1)} \end{align*}
The reliability function \(F\) uniquely determines the density function \(f\) for some values of \(m \in \N_+\), but not others.
Suppose that \(F\) is the reliability function for \((N_m, \lfrta)\) corresponding to a density function \(f\). Then \(F\) uniquely determines \(f\) except when \(m = 2 \mod 4\).
From , note that 0 is an eigenvalue if and only if \(m\) is even. In this case, an eigenfunction \(g\) is given by \begin{align*} g(2 x) &= (-1)^x, \quad x \in \{0, 1, \ldots m / 2\} \\ g(2 x + 1) &= 0, \quad x \in \{0, 1, \ldots, m / 2 - 1\} \end{align*} If \(m\) is a multiple of \(4\) then \(\sum_{x = 0}^m g(x) = 1\). If \(m = 2 \mod 4\) then \(\sum_{x = 0}^m g(x) = 0\). So the result follows from Section 1.3.
From and it follows that the graph \((\N_m, \lfrta)\) is stochastic except when \(m = 2 \mod 4\). The graph is stochastic in the exceptional case \(m = 2\) as well. If \(P\) is a probability meaasure on the associated \(\sigma\)-algebra \(\ms A\) in , with reliability function \(F\), then \(P(\{1\}) = F(0) = F(2)\) and \(P(\{0, 2\}) = F(1)\). But of course a reliability function \(F\) of a probability measure on the reference \(\sigma\)-algebra \(\ms P(\N_2)\) does not uniquely determine that measure in general. When \(m = 2 \mod 4\) and \(m \gt 2\) then the graph \((\N_m, \lfrta)\) is non-stochastic: the associated \(\sigma\)-algebra is \(\ms P(\N_m)\) but the reliability function of a probability measure on \(\ms P(\N_m)\) does not uniquely determine that measure in general. The following result gives more detail on how to recover the density function \(f\) from the reliabiity function \(F\).
Suppose that \(m \in \N_+\) and that \(f\) is a probability density function on \(\N_m\) with reliability function \(F\) for the graph \((\N_m, \lfrta)\).
In part (a), the first equation gives \(f\) at an odd vertex in terms of \(F\) at even vertices, while the second equation gives \(f\) at an even vertex in terms of \(F\) at odd vertices. In particular, when \(m\) is odd, \(F\) uniquely determines \(f\). In part (b), the first equation once again gives \(f\) at an odd vertex in terms of \(F\) at even vertices. The second equation gives \(f\) at an even vertex in terms of \(f(0)\) and \(F\) at odd vertices. When \(m\) is not of the form \(2 \mod 4\), these equations together with the normalizing equation \(\sum_{x = 0}^m f(x) = 1\) uniquely determine \(f\). But when \(m = 4 k + 2\) for some \(k \in \N\), the normalizing equation gives no additional information since it's equivalent to \[\sum_{j = 0}^k [F(4 j) + F(4 j + 1)] = 1\] The following simple example gives two distributions with the same reliability function in the case \(m = 6\).
Define the probability density functions \(f\) and \(g\) on \(\N_6\) by \[f(1) = f(3) = f(5) = 1 / 6, \, f(0) = f(2) = f(4) = f(6) = 1 / 8 \] \[g(1) = g(3) = g(5) = 1 / 6, \, g(0) = g(4) = 1 / 12, \, g(2) = g(6) = 1 / 6 \] Then \(f\) and \(g\) have the same reliability function \(F\) for \((\N_6, \lfrta)\), given by \[F(0) = F(6) = 1 / 6, \, F(2) = F(4) = 1 / 3, \, F(1) = F(3) = F(5) = 1 / 4 \]
As always, we are particularly interested in constant rate distributions. The equations for the density \(f\) to have constant rate \(\alpha \in (0, \infty)\) for \((\N_m, \lfrta)\) are \begin{align} f(0) &= \alpha f(1) \\ f(x) &= \alpha[f(x - 1) + f(x + 1)], \quad x \in \{1, 2, \ldots, m - 1\} \\ f(m) &= \alpha f(m - 1) \end{align} and of course we also need \(f(x) \ge 0\) for \(x \in S\) and \(\sum_{x=0}^m f(x) = 1\). Here is our main result:
For each \(m \in \N_+\), there exists a unique constant rate distribution for \((\N_m, \lfrta)\). The rate is \[\alpha = \frac{1}{2 \cos\left(\frac{\pi}{m+2}\right)}\] and the density function \(f\) is given by \[f(x) = \frac{\sin\left(\frac{\pi}{m + 2}\right)}{1 + \cos\left(\frac{\pi}{m + 2}\right)} \sin\left(\frac{x + 1}{m + 2} \pi\right), \quad x \in \N_m\]
The eigenvalues of the adjacency matrix \(L\) are given in . The largest eigenvalue is \[2 \cos\left(\frac{\pi}{m + 2}\right)\] and a corresponding eigenfunction \(g\) is given by \[g(x) = \sin\left(\frac{x + 1}{m + 2} \pi\right), \quad x \in \N_m \] So the result follows from the Peron-Frobenius theorem as discussed in Section 1.5. The probability density function \(f\) is the normalized eigenfunction.
Note that the density function \(f\) of the constant rate distribution is symmetric. Clearly also \(\alpha \in \left(\frac 1 2, 1\right)\) for \(m \in \N_+\) and \(\alpha \to \frac 1 2\) as \(m \to \infty\). By symmetry, the mean of the constant rate distribution is \(m / 2\), but the variance and other higher-order moments do not have simple expressions.
Open the simulation of the constant rate distribution on the path graph \((\N_m, \lfrta)\). Vary \(m\) with the scroll bar and note the shape of the graph. For selected values of \(m\), run the simulation 1000 times and compare the empirical density function with the probability density function.
Consider the case \(m = 2\) so that \((\N_2, \lfrta)\) is the undirected simple path \((0, 1, 2)\). Find each of the following explicitly:
Consider the case \(m = 3\) so that \((\N_3, \lfrta)\) is the undirected simple path \((0, 1, 2, 3)\). Find each of the following explicitly:
Consider the case \(m = 4\) so that \((\N_4, \lfrta)\) is the undirected simple path \((0, 1, 2, 3, 4)\). Find each of the following explicitly:
Our next result gives the asymptotic behavior of the constant rate distributions.
Suppose that \(X_m\) has the constant rate distribution on \((\N_m, \lfrta)\) for each \(m \in \N_+\). Then as \(m \to \infty\), the distribution of \(X_m / m\) converges (in the usual sense) to the Gilbert's sine distribution on \([0, 1]\), with density function \[x \mapsto \frac{\pi}{2} \sin(\pi x), \quad x \in [0, 1]\]
Let \(x \in [0, 1]\). Then \begin{align*} \P(X_m / m \le x) &= \sum_{k=0}^m \bs{1}\left(\frac{k}{m} \le x\right) f(k) \\ &= \frac{\sin\left(\frac{\pi}{m+2}\right)}{1 + \cos\left(\frac{\pi}{m+2}\right)} \sum_{k=0}^m \bs{1}\left(\frac{k}{m} \le x\right) \sin\left(\frac{k+1}{m+2} \pi\right) \\ &= \left[m \frac{\sin\left(\frac{\pi}{m+2}\right)}{1 + \cos\left(\frac{\pi}{m+2}\right)}\right] \left[\frac{1}{m} \sum_{k=0}^m \bs{1}\left(\frac{k}{m} \le x\right) \sin\left(\frac{k+1}{m+2} \pi\right) \right] \end{align*} The factor in the first set of square brackets converges to \(\pi / 2\) as \(m \to \infty\) by simple calculus. The factor in the second set of square brackets is a Riemann sum for \(\int_0^x \sin(\pi u) du\) Hence \[\P(X_m / m \le x) \to \int_0^x \frac{\pi}{2} \sin(\pi u) \, du \text{ as } m \to \infty\] As a function of \(x \in [0, 1]\), the right side is the distribution function of Gilbert's sine distribution.
Open the simulation of the sine distribution and note the shape of the probability density function. Run the simulation 1000 times and compare the empirical density function to the probability density function.
The sine distribution is unimodal and is symmetric about \(\frac 1 2\). The density function is concave downward. Here are some other simple properties:
Suppose that \(X\) has the sine distribution. Then
Suppose now that \(\bs Y = (Y_1, Y_2, \ldots)\) is the random walk on the path \(\N_m, \lfrta)\) associated with the constant rate distribution. So \(Y_1\) has the constant rate distribution, and the transition probabilitiy matrix \(P\) is given by \(P(0, 1) = 1\), \(P(m, m - 1) = 1\), and \[P(x, x - 1) = \alpha \frac{f(x - 1)}{f(x)}, \; P(x, x + 1) = \alpha \frac{f(x + 1)}{f(x)}, \quad x \in \{1, 2, \ldots, m - 1\}\] where \(\alpha\) and \(f\) are given in .
The random walk \(\bs Y\) has a unique invariant distribution with density function \(h\) given by \[h(x) = \frac{2}{m + 2} \sin^2\left(\frac{x + 1}{m + 2} \pi\right), \quad x \in \N_m\]
Since the path is symmetric, it follows from our general theory that the square \(f^2\) of the constant rate density \(f\) is invariant for \(\bs Y\). Equivalently, the square \(g^2\) of the largest eigenfunction \(g\) is invariant. After some algegra, the normalizing constant for \(g^2\) is \[\sum_{x = 0}^m g^2(x) = \sum_{x = 0}^m \sin^2\left(\frac{x + 1}{m + 2} \pi\right) = \frac{m + 2}{2}\] and so the result follows.
Of course, \(h\) is also symmetric and hence has mean \(m / 2\). Once again, the variance and higher-order moments do not have simple expressions.
Open the simulation of the random walk on \((\N_m, \lfrta)\) corresponding to the constant rate distribution. The distribution graph and table display the invariant distribution, with the data corresponding to the relative frequency of visits to the states. Vary \(m\) with the scroll bar and note the shape of the graph. For selected values of \(m\), run the simulation 1000 times and compare the relative frequency function with the invariant density function. If \(m\) is large, you will notice that it takes a long time for convergence to the invariant distribution to become apparent.
Consider the case \(m = 2\) so that \((\N_2, \lfrta)\) is the undirected simple path \((0, 1, 2)\). Find each of the following explicitly:
Consider the case \(m = 3\) so that \((\N_3, \lfrta)\) is the undirected simple path \((0, 1, 2, 3)\). Find each of the following explicitly:
Consider the case \(m = 4\) so that \((\N_4, \lfrta)\) is the undirected simple path \((0, 1, 2, 3, 4)\). Find each of the following explicitly:
Our last task is to find the limit of the invariant distributions as \(m \to \infty\).
Suppose that \(X_m\) has the invariant distribution in for each \(m \in \N_+\). Then as \(m \to \infty\), the distribution of \(X_m / m\) converges (in the usual sense) to the sine square distribution on \([0, 1]\), with density function \[x \mapsto 2 \sin^2(\pi x), \quad x \in [0, 1]\]
Let \(x \in [0, 1]\). Then \begin{align*} \P(X_m / m \le x) &= \sum_{k=0}^m \bs{1}\left(\frac{k}{m} \le x\right) f(k) \\ &= \frac{2}{m + 2} \sum_{k=0}^m \bs{1}\left(\frac{k}{m} \le x\right) \sin^2\left(\frac{k + 1}{m + 2} \pi\right) \\ &= \frac{2 m}{m + 2} \left[\frac{1}{m} \sum_{k=0}^m \bs{1}\left(\frac{k}{m} \le x\right) \sin^2\left(\frac{k + 1}{m + 2} \pi\right) \right] \end{align*} The first factor converges to 2 as \(m \to \infty\). The sum is a Riemann sum for \(\int_0^x \sin^2 (\pi u) du\) Hence \[\P(X_m / m \le x) \to \int_0^x 2 \sin^2 (\pi u) \, du \text{ as } m \to \infty\] As a function of \(x \in [0, 1]\), the right side is the distribution function of the sine square distribution.
Open the simulation of the sine square distribution. Note the shape of the probability density function and compare this shape with that of the sine distribution. Run the simulation 1000 times and compare the empirical density function to the probability density function.
The sine square distribution, like the sine distribution, is unimodal and symmetric about \(\frac 1 2\). The density function is concave upward, then downward, then upward again, with inflection points at \(x = \frac 1 4\) and \(x = \frac 3 4\). Here are some other simple properties.
Suppose that \(X\) has the sine square distribution. Then