In this brief section, we study another simple construction that is helpful for the analysis of discrete graphs, particularly the interesting collection of binomial trees.
Suppose that \((S, \rta)\) is a discrete, graph, so a graph in the combinatorial sense. Let Let \(T = S \cup S^\prime\) where \(S^\prime = \{u_x: x \in S\}\) where is a distinct set of elements, disjoint from \(S\) and indexed by \(x \in S\). Define the relation \(\Rta\) on \(T\) by
The graph \((T, \Rta)\) is the graph obtained from \((S, \rta)\) by endpoint addition.
That is, we simply add an endpoint \(u_x\) to \(x \in S\) by an undirected edge for each \(x \in S\). If the original graph \((S, \rta)\) is symmetric (undirected) then so is \((T, \Rta)\). Given a probability distribution on \(S\), there is a natural way to construct a probability distribution on \(T\).
Suppose that \(X\) is a random variable in \(S\). For \(p \in (0, 1)\), let \(Y\) be the random variable in \(T\) defined as follows: \[ \P(Y = x \mid X = x) = p, \; \P(Y = u_x \mid X = x) = 1 - p, \quad x \in S \]
So in particular, \(\P(Y \in S) = p\) and \(\P(Y \in S^\prime) = 1 - p\). Our main result is that if \(X\) has constant rate for \((S, \rta)\) then with an appropriate choice of \(p\), \(Y\) has constant rate for \((T, \Rta)\).
Suppose that \(X\) has constant rate \(\alpha \in (0, \infty)\) for \((S, \rta)\). Let \begin{align*} \beta &= \frac{\sqrt{4 \alpha^2 + 1} - 1}{2 \alpha} \\ p &= \frac{1}{1 + \beta} = \frac{2 \alpha}{\sqrt{4 \alpha^2 + 1} + (2 \alpha - 1)} \end{align*} Then random variable \(Y\) with parameter \(p\) constructed in Proposition has constant rate \(\beta\) for \((T, \Rta)\).
Let \(x \in S\). Using Proposition and the fact that \(X\) has constant rate \(\alpha\) for \((S, \rta)\) we have \[g(x) = \frac{1}{1 + \beta} f(x) = \frac{\alpha}{1 + \beta} F(x) = \alpha \left[G(x) - \frac{\beta}{1 + \beta} f(x) \right] = \alpha [G(x) - \beta g(x)]\] Hence \[g(x) = \frac{\alpha}{1 + \alpha \beta} G(x) = \beta G(x)\] The last equality holds since \(\beta\) is defined by the quadratic equation \(\alpha \beta^2 + \beta - \alpha = 0\). Next, \[g(u_x) = \frac{\beta}{1 + \beta} f(x) = \beta g(x) = \beta G(u_x), \quad x \in S\]
In the context of Proposition ,
By simple calculus, note that \(\beta\) increases and \(p\) decreases as \(\alpha\) increases and that \(\beta \to 0\) and \(p \to 1\) as \(\alpha \to 0\) while \(\beta \to 1\) and \(p \to \frac{1}{2}\) as \(\alpha \to \infty\). We can recursively add endpoints to a given graph.
Suppose that \((S_1, \rta_1)\) is a discrete graph with constant rate \(\alpha_1 \in (0, \infty)\). Recursivle, for \(n \in \N_+\), let \((S_{n + 1}, \rta_{n + 1})\) denote the graph obtained from \((S_n, \rta_n)\) by endpoint addition as in Proposition . So this graph has constant rate \[ \alpha_{n + 1} = \frac{\sqrt{4 \alpha_n^2 + 1} - 1}{2 \alpha_n}, \quad n \in \N_+ \]
In the context of Proposition , \(\alpha_n \to 0\) as \(n \to \infty\).
By construction, \(\alpha_{n + 1} = \varphi(\alpha_n)\) for \(n \in \N_+\) where \[ \varphi(t) = \frac{\sqrt{4 t^2 + 1} - 1}{2 t}, \quad t \in (0, \infty)\] We define \(\varphi(0) = 0\) so that \(\varphi\) is continuous on \([0, \infty)\). So then \(\alpha_n\) is decreasing in \(n\) and converges to the only fixed point of \(\varphi\), namely 0.
The most important application of endpoint addition is to binomial trees, since these trees are generated recursivley precisely by this method.
The (undirected) binomial trees are defined recursively as follows:
The binomial tree of order \(n \in \N_+\) has \(2^n\) vertices.
So the vertices of the binomial tree of order \(n \in \N_+\) can be labeled with bit strings of length \(n\). It helps to have a consistent way to do that.
The vertices of the binomial trees are labeled with bit strings as follows:
The following result identifies the degrees of the vertices in the binomial tree. To state the result succinctly, let \(1^{(j)}\) denote the string with 1 repeated \(j\) times \(j \in \N_+\). Let \(1^{(0)}\) denote the empty string.
Let \((B_n, \lfrta_n)\) denote the binomial tree of order \(n \in \N_+\), labeled as in Proposition .
In particulr, the binomial tree of order \(n \ge 2\) has \(2^{n - 1}\) endpoints. It's now easy to describe the probability distributions on the binomial trees generated recursively by the construction in Definition . A bit of additional notation will help. For \(p \in (0, 1)\), let \(p(0) = 1 - p\) and \(p(1) = p\).
Let \(X_0\) have the point mass distribution on the single vertex in the binomial tree of order 0. For \(n \in \N\), let \(X_{n + 1}\) have the distribution on (\(B_{n + 1}, \lfrta_{n + 1})\) constructed from the distribution of \(X_n\) on \((B_n, \lfrta_n)\) as in Definition , with parameter \(p_{n + 1} \in (0, 1)\). Then the random bits \(I_1 I_2 \cdots I_n\) of \(X_n\) are independent Bernoulli variables and \(I_k\) has parameter \(p_k\) for \(k \in \{1, 2, \ldots, n\}\). That is, the probability density function \(f_n\) of \(X_n\) is given by \[f_n(i_1 i_2 \cdots i_n) = p_1(i_1) p_2(i_2) \cdots p_n(i_n), \quad i_1 i_2 \cdots i_n \in \{0, 1\}^n \]
If \(p_k = p \in (0, 1)\) for \(k \in \N_+\) then the bits of \(X_n\) are a sequence of \(n\) Bernoulli trials with parameter \(p\) for \(n \in \N_+\). The following result gives the distribution of the degree of \(X_n\).
For \(n \in \N_+\) let \(X_n\) denote the random variable on \((B_n, \lfrta_n)\)constructed in Proposition and let \(V_n\) denote the degree of \(X_n\). Then \(V_n\) has density function \(h_n\) given by \begin{align*} h_n(k) &= (1 - p_{n - k + 1}) \prod_{j = n - k + 2}^n p_j, \quad k \in \{1, 2, \ldots, n - 1\} \\ h_n(n) &=\prod_{j = 2}^{n} p_j \end{align*}
This follows from Proposition and Proposition : \begin{align*} \P(V_n = k) &= \P(I_{n - k + 1} = 0, I_j = 1 \text{ for } j \in \{n - k + 2, \ldots, n\}), \quad k \in \{1, 2, \ldots, n - 1\} \\ \P(V_n = n) &= \P(I_j = 1 \text{ for } j \in \{2, 3, \ldots n\}) \end{align*}
When \(p_k = p\) for all \(k \in \N_+\) then \(V_n\) has a truncated geometric distribution.
Suppose that \(p_k = p\) for \(k \in \N_+\) and for \(n \in \N_+\) and let \(V_n = \deg(X_n)\) as above.
Of course for us, the most interesting case is when \(X_n\) has constant rate on \((B_n, \lfrta_n)\) for each \(n \in \N_+\). The following results are a special case of the general recursive scheme in Proposition and Proposition
Let \(\alpha_1 = 1\) and then recursively let \[ \alpha_{n + 1} = \frac{\sqrt{4 \alpha_n^2 + 1} - 1}{2 \alpha_n}, \quad n \in \N_+ \] Let \(p_n = 1 / (1 + \alpha_n)\) for \(n \in \N_+\). Then random variable \(X_n\) in Proposition has constant rate \(\alpha_n\) on \((B_n, \lfrta_n)\) for each \(n \in \N_+\).
This follows from Proposition since the binomial tree of order 1 is a path on two vertices and hence the uniform distribution has constant rate 1 for this tree.
We can also give a recurrence relation for the parameters \((p_n: n \in \N_+)\) directly: \(p_1 = \frac{1}{2}\) and \[ p_{n + 1} = \frac{2 - 2 p_n}{(2 - 3 p_n) + \sqrt{5 p_n^2 - 8 p_n + 4}}, \quad n \in \N_+ \]
The rate constant \(\alpha_n\) decreases to 0 and the probability parameter \(p_n\) increases to 1 as \(n \to \infty\).
Explicit formulas for \(\alpha_n\) and \(p_n\) as a function of \(n \in \N_+\) seem difficult. But we can give the results for the first few values. We already know what happens when \(n = 1\); only the notation is different.
The binomial tree of order 1 is a path on 2 vertices. The rate constant and probability are \(\alpha_1 = 1\) and \(p_1 = 1 / 2\). The constant rate distribution has is uniform, with density \(f_1\) given by \(f_1(0) = 1 / 2\) and \(f_1(1) = 1 / 2\).
When \(n = 2\) we also have a path so the result is a special case of general results on paths in Section 7.3.
The binomial tree of order 2 is a path on 4 vertices. The rate constant and probability are \(\alpha_2 = p_2 = \left(\sqrt{5} - 1\right) / 2 \approx 0.6180\). The constant rate distribution has density \(f_2\) given by \begin{align*} f_2(00) & = f_2(10) = \frac{3 - \sqrt{5}}{4} \\ f_2(01) & = f_2(11) = = \frac{\sqrt{5} - 1}{4} \end{align*}
The case \(n = 3\) is different and not treated elsewhere.
For the binomial tree of order 3, the rate constant and probability are \[ \alpha_3 = \frac{\sqrt{7 - 2 \sqrt{5}} - 1}{\sqrt{5} - 1} \approx 0.4773, \; p_3 = \frac{\sqrt{5} - 1}{\sqrt{7 - 2 \sqrt{5}} + \sqrt{5} - 2} \approx 0.6769 \] The constant rate distribution has density \(f_3\) given by \begin{align*} f_3(000) & = f_3(100) = \\ f_3(010) & = f_3(110) = \\ f_3(001) & = f_3(101) = \\ f_3(011) & = f_3(111) = \end{align*}
Of course, Proposition on \(V_n = \deg(X_n)\) applies to the constant rate distributions. Rooted, directed binomial trees will be studied in Chapter 5.
Another tractible case arises from endpoint addition to a regular graph.
Suppose that \((S, \rta)\) is a right \(k\)-regular graph with \(n\) vertices where \(n, \, k \in \N_+\). Let \((T, \Rta)\) denote the graph obtained from \((S, \rta)\) by endpoint addition. Then \((T, \Rta)\) has a constant rate distribution with rate \[ \beta = \frac{\sqrt{k^2 + 4} - k}{2} \] and density function \(g\) given by \begin{align*} g(x) &= \frac{1}{n} \frac{2}{\sqrt{k^2 + 4} + 2 - k}, \quad x \in S \\ g(u_x) & = \frac{1}{n} \frac{\sqrt{k^2 + 4} - k}{\sqrt{k^2 + 4} + 2 - k}, \quad x \in S \end{align*}
The uniform distribution on \(S\) has constant rate \(1 / k\) for \((S, \rta)\), so the result follows from Proposition and some algebra.
Note that the rate constant in Proposition depends only on \(k\) (but of course we must have \(k \le n\)). Note also that \(\beta \to 0\) as \(k \to \infty\).
Let \(n \in \{3, 4, \ldots\}\). Give the results in Proposition explicitly for the following graphs: