In this brief section, we study a simple construction that is helpful for the analysis of discrete graphs. To begin, suppose that \((S, \rta)\) is a discrete, irreflexive graph, so in the combinatorial sense, a graph with no loops.
Recall that the reflexive closure of \((S, \rta)\) is the graph \((S, \lrta)\) where \(x \lrta y\) if and only if \(x = y\) or \(x \rta y\) for \(x, \, y \in S\).
That is, we simply add a loop at each vertex so that \((S, \lrta)\) is the union of \((S, \rta)\) and \((S, =)\). Equivalently, we could start with a discrete, reflexive graph \((S, \lrta)\) and remove the loops to form the irreflexive graph \((S, \rta)\). Recall that this is irreflexive reduction of \((S, \lrta)\) and is the difference between \((S, \lrta)\) and \((S, =)\). Recall in particular that if \((S, \prec)\) is a strict partial order graph (anti-reflexive, asymmetric, and transitive) then the reflexive closure is \((S, \preceq)\), the corresponding partial order graph (reflexive, anti-symmetric, and transitive). We will use our usual notation for mathematical objects related to the graphs \((S, \rta)\) and \((S, \lrta)\), but with the addition of a circumflex for the latter. The following result connects the walk functions for \((S, \rta)\) and \((S, \lrta)\).
Let \(u_n\) and \(\hat u_n\) denote the left walk functions of order \(n \in \N\), for \((S, \rta)\) and \((S, \lrta)\) respectively. Then for \(x \in S\), \begin{align*} \hat u_n(x) &= \sum_{k = 0}^n \binom{n}{k} u_k(x) \\ u_n(x) &= \sum_{k = 0}^n (-1)^{n - k} \binom{n}{k} \hat u_k(x) \end{align*}
Let \(n \in \N_+\) and \(x \in S\). Consider a walk \(\bs{x} = (x_1, x_2, \ldots, x_k, x_{k + 1})\) of length \(k\) in \((S, \rta)\), where \(k \in \N\), \(k \le n\), and \(x_{k + 1} = x\) (so the walk ends at \(x\)). Since \(\rta\) is anti-reflexive, \(x_{j + 1} \ne x_j\) for \(j \in \{1, 2, \ldots k\}\). To construct a walk \(\bs y\) of length \(n\) in \((S, \lrta)\) that ends in \(x\), we can add \(n - k\) loops to the walk \(\bs x\). Conversely, every walk of length \(n\) in \((S, \lrta)\) that ends in \(x\) must have this form for some \(k \le n\). In the walk \(\bs y\), let \(a_j\) be the number of repetitions (loops) of \(x_j\) for \(j \in \{1, 2, \ldots, k + 1\}\). Then \(a_j\) is a nonnegative integer and \(\sum_{j = 1}^{k + 1} a_j = n - k\). The number of solutions is \[\binom{(k + 1) + (n - k) - 1}{n - k} = \binom{n}{k}\] By definition, there are \(u_k(x)\) walks of length \(k\) in \((S, \rta)\) that end in \(x\), so it follows that the number of walks of length \(n\) for \((S, \lrta)\) that end in \(x\) is \[\hat u_n(x) = \sum_{k=0}^n \binom{n}{k} u_k(x)\] The second result follows from the first by the binomial inversion formula.
In the case that \(S\) is finite, the right walk functions \(v_n\) and \(\hat v_n\) of order \(n \in \N\), and the walk parameters \(w_n\) and \(\hat w_n\) of order \(n\) are related in a similar way. That is, \begin{align*} \hat v_n(x) &= \sum_{k = 0}^n \binom{n}{k} v_k(x) \\ v_n(x) &= \sum_{k = 0}^n (-1)^{n - k} \binom{n}{k} \hat v_k(x) \\ \hat w_n &= \sum_{k = 0}^n \binom{n}{k} w_k \\ w_n &= \sum_{k = 0}^n (-1)^{n - k} \binom{n}{k} \hat w_k \end{align*} So then the right walk density function \(\hat d_n\) of order \(n\) for \((S, \lrta)\) is a convex combination of the right walk density functions \(\{d_0, d_1, \ldots, d_n\}\) of \((S, \rta)\).
Suppose that \(S\) is finite. For \(n \in \N\) and \(x \in S\), \(\hat d_n(x) = \sum_{k = 0}^n p_{n, k} d_k(x)\) where \[p_{n, k} = \frac{\binom{n}{k} w_k}{\sum_{j = 0}^n \binom{n}{j} w_j}, \quad k \in \{0, 1, \ldots, n\}\]
The left generating functions are also related in a simple way.
Suppose that \(U\) and \(\hat U\) denote the walk generating functions for \((S, \rta)\) and \((S, \lrta)\), with convergence functions \(\rho\) and \(\hat \rho\), respectively. Then for \(x \in S\), \begin{align*} \hat U(x, t) & = \frac{1}{1-t} U \left(x, \frac{t}{1-t}\right), \quad \hat \rho(x) = \frac{\rho(x)}{1 + \rho(x)} \\ U(x, t) & = \frac{1}{1 + t} \hat U\left(x, \frac{t}{1 + t}\right), \quad \rho(x) = \frac{\hat \rho(x)}{1 - \hat \rho(x)} \end{align*}
For \(x \in S\), \begin{align*} \hat U(x, t) &= \sum_{n = 0}^\infty \hat u_n(x) t^n = \sum_{n = 0}^\infty \sum_{k = 0}^n \binom{n}{k} u_k(x) t^n \\ &= \sum_{k = 0}^\infty u_k(x) \sum_{n = k}^\infty \binom{n}{k} t^n = \sum_{k = 0}^\infty u_k(x) \frac{t^k}{(1 - t)^{k + 1}} \\ &= \frac{1}{1 - t} \sum_{k = 0}^\infty u_k(x) \left(\frac{t}{1 - t}\right)^k = \frac{1}{1 - t} U\left(x, \frac{t}{1 - t}\right) \end{align*} The series converges when \(|t / (1 - t)| \le \rho(x)\). Solving \(t / (1 - t) = \rho(x)\) for \(t\) gives \(\hat \rho(x) = \rho(x) / [1 + \rho(x)]\). It should be understood that \(\hat \rho(x) = 1\) if \(\rho(x) = \infty\).
The second result follows from the first. For \(t \in \R\), let \(s = t / (1 + t)\) so that \(t = s / (1 - s)\). Then \[U(x, t) = U\left(x, \frac{s}{1 - s}\right) = (1 - s) \hat U(x, s) = \frac{1}{1 + t} \hat U\left(x, \frac{t}{1 + t}\right)\] Solving \(t / (1 + t) = \hat \rho(x)\) for \(t\) gives \(\rho(x) = \hat \rho(x) / [1 - \hat \rho(x)]\). It should be understood that \(\rho(x) = \infty\) if \(\hat \rho(x) = 1\).
Suppose now that \(X\) is a random variable in \(S\). There are very simple relationships between the reliability functions, rate functions, and generating functions of \(X\) with respect to \((S, \rta)\) and \((S \lrta)\). This in turn leads to a simple relationship between the constant rate distributions for the two graphs (if they exist). As usual, we assume that \(X\) is supported by the graph \((S, \rta)\) (and as we will see below, supported also by \((S, \lrta)\)).
Suppose that \(X\) is supported by \((S, \rta)\).
As usual, we are particularly interested in constant rate distributions.
Suppose again that \(X\) is supported by \((S, \rta)\). Then
Note that \(\hat r \lt 1\). Also, there is a one-to-one correspondence between constant rate distributions for \((S, \rta)\) and \((S, \lrta)\). The respective rate constants \(\alpha\) and \(\beta\) satisfy \(1 / \beta - 1 / \alpha = 1\), a bit reminiscent of conjugate exponents. In particular, a constant rate distribution exists for \((S, \rta)\) if and only if a constant rate distribution exists for \((S, \lrta)\).
Suppose that \(X\) is a random variable on \(S\) as above. Let \(\bs Y = (Y_1, Y_2, \ldots)\) and \(\bs{\hat Y} = (\hat Y_1, \hat Y_2, \ldots)\) denote the random walks on \((S, \rta)\) and \((S, \lrta)\) associated with \(X\), respectively. The transition densities are also related in a simple way.
Let \(P\) and \(\hat P\) denote the transition densities of \(\bs Y\) and \(\bs{\hat Y}\), respectively.
As before, let \(F\) and \(\hat F\) denote the reliability functions of \(f\) for \((S, \rta)\) and \((S, \lrta)\), respectively. If \(x \lrta y\) then \[\hat P(x, y) = \frac{f(y)}{\hat F(x)} = \frac{f(y)}{f(x) + F(x)} = \frac{f(y) / F(x)}{f(x) / F(x) + 1} = \frac{f(y) / F(x)}{r(x) + 1}\] Part (a) follows since \(x \lrta y\) if and only if \(x = y\) or \(x \rta y\). Part (b) follows from part (a).
As a corollary, the higher order-density functions for \((S, \lrta)\) and \((S, \rta)\) have a simple relationship when the underlying random variable has constant rate.
For \(n \in \N_+\), let \(f_n\) and \(\hat f_n\) denote the density functions of \(Y_n\) and \(\hat Y_n\), respectively.
The proof uses the general formula for the higher-order densities in Section 5
Finally, recall that \(\bs N = \{N_A: A \in \ms S\}\) and \(\bs{\hat N} = \{\hat N_A: A \in \ms S\}\) are the point processes corresponding to the random walks \(\bs Y\) and \(\bs{\hat Y}\), respectively.
Suppose that \(X\) has constant rate \(\alpha \in (0, \infty)\) for \((S, \rta)\). Then \[\E(\hat N_A) = (1 + \alpha) \E(N_A), \quad A \in \ms S\]
Since \(X\) has constant rate \(\alpha \in (0, \infty)\) for \((S, \rta)\), \(X\) has constant rate \(\beta = \alpha / (\alpha + 1) \in (0, 1)\) for \((S, \lrta)\). Hence using the result in Section 5 and above, \begin{align*} \E(\hat N_A) &= \E[\hat U(X, \beta), X \in A] = \E\left[\frac{1}{1 - \beta} U\left(X, \frac{\beta}{1 - \beta}\right), X \in A\right]\\ &= (1 + \alpha) \E(U(X, \alpha), X \in A) = (1 + \alpha) \E(N_A) \end{align*}
Suppose that the finite, irreflexive graph \((S, \rta)\) is regular of degree \(k \in \N_+\), so that the reflexive closure \((S, \lrta)\) is regular of dgree \(k + 1\). In this simple case, verify each of the following:
Suppose that \(S\) is a nonempty countable set. The graph \((S, \ne)\) is the complete irrefexive graph on \(S\). The reflexive closure \((S, \equiv)\) is the complete reflexive graph on \(S\), so that \(x \equiv y\) for all \(x, \, y \in S\). Find the \(\sigma\) algebra associated with each graph.
For \(x \in S\), the neighbor set of \((S, \ne)\) at \(x\) is \(A_x = S - \{x\}\) while the neighbor set of \((S, \equiv)\) at \(x\) is \(B_x = S\). So the \(\sigma\)-algebra associated with \((S, \ne)\) is \(\ms A = \ms P(S)\), the collection of all subsets of \(S\). The \(\sigma\)-algebra associated with \((S, \equiv)\) is the trivial \(\sigma\)-algebra \(\ms B = \{\emptyset, S\}\).
In general, there is no simple relationship between the \(\sigma\)-algebra associated with the original irreflexive graph and the \(\sigma\)-algebra associated with the reflexive closure. If \(S\) in example is finite with \(k \in \N_+\) points, then \((S, \ne)\) is regular of degree \(k - 1\) while \((S, \equiv)\) is regular of degree \(k\), so applies.
Suppose that \((S, \preceq)\) is a discrete partial order graph. As noted earlier, \((S, \prec)\) is the corresponding strict partial order graph, and \((S, \preceq)\) is the reflexive closure of \((S, \prec)\). Recall that the covering graph \((S, \upa)\) is defined by \(x \upa y\) if and only if \(y\) covers \(x\) for \(x, \, y \in S\). That is, \(x \prec y\) and no \(z \in S\) satisfies \(x \prec z \prec y\). Let \((S, \Upa)\) denote the reflexive closure of \((S, \upa)\) so that \(x \Upa y\) if and only if \(x = y\) or \(y\) covers \(x\). In Section 2 we showed that if \((S, \preceq)\) is well founded then the \(\sigma\)-algebra associated is \((S, \preceq)\) is \(\ms P(S)\), the reference \(\sigma\)-algebra. The same is true of \((S, \Upa)\).
If \((S, \preceq)\) is well founded then the \(\sigma\)-algebra associated with \((S, \Upa)\) is \(\ms P(S)\).
The neighbor set of \(x \in S\) for \((S, \Upa)\) is \(A_x = \{x\} \cup \{y \in S: x \upa y\}\). Since the graph is well founded, \[ \{x\} = A_x \setminus \bigcup_{x \upa y} A_ y, \quad x \in S\]
Suppose now that \((S, \preceq)\) has minimum element \(e\). Let \(S_+ = S - \{e\}\). Then \((S_+, \preceq)\) is a sub-graph of \((S, \preceq)\) and \((S_+, \prec)\) is a sub-graph of \((S, \prec)\), and the former is the reflexive closure of the latter.
Suppose now that \(X\) is a random variable on \(S\) with probability density function \(f\).
With the notation in place, the following corollaries are a summary of our results:
Suppose that \(X\) has constant rate \(\alpha \in (0, \infty)\) for \((S, \prec)\).
Consider the reflexive closure \((S, \Lfrta)\) of the diamond graph \((S, \lfrta)\) introduced in Section 1 and shown below.