In this section we study a few graphs that can be constructed from the finite paths studied in Section 2. As in that section, let \((\N_m, \lfrta)\) denote the simple path on the \(m + 1\) vertices in \(\N_m = \{0, 1, \ldots, m\}\) vertices for \(m \in \N_+\) . That is, \(x \lfrta x + 1\) for \(x \in \{0, 1, \ldots, m - 1\}\) and \(x \lfrta x - 1\) for \(x \in \{1, 2, \ldots, m\}\). The figure below shows \((\N_{10}, \lfrta)\):
Here is a summary of the main result.
The unique constant rate distribution for \((\N_m, \lfrta)\) has rate constant \(\alpha_m\) and density function \(f_m\) given by \begin{align*} \alpha_m &= \frac{1}{2 \cos\left(\frac{\pi}{m + 2}\right)} \\ f_m(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 \end{align*}
For \(m \in \N_+\) let \((\N_m, \updna)\) denote the reflexive closure of \((\N_m, \lfrta)\) as defined in Section 1.6. So \(x \updna y\) if and only if \(x = y\) or \(x \lfrta y\) for \(x, \, y \in \N_m\).
In short, we add a loop at each vertex in the path.
The unique constant rate distribution for \((\N_m, \updna)\) has density function \(f_m\) given in Proposition and rate constant \[\beta_m = \frac{1}{1 + 2 \cos\left(\frac{\pi}{m + 2}\right)}\]
That \(f_m\) is the density of a distribution with constant rate \(\beta_m\) follows from and results in Section 1.6. The constant rate distribution is unique since \((\N_m, \updna)\) is finite and strongly connected.
Note that \(\beta_m \in (1 / 3, 1)\) for \(m \in \N_+\) and \(\beta_m \to 1 / 3\) as \(m \to \infty\). If random variable \(X_m\) in \(\N_m\) has the constant rate distribution for \((\N_m, \updna)\) then \(X_m\) also has constant rate (but with a different constant) for \((\N_m, \lfrta)\). Hence from Section 2, the distribution of \(X_m / m\) converges to the sine distribution as \(m \to \infty\).
Consider the case \(m = 2\) so that \((\N_2, \updna)\) is the undirected path \((0, 1, 2)\) with loops. Find the rate constant \(\beta_2\) and the probability density function \(f_2\) of the constant rate distribution explicitly.
\[\beta_2 = \frac{1}{1 + \sqrt{2}} \approx 0.414\] \begin{align*} f_2(0) &= f_2(2) = \frac{1}{2 + \sqrt{2}} \approx 0.293\\ f_2(1) &= \frac{\sqrt{2}}{2 + \sqrt{2}} \approx 0.414 \end{align*}
Consider the case \(m = 3\) so that \((\N_3, \updna)\) is the undirected path \((0, 1, 2, 3)\) with loops. Find the rate constant \(\beta_3\) and the probability density function \(f_3\) of the constant rate distribution explicitly.
\[\beta_3 = \frac{\sqrt{5} - 1}{\sqrt{5} + 1} \approx 0.382\] \begin{align*} f_3(0) &= f_3(3) = \frac{3 - \sqrt{5}}{4} \approx 0.191\\ f_3(1) &= f_3(2) = \frac{\sqrt{5} - 1}{4} \approx 0.309 \end{align*}
Consider the case \(m = 4\) so that \((\N_4, \updna)\) is the undirected path \((0, 1, 2, 3, 4)\) with loops. Find the rate constant \(\beta_4\) and the probability density function \(f_3\) of the constant rate distribution explicitly.
\[\beta_4 = \frac{1}{\sqrt{3} + 1} \approx 0.366\] \begin{align*} f_4(0) &= f_4(4) = \frac{1}{4 + 2 \sqrt{3}} \approx 0.134\\ f_4(1) &= f_4(3) = \frac{3}{6 + 4 \sqrt{3}} \approx 0.232\\ f_4(2) &= \frac{1}{2 + \sqrt{3}} \approx 0.268 \end{align*}
For \(m \in \N_+\), let \((C_m, \lfrta)\) denote the graph obtained from \((\N_m, \lfrta)\) by endpoint addition as described in Section 1.10. That is, \(C_m = \N_m \cup \{t_x: x \in \N_m\}\) where \(\{t_x: x \in \N_m\}\) is a set of \(m + 1\) distinct points, disjoint from \(\N_m\). The relation \(\lfrta\) is extended from \(\N_m\) to \(C_m\) by \(x \lfrta t_x\) for each \(x \in \N_m\).
So \((C_m, \lfrta)\) is a type of caterpillar graph and can also be viewed as a path on \(m + 3\) vertices with an endpoint attached to each of the \(m - 1\) interior vertices of \((\N_m, \lfrta)\).
The caterpillar graph \((C_m, \lfrta)\) has a unique constant rate distribution.
The results follow from the more general results in Section 1.10. Once again, the uniqueness of the constant rate distribution follows since \((C_m, \lfrta)\) is a finite, strongly connected graph.
Note that \(\delta_m \in (\sqrt{2} - 1, (\sqrt{5} - 1) / 2)\) for \(m \in \N_+\), and that \(\delta_m \to \sqrt{2} - 1\) and \(p_m \to 1 / \sqrt{2}\) as \(m \to \infty\). Moreover, \(f_m\) is symmetric on \(\N_m\) from Section 2, so \(g_m\) has a natural symmetry property as well: \[g_m(x) = g_m(m - x), \; g_m(t_x) = g_m(t_{m - x}); \quad x \in \N_m\]
The caterpillar graph \((C_1, \lfrta)\) is isomorphic to \((\N_3, \lfrta)\). That is, if we add an endpoint to each of the two vertices in a path of length 1 we simply get a path of length 3. As a check on our work, compute the rate constant \(\delta_1\) and the density function \(g_1\) of the constant rate distribuition using the results in , and compare to \(\alpha_3\) and \(f_3\).
Recall that \(\alpha_1 = 1\). Hence \(\delta_1 = (\sqrt{5} - 1) / 2 = \alpha_3\). Moreover, \(p_1 = (\sqrt{5} - 1) / 2\) and \(f_1(0) = f_1(1) = 1 / 2\) so \begin{align*} g_1(t_0) & = (1 - p_1) f_1(0) = \frac{3 - \sqrt{5}}{4} = f_3(0) \\ g_1(0) & = p_1 f_1(0) = \frac{\sqrt{5} - 1}{4} = f_3(1) \\ g_1(1) & = p_1 f_1(1) \frac{\sqrt{5} - 1}{4} = f_3(2) \\ g_1(t_1) & = (1 - p_1) f_1(1) = \frac{3 - \sqrt{5}}{4} = f_3(3) \end{align*}
For the caterpillar graph \((C_2, \lfrta)\), find the rate constant \(\delta_2\) and the density \(g_2\) of the constant rate distribtuion explicitly.
Recall that \(\alpha_2 = 1 / \sqrt{2}\). Hence \(\delta_2 = (\sqrt{3} - 1) / \sqrt{2}\). Moreover, \(p_2 = \sqrt{2} / (\sqrt{2} + \sqrt{3} -1)\) and \(f_2(0) = f_2(2) = 1 / (2 + \sqrt{2})\) and \(f_2(1) = \sqrt{2} / (2 + \sqrt{2})\) so \begin{align*} g_2(t_0) = g_2(t_2) & = \frac{\sqrt{3} - 1}{\sqrt{2} + 2 \sqrt{3} + \sqrt{6}} \\ g_2(0) = g_2(2) & = \frac{\sqrt{2}}{\sqrt{2} + 2 \sqrt{3} + \sqrt{6}} \\ g_2(1) & = \frac{2}{\sqrt{2} + 2 \sqrt{3} + \sqrt{6}} \\ g_2(t_1) & = \frac{\sqrt{6} - \sqrt{2}}{\sqrt{2} + 2 \sqrt{3} + \sqrt{6}} \end{align*}
For \(m \in \N_+\), let \((\N_m \cup \{t\}, \lfrta)\) denote the graph obtained from \((\N_m, \lfrta)\) by the addition of a univeral point \(t \notin \N_m\) as defined in Section 1.10. That is, the relation \(\lfrta\) is extended from \(\N_m\) to \(\N_m \cup \{t\}\) by \(t \lfrta x\) for every \(x \in \N_m\).
The graph \((\N_m \cup \{t\}, \lfrta)\) is a cone graph and in this context is a fan graph. It is also the join of the path \((\N_m, \lfrta)\) with the point graph that with vertex \(t\) and no edges.
For \(m \in \N_+\), the fan graph \((\N_m \cup \{t\}, \lfrta)\) has a unique constant rate distribution. The rate constant \(\gamma_m\) is the largest root of the characteristic equation \[\gamma^3 - (m + 1) \gamma - 2 m = 0\]
We cannot give more explicit results for the rate constant or the density function \(h_m\) of the constant rate distribution. Of course, \(h_m\) is symmetric on \(\N_m\) so \(h_m(x) = h_m(m - x)\) for \(x \in \N_m\).
Grid graphs are graphs constructed from the finite paths by means of Cartesian product as studied in Section 1.8.
For \(m, \, n \in \N_+\), the \(m \times n\) grid graph \((\N_m \times \N_n, \Lfrta)\) is the Cartesian (graph) product of the path graphs \((\N_m, \lfrta)\) and \((\N_n, \lfrta)\). That is, \((x, y) \Lfrta (z, w)\) if and only if \(x \lfrta z\) and \(y = w\), or \(x = z\) and \(y \lfrta w\) for \((x, y), \, (z, w) \in \N_m \times \N_n\).
Here is the main result on constant rate distributions:
For \(m, \, n \in \N_+\), the \(m \times n\) grid graph \((\N_m \times \N_n, \Lfrta)\) has a unique constant rate distribution. If \(X\) has constant rate \(\alpha_m\) for \((\N_m, \lfrta)\) and \(Y\) has constant rate \(\alpha_n\) for \((\N_n, \lfrta)\) and if \(X\) and \(Y\) are independent, then \((X, Y)\) has constant rate \(\alpha_m \alpha_n / (\alpha_m + \alpha_n)\) for \((\N_m \times \N_n, \Lfrta)\).
This follows from results in Section 1.8. The constant rate distribution is unique since \(\left(\N_m \times \N_n, \Lfrta\right)\) is finite and strongly connected. Note that the rate constant is \[\frac{\alpha_m \alpha_n}{\alpha_m + \alpha_n} = \frac{1}{2 \cos\left(\frac{\pi}{m + 2}\right) + 2 \cos \left(\frac{\pi}{n + 2}\right)}\] and the density function \(f_{m,n}\) of the constant rate distribution is given by \begin{align*} f_{m,n}(x, y) &= f_m(x) f_n(y) \\ &= \frac{\sin\left(\frac{\pi}{m + 2}\right) \sin\left(\frac{\pi}{n + 2}\right)}{\left[1 + \cos\left(\frac{\pi}{m + 2}\right)\right] \left[1 + \cos\left(\frac{\pi}{n + 2}\right) \right]} \sin\left(\frac{x + 1}{m + 2} \pi \right) \sin\left(\frac{y + 1}{n + 2} \pi \right), \quad (x, y) \in \N_m \times \N_n \end{align*}
We can also consider the direct product as defined in Section 1.8.
For \(m, \, n \in \N_+\), the direct product of the path graphs \((\N_m, \lfrta)\) and \((\N_n, \lfrta)\) is the graph \((\N_m \times \N_n, \Lfrta)\) where \((x, y) \Lfrta (z, w)\) if and only if \(x \lfrta z\) and \(y \lfrta w\) for \((x, y), \, (z, w) \in \N_m \times \N_n\).
The following result parallels .
Consider the direc product graph \((\N_m \times \N_n, \Lfrta)\) where \(m, \, n \in \N_+\). If \(X\) has constant rate \(\alpha_m\) on \((\N_m, \lfrta)\), and \(Y\) has constant rate \(\alpha_n\) on \((\N_n, \lfrta)\), and if \(X\) and \(Y\) are independent, then \((X, Y)\) has constant rate \(\alpha_m \alpha_n\) on \((\N_m \times \N_n, \Lfrta)\).
The follows immediately from results in Section 1.8.
However, the direct product of two paths always has two components.
The graph \((\N_m \times \N_n, \Lfrta)\) has two (disjoint) connected components:
If the number of vertices \((m + 1)(n + 1)\) is even then the two components are isomorphic.
The neighbors of \((x, y) \in \N_m \times \N_n\) form a subset of \(\{(x + 1, y + 1), (x - 1, y + 1), (x + 1, y - 1), (x - 1, y - 1)\}\). The sum of the coordinates of each of these points has the same parity (even or odd) as \(x + y\). Hence there are two components. If \(x + y\) is even then \((x, y)\) is connected to \((0, 0)\). If \(x + y\) is odd then \((x, y)\) is connected to \((1, 0)\). If the number of points \((m + 1)(n + 1)\) is even, the two component graphs are isomorphic by the symmetry of the paths. If \((m + 1)(n + 1)\) is odd, then \(S_0\) has one more point than \(S_1\) and so the components are not isomorphic
Because the direct product has two connected components, it actually has a one-parameter family of constant rate distributions.
Consider again the direct product graph \((\N_m \times \N_n, \Lfrta)\) where \(m, \, n \in \N_+\). All constant rate distributions have rate \(\alpha_m \alpha_n\). Moreover, \((X, Y)\) has constant rate on \((\N_m \times \N_n, \Lfrta)\) if and only if for \(i \in \{0, 1\}\), the conditional distribution of \((X, Y)\) given \((X, Y) \in S_i\) has constant rate \(\alpha_m \alpha_n\) on \((S_i, \Lfrta)\) with density function defined by \[(x, y) \mapsto \frac{f_m(x) f_n(y)}{C_i}, \quad (x, y) \in S_i \text{ where } C_i = \sum_{(x, y) \in S_i} f_m(x) f_n(y)\]
\((X, Y)\) has constant rate on \((\N_m \times \N_n)\) if and only if the conditional distribution of \((X, Y)\) given that \((X, Y) \in S_i\) has constant rate on \((S_i, \Lfrta)\), with the same constant. Moreover, the components are strongly connected and hence each has a unique constant rate distribution. Since we know by that a distribution with constant rate \(\alpha_m \alpha_n\) exists, it follows that all constant rate distributions have this same rate. So if \((X, Y)\) has constant rate on \((\N_m \times \N_n, \Lfrta)\) then \((X, Y)\) density function \(f\) of the form \begin{align*} f(x, y) &= p \frac{f_m(x) f_n(y)}{C_0}, \quad (x, y) \in S_0\\ f(x, y) &= (1 - p) \frac{f_m(x) f_n(y)}{C_1}, \quad (x, y) \in S_1 \end{align*} where \(p = \P[(X, Y) \in S_0] \in (0, 1)\). Note that \(C_1 = 1 - C_0\). Hence if \(p = C_0\) then \(X\) and \(Y\) are independent. If the number of points \((m + 1)(n + 1)\) is even then \(C_0 = C_1 = \frac 1 2\) since the two components are isomorphic.
It's interesting that as a consequence of , we can identify the rate constant and density function of the constant rate distribution for any graph that is a component of \((\N_m \times \N_n, \Lfrta)\) for some \(m, \, n \in \N_+\).
The following examples give more complete results in some special cases.
For \(n \in \N_+\), the components of \((\N_1 \times \N_n, \Lfrta)\) are two paths of length \(n\). Describe the graph in more detail and find all constant rate distributions.
Component 0 is the path \((0, 0) \Lfrta (1, 1) \Lfrta (0, 2) \Lfrta \cdots \Lfrta (x, n)\) where \(x = 0\) if \(n\) is even and \(x = 1\) if \(n\) is odd. Component 1 is the path \((1, 0) \Lfrta (0, 1) \Lfrta (1, 2) \Lfrta \cdots \Lfrta (x, n)\) where \(x = 1\) if \(n\) is even and \(x = 0\) if \(n\) is odd. Constant rate distributions have rate 1 and density function \(f\) of the form \(f(x, y) = p f_n(y)\) for \((x, y) \in S_0\) and \(f(x, y) = (1 - p) f_n(y)\) for \((x, y) \in S_1\), where \(p \in (0, 1)\). The distribution with independent coordinates corresponds to \(p = \frac 1 2\).
The components of \((\N_2 \times \N_2, \Lfrta)\) are a 4-star and a 4-cycle. Describe the graph in more detail and find all constant rate distributions.
Component 0 is a star with center \((1, 1)\) and endponts \((0, 0)\), \((0, 2)\), \((2, 0)\) and \((2, 2)\). Component 1 is the cycle with vertices \((0, 1)\), \((1, 0)\), \((1, 2)\) and \((2, 1)\). Constant rate distributions have rate \(\frac 1 2\) and density function \(f\) of the form \(f(x, y) = p / 4\) for \((x, y)\) on the cycle, \(f(x, y) = (1 - p) / 6\) for an endpoint \((x, y)\) of the star, and \(f(1, 1) = (1 - p) / 3\) for the center of the star, where \(p \in (0, 1)\). The distribution with independent coordinates corresponds to \(p = 4 / (4 + 3 \sqrt 2)\).
The components of \((\N_2 \times \N_3, \Lfrta)\) are isomorphic and consist of a 4-cycle with two endpoints attached to a vertex on the cycle. Describe the graph in more detail and find all constant rate distributions.
Component 0 consists of the cycle connecting \((1, 1)\), \((0, 2)\), \((1, 3)\), and \((2, 2)\), with \((0, 0)\) and \((2, 0)\) attached to \((1, 1)\) as endponts. Component 1 consists of the cycle connecting \((1, 0)\), \((0, 1)\), \((1, 2)\), and \((2, 1)\), with \((0, 3)\) and \((2, 3)\) attached to \((1, 2)\) as endponts. Constant rate distributions have rate \[\alpha_2 \alpha_3 = \frac{\sqrt{5} - 1}{2 \sqrt{2}}\] and density function \(f\) of the following form, where \(p \in (0, 1)\): \begin{align*} f(0, 0) = f(2, 0) &= p \frac{3 - \sqrt{5}}{4 + 2 \sqrt{2}} \\ f(0, 2) = f(2, 2) &= p \frac{\sqrt{5} - 1}{4 + 2 \sqrt{2}} \\ f(1, 3) &= p \frac{3 - \sqrt{5}}{2 + 2 \sqrt{2}} \\ f(1, 1) &= p \frac{\sqrt{5} - 1}{2 + 2 \sqrt{2}} \\ f(0, 1) = f(2, 1) &= (1 - p) \frac{\sqrt{5} - 1}{4 + 2 \sqrt{2}} \\ f(0, 3) = f(2, 3) &= (1 - p) \frac{3 - \sqrt{5}}{4 + 2 \sqrt{2}} \\ f(1, 0) &= (1 - p) \frac{3 - \sqrt{5}}{2 + 2 \sqrt{2}} \\ f(1, 2) &= (1 - p) \frac{\sqrt{5} - 1}{2 + 2 \sqrt{2}} \end{align*} The distribution with independent coordinates corresponds to \(p = \frac 1 2\).