In this section we study a few graphs that can be constructed from the finite paths studied in Section 3. 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\}\). 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.
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\).
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\).