----- > [!proposition] Proposition. ([[the cascade model]]) > > > The cascade model is a simple mathematical model of a directed acyclic network, sometimes used to model food webs. We take $n$ nodes labeled $i = 1 \ldots n$ and place an undirected edge between each distinct pair with independent probability $p$, just as in the ordinary random graph. Then we add directions to the edges such that each edge runs from the node with numerically higher label to the node with lower label. This ensures that all directed paths in the network run from higher to lower labels and hence that the network is acyclic, as discussed in Section 6.4.1. > > a) Show that the average in-degree of node $i$ in the ensemble of the cascade model is $\langle k_{\text{in}} \rangle = (n - i)p$ and the average out-degree is $\langle k_{\text{out}} \rangle = (i - 1)p$. > > Let $X$ denote the in-degree of node $i$. For each node $j$ the network define $X_{i}=\mathbb{1}_{\text{edge exists from }j \text{ to }i}$. Then $X=\sum_{j=1}^{n}X_{i}$. But for all nodes $j$ with index less than or equal to $i$ , of which there are $i$ , $X_{j}=0$ with [[probability]] $1$. Thus $\mathbb{E}[X]=\sum_{n-i\text{ terms}} p=(n-i)p$ is the average in-degree of $i$. > > Let $Y$ denote the out-degree of node $i$. For each node $j$ the network define $X_{i}=\mathbb{1}_{\text{edge exists from }j \text{ to }i}$. Then $X=\sum_{j=1}^{n}X_{i}$. But for all nodes $j$ with index greater than $i$ , of which there are $n-i+1$ , $X_{j}=0$ with [[probability]] $1$. Thus $\mathbb{E}[X]=\sum_{i-1\text{ terms}} p=(n-1)p$ is the average in-degree of $i$. > > b) Show that the expected number of edges that connect to nodes $i$ and lower from nodes above $i$ is $(ni - i^2)p$. > > Let $X$ denote the number of edges that connect to nodes $i$-and-lower from nodes above $i$. For each pair of nodes $j,k$ with $j \leq i$ and $k > i$, define $X_{jk}=\mathbb{1}_{\text{edge exists from }k \to j}$. Then $X=\sum_{j,k}X_{jk}$, so that $\mathbb{E}[X]=\sum_{j,k}\mathbb{E}[X_{jk}]$. There are $i(n-i)$ such pairs of $j$ and $k$ and therefore $i(n-i)$ terms in the summation. Because $\mathbb{E}[X_{jk}]$ is just $p$, we conclude $\mathbb{E}[X]=i(n-i)p=(ni-i^{2})p$. > > > c) Assuming $n$ is even, what are the largest and smallest values of this quantity and where do they occur? > > The largest value is at $i=\frac{n}{2}$ and is $\left( \frac{n^{2}}{2}-\frac{n^{2}}{4} \right)p$ (pretend its continuous and differentiate, critical point is maximum because of concavity). The smallest value is at $i=1$ and is $(n-1)p$. (kind of just a guess im sleepy) ----- #### ---- #### References > [!backlink] > ```dataview > TABLE rows.file.link as "Further Reading" > FROM [[]] > FLATTEN file.tags as Tag > WHERE Tag = "#definition" OR Tag = "#theorem" OR Tag = "#MOC" OR Tag = "#proposition" OR Tag = "#axiom" > GROUP BY Tag > ``` > [!frontlink] > ```dataview > TABLE rows.file.link as "Further Reading" > FROM outgoing([[]]) > FLATTEN file.tags as Tag > WHERE Tag = "#definition" OR Tag = "#theorem" OR Tag = "#MOC" OR Tag = "#proposition" OR Tag = "#axiom" > GROUP BY Tag > ```