21 | May | 2012 | Eventually Almost Everywhere

Here, devices have fixed capacity, but packet sizes are random. So, we still have a capacity constraint for the links, but we accept that it won’t be possible to ensure that we stay within those limits all the time, and seek instead to minimise the probability that the limits are exceeded, while keeping throughput as high as possible.

An important result is Chernoff’s Bound: $\mathbb{P}(Y\geq 0)\leq \inf_{s\geq 0}\mathbb{E}e^{sY}$ . The proof is very straightforward: apply Markov’s inequality to the non-negative random variable $e^{SY}$ . So in particular $\frac{1}{n}\log\mathbb{P}(X_1+\ldots+X_n\geq 0)\leq \inf M(s)$ , where $M(s)=\log\mathbb{E}e^{sX}$ , and Cramer’s Theorem asserts that after taking a limit in n on the LHS, equality holds, provided $\mathbb{E}X<0,\mathbb{P}(X>0)>0$ .

We assume that the traffic has the form $S=\sum_{j=1}^J\sum_{i=1}^{n_j}X_{ji}$ , where these summands are iid, interpreted as one of the $n_j$ loads used on source j. We have

$\log\mathbb{P}(S>c)\leq\log \mathbb{E}[e^{s(S-C)}]=\sum_{j=1}^Jn_jM_j(s)-sC$

so $\inf(\sum n_jM_j(s)-sC)\leq -\gamma\quad\Rightarrow\quad \mathbb{P}(s\geq C)\leq e^{-\gamma}$

so we want this to hold for large $\gamma$ .

We might then choose to restrict attention to

$A=\{n:\sum n_jM_j-sC\leq-\gamma,\text{ some }s\geq 0\}$

So, when operating near capacity, say with call profile n* on (ie near) the boundary of A, with s* the argmin of the above. Then the tangent plane is $\sum n_jM_j(s^*)-s^*C=-\gamma$ , and since A’s complement is convex, it suffices to stay on the ‘correct’ side (ie halfspace) of this tangent plane.

We can rewrite as $\sum n_jM_j(S^*)\leq C-\frac{\gamma}{s^*}$ . Note that this is reasonable since s* is fixed, and we call $\frac{M_j(s)}{s}=:\alpha_j(s)$ , the effective bandwidth. It is with respect to this average that we are bounding probabilities, hence ‘effective’.

Observe that $\alpha_j(s)$ is increasing by Jensen as $(\mathbb{E}e^X)^t\leq \mathbb{E}e^{tX}$ for t>1 implies that for t>s, $(\mathbb{E}e^{sX})^t\leq(\mathbb{E}e^{tX})^s$ .

In particular,

$\mathbb{E}X\leq \alpha_j(s)\leq \text{ess sup}X$

Eventually Almost Everywhere

A blog about probability and olympiads by Dominic Yeo

Daily Archives: May 21, 2012

Effective Bandwidth