= Solution
Use an ideal <carrier-sense multiple access> scheme on the <interference graph>. An active station finishes its transmission after an independent unit-rate <exponential distribution> waiting time. An inactive station has an independent attempt clock with an <exponential distribution> of rate $e^{\theta_r}$; an attempt succeeds only when all its neighbors are inactive. Attempts that are blocked do not change the state. Thus, on the <independent sets> represented by $S$, the <continuous-time Markov chain> has <transition rates>
$$
q(n,n+e_r)=e^{\theta_r}\quad(n+e_r\in S),
\qquad q(n,n-e_r)=1\quad(n_r=1).
$$
The empty <independent set> can be reached by successive deactivations, and any other <independent set> can be reached from it by successive activations. Hence this finite chain is an <irreducible Markov chain>. The weight $a_\theta(n)=e^{\theta\cdot n}$ satisfies
$$
a_\theta(n)e^{\theta_r}=a_\theta(n+e_r).
$$
By <detailed balance for a continuous-time Markov chain>, its \b[unique stationary law] is
$$
\boxed{\pi_\theta(n)=\frac{e^{\theta\cdot n}}{Z(\theta)},\qquad
Z(\theta)=\sum_{m\in S}e^{\theta\cdot m}.}
$$
This is a finite <exponential family>. Its <natural parameter of an exponential family> is $\theta$ and its <mean parameter of an exponential family> is the vector of active fractions.
The <throughput region of an interference graph> is exactly $\Lambda=\operatorname{conv}S$. To see the possibly less immediate inclusion, suppose a random feasible schedule has mean $v\geq\lambda$. Retain each of its active vertices $r$ independently with <probability> $\lambda_r/v_r$, interpreting zero coordinates as always deleted. A subset of an <independent set> remains an <independent set>; the thinned schedule has mean exactly $\lambda$. Thus $\lambda$ lies in the <convex hull> of $S$. The opposite inclusion follows from the definition using equality. Moreover $0,e_1,\ldots,e_R\in S$, so this <convex hull> has full dimension.
Now choose $\varepsilon>0$ such that $\mu=\lambda+\varepsilon\mathbf1$ remains in the interior of $\operatorname{conv}S$. Use <interior moment matching in a finite exponential family>. Consider the <convex function>
$$
F(\theta)=\log Z(\theta)-\theta\cdot\mu.
$$
There is a ball of radius $\delta>0$ around $\mu$ contained in $\operatorname{conv}S$. Maximizing a linear functional over the <convex hull> is the same as maximizing over its generating set, so, for every $\theta$,
$$
F(\theta)\geq\max_{n\in S}\theta\cdot(n-\mu)
\geq\delta\|\theta\|.
$$
The last inequality uses the point $\mu+\delta\theta/\|\theta\|$ when $\theta\ne0$. Hence $F$ is a <coercive function> and has a finite minimizer $\theta^*$. Differentiating the finite normalizing sum gives
$$
\frac{\partial F}{\partial\theta_r}=\mathbb E_\theta[n_r]-\mu_r,
\qquad \nabla^2F=\operatorname{Cov}_\theta(n).
$$
This <covariance matrix> is a <positive-definite matrix>: a linear functional constant on all states of positive weight must be constant on $0,e_1,\ldots,e_R$, so its coefficients vanish. Thus $F$ is a <strictly convex function>; its minimizer is unique. At that minimizer the \b[desired strict service margins] are
$$
\boxed{\mathbb E_{\theta^*}[n_r]=\mu_r=\lambda_r+\varepsilon>\lambda_r
\quad\text{for all }r.}
$$
For a backlogged station that transmits at unit speed whenever active, the long-run <throughput> is $\mathbb E_\theta[n_r]$, by the <ergodic theorem for a finite continuous-time Markov chain>. Therefore the ideal <carrier-sense multiple access> scheme can supply a strict service margin for every arrival vector in the interior of the <throughput region of an interference graph>. The local attempt rates can realize the whole interior capacity region in this sense. Boundary points may require parameters tending to infinity, and the argument gives no uniform delay or mixing-time bound near the boundary.
Back to article page
