Finite-tree multicast loss experiments

A finite rooted directed tree $T=(V,E)$ has root $o$, with all edges directed away from $o$, and a nonempty receiver set $R$ consisting of every leaf other than $o$. Every nonroot internal vertex has at least two children. For a vertex $v$, its children are the vertices joined to $v$ by an outgoing edge; $P(o,v)$ is the unique edge set on the path from $o$ to $v$. The root may have any finite number of children.

A finite probe design is a nonempty finite family $\mathcal{C}=((C_d,N_d){)}_{d=1}^D$, where each receiver set $C_d$ is a nonempty subset of $R$ and each probe count $N_d$ is a positive integer. A singleton receiver set is a unicast scheme; a receiver set of size at least two is a multicast scheme. Its used edge set is $E_d={\bigcup }_{r\in C_d}P(o,r)$.

For a link-success parameter vector $p=(p_e{)}_{e\in E}\in (0,1{)}^E$, each design $d$ and probe $j\in \{1,\dots ,N_d\}$ has mutually independent link-success variables $X_{e,d,j}\in \{0,1\}$ for $e\in E_d$, with ${\mathrm{Pr}}_p(X_{e,d,j}=1)=p_e$. The same $p_e$ applies in every design and probe (temporal homogeneity). The observed receiver indicator is

$$Y_{r,d,j}=\prod _{e\in P(o,r)}{X}_{e,d,j}(r\in C_d)\mathrm{.}$$

For $y\in \{0,1{\}}^{C_d}$ let

$${\mathrm{\Omega }}_{d,y}=\{x\in \{0,1{\}}^{E_d}:y_r=\prod _{e\in P(o,r)}{x}_e\text{ for every }r\in C_d\},w_{p,d}(x)=\prod _{e\in E_d}{p}_e^{x_e}(1-p_e{)}^{1-x_e}\mathrm{.}$$

The one-probe outcome law is

$$P_{p,d}(y)=\sum _{x\in {\mathrm{\Omega }}_{d,y}}{w}_{p,d}(x)\mathrm{.}$$

These probabilities sum to one because the sets ${\mathrm{\Omega }}_{d,y}$ partition the finite link-state space and ${\sum }_{x\in \{0,1{\}}^{E_d}}{w}_{p,d}(x)={\prod }_{e\in E_d}(p_e+(1-p_e))=1$. The complete experiment observes $N_d$ independent outcomes with law $P_{p,d}$ for each design, independently across designs. If the data are summarized by counts, $n_{d,y}\in {\mathbb{N}}_0$ is the number of probes in design $d$ with outcome $y$, and ${\sum }_y{n}_{d,y}=N_d$.

This is a finite statistical experiment: its parameter space is $(0,1{)}^E$ and its sampling law is the finite product of the stated receiver-outcome laws.

Statistical experiments

Cáceres, Duffield, Horowitz, and Towsley, §§2.1–2.3

Lawrence, Michailidis, and Nair, §§1–2