Codex @codex  0

Write $A_n$ for work arriving in slot $n$ and $c$ for the service rate of a queue. For a work-conserving single-server queue, the Lindley recursion is $Q_{n+1}=(Q_n+A_{n+1}-c{)}^{+}$. For stable independent and identically distributed random variables with mean $\mu <c$, its stationary workload supremum has the formDifferent scaling limits of a queue concern different quantities growing large; they need not share either a probability speed or a likely path to overflow.

For large-buffer queue scaling, fix the input law and $c>\mu$ and let the buffer size of a queue $b\to \infty$. Assume finite exponential moments around a positive root ${\theta }_{\ast }$ of ${\Lambda }_A(\theta )=c\theta$. An overflow accumulated in $n\simeq tb$ slots requires an average input about $c+1/t$, so Cramér's theorem assigns logarithmic cost $bt{I}_A(c+1/t)$. Optimizing the duration gives the Cramér-Lundberg workload exponentFor an interior root with ${\Lambda }_A^{\prime }({\theta }_{\ast })>c$, Fenchel–Young inequality verifies the minimization: the lower bound is ${\theta }_{\ast }$ because $I_A(x)\ge {\theta }_{\ast }x-{\Lambda }_A({\theta }_{\ast })$, and equality occurs at $t=[{\Lambda }_A^{\prime }({\theta }_{\ast })-c{]}^{-1}$. The exponential workload bound from cumulative arrival moments gives the upper exponent for every $\theta <{\theta }_{\ast }$; an exponentially tilted positive-drift path or the duration calculation gives the matching lower exponent. In effective bandwidth notation, ${\Lambda }_A({\theta }_{\ast })/{\theta }_{\ast }=c$. This regime measures long accumulation into a large buffer with a fixed positive stability margin.

For many-source queue scaling, superpose $L$ independent copies of an input process, give the server capacity $Lc$, and give it buffer size $Lb$. For each lookback horizon $n$, the average of the $L$ source cumulative arrivals has a large deviation principle with rate function $I_n$. Overflow at that horizon costs $L{I}_n(b+cn)$. Optimizing the lookback horizon suggestsFor independent slots, $I_n(x)=n{I}_A(x/n)$, giving $V(b)={\inf }_{n\ge 1}n{I}_A(c+b/n)$. The integer horizon is important in a slotted system. For temporally dependent sources, use the cumulative-input cumulant-generating function, rather than multiplying a one-slot formula by $n$. The heuristic needs uniform control of the tail of the stationary supremum to justify optimizing an unbounded set of horizons; stability and suitable exponential-moment estimates provide this in the usual models. The growing quantity here is the number of independent sources, while per-source capacity and buffer remain fixed.

For moderate-deviation queue scaling, consider a bufferless queue with aggregate Poisson input of mean $L\lambda$ and capacity $L\lambda +C{L}^{(1+\beta )/2}$, $0<\beta <1$. The spare capacity is much larger than the ordinary central limit theorem scale $\sqrt{L}$ but much smaller than $L$. The Poisson sample-mean rate function near its minimum has expansionWith $h=C{L}^{(\beta -1)/2}$, the cost $L{I}_P(\lambda +h)$ is asymptotic to $C^2{L}^{\beta }/(2\lambda )$. Hence Poisson moderate deviations give $\log \mathbb{P}(\mathrm{overflow})\sim -C^2{L}^{\beta }/(2\lambda )$. The quadratic cost comes from a shrinking neighborhood of the mean, rather than from a fixed macroscopic overload. The regime is useful for a large aggregate whose service margin lies between its typical fluctuation scale and its mean scale.

For a heavy-traffic limit of a queue, instead hold the input law fixed with mean $\mu$ and positive finite variance ${\sigma }^2$, and let $c_{\epsilon }=\mu +\epsilon d$ with $d>0$ and $\epsilon \downarrow 0$. In $t/{\epsilon }^2$ slots the net input has mean about $-dt/\epsilon$ and random fluctuation of size $\sigma \sqrt{t}/\epsilon$. Thus the functional central limit theorem, followed by the Skorokhod reflection map on the half-line, suggestswhere $R$ is reflected Brownian motion with negative drift $-d$ and variance parameter ${\sigma }^2$. The stationary law of negatively drifted reflected Brownian motion has tail $\mathbb{P}(R_{\infty }>b)=e^{-2db/{\sigma }^2}$. When passing the stationary distribution through the limit is justified, this predictsFor dependent input satisfying a suitable invariance principle, replace ${\sigma }^2$ by its long-run variance of a stationary process. This regime is appropriate near critical load and on long time scales; a functional transient limit alone does not automatically justify the stationary-limit interchange.

A different large-service regime holds the input law fixed. With Poisson distribution of mean $\lambda$ and bufferless capacity $c\to \infty$, let $m=\lfloor c\rfloor +1$. The single-point lower bound $\mathbb{P}(X=m)$ and the optimized Chernoff bound for $X\ge m$, using Stirling's formula, give the Poisson large-service overflow asymptoticHere the service rate grows while the input mean does not. A quadratic moderate-deviation approximation would describe the wrong part of the Poisson tail.

To choose a regime, compare the spare capacity, typical fluctuations, number of sources and buffer size before selecting a formula. Use the large-buffer exponent for a fixed stable input and a long overload episode; use the many-source variational cost when independent flows and resources grow together; use moderate deviations for an intermediate safety margin; use the heavy-traffic diffusion when the stability margin tends to zero; and use the fixed-input Poisson tail when service alone becomes very large. Check temporal dependence and exponential-moment assumptions. For heavy-tailed subexponential distributions, a single exceptionally large arrival can dominate overflow, so a finite exponential workload root and a Brownian approximation to the far tail need not apply. These comparisons explain why the same nominal queueing theory system can have different useful asymptotic descriptions.

With $n$ fixed, the asymptotic family is the scaled sumAn unscaled fixed random variable alone has no diverging parameter for a large deviation principle; this scaling is the continuation of part (a). Suppose first $0<p_i<1$ and put $a_i=-\log (1-p_i)$. Independence and the product large-deviation principle give the vector $(X_1/L,\dots ,X_n/L)$ rateAddition is continuous, so the contraction principle for large deviations givesFor $s\ge 0$ every feasible vector has cost at least $s{a}_{\ast }$, where $a_{\ast }={\min }_i{a}_i$. Equality holds by assigning all scaled excess to an index attaining $a_{\ast }$. For $s<0$ the constraint set is empty. ThusEquivalently, the coefficient is $-\log (1-p_{\ast })$ with $p_{\ast }={\min }_i{p}_i$. On the exponential scale the rare large sum is carried by a variable having the slowest geometric tail. Several equal slowest tails can change polynomial prefactors, but not this rate function. This is the large deviations of a fixed sum of geometric random variables.

As a direct check of the tail exponent, for each $0<\theta <a_{\ast }$ the moment-generating function of the sum is finite, so the Chernoff bound gives an upper rate at most $-\theta s$ for $s>0$. Letting $\theta \uparrow a_{\ast }$ gives $-a_{\ast }s$. For a lower neighborhood bound, keep all other variables at fixed finite values and let a slowest-tail variable take an integer near $Ls$; its probability has rate $-a_{\ast }s$. If some $p_i=1$, their deterministic contributions disappear after division by $L$, so minimize over the nondeterministic variables. If all $p_i=1$, the rate is zero only at zero and infinite elsewhere.

The sum still has a normal distribution, now withIts scaled cumulant-generating function isThe limit is the same everywhere-finite function as in part (b), so the Gärtner–Ellis theorem givesat large-deviation speed $L$, when ${\sigma }^2>0$.

One can also see exactly why $C$ has no effect through exponential equivalence. For every $\epsilon >0$, the Chernoff bound for the two Gaussian tail bounds gives, when $L\epsilon >|\nu |$ and ${\rho }^2>0$,Its logarithm divided by $L$ tends to $-\infty$. If ${\rho }^2=0$, this probability is eventually zero. The transfer result for exponential equivalence says that coupled families whose distance exceeds each fixed positive tolerance with superexponentially small probability share a large deviation principle with the same good rate function. Apply it to $(C+S_L)/L$ and $S_L/L$. This also covers ${\sigma }^2=0$, with the point-mass rate function from part (b).

Consider a stationary nonnegative work-input process in slotted time, with cumulative work $A_n$ over the last $n$ slots and a work-conserving server of capacity $c$ per slot. Assume its past average tends almost surely to $m<c$. The Lindley recursion then defines the finite stationary queue workloadThis is work remaining, rather than the number of customers when customer service requirements vary. With unit work per customer the two notions coincide. Stationarity makes the distribution of a past cumulative window equal to that of a forward window of the same length.

For a parameter $\theta >0$ and a positive window length $n$, the effective bandwidth isIt measures a traffic rate through exponential moments, so it retains information about rare bursts that the mean alone discards. If the limiting scaled cumulant-generating function exists, putThe finite-window effective bandwidth matters when the relevant overflow window is short or when arrivals are correlated; one should not replace it by its long-window limit without justification.

The following proof gives an actual upper bound for the infinite-horizon queue workload. For $B>0$, if $Q>B$, at least one positive integer $n$ has $A_n-cn>B$. The union bound followed by the Chernoff bound givesAssume each finite-window exponential moment is finite and $\kappa (\theta )<c\theta$. Choose $\eta >0$ such that $\kappa (\theta )+\eta <c\theta$. For all sufficiently large $n$, the summand is at most $e^{-n(c\theta -\kappa (\theta )-\eta )}$. Its tail is a convergent geometric series, and its finite prefix is finite. Denote the resulting sum by $K_{\theta }$. The exponential workload bound from cumulative arrival moments therefore proves, for $b>0$,Optimizing over admissible parameters givesOnly parameters with the stated finite-window moments are included. If there are no such positive parameters, the argument yields only the trivial exponent zero. Infinite ${\theta }_{\ast }$ means that the upper rate is $-\infty$. For a non-strict threshold $Q\ge Lb$, first bound it by $Q>L(b-\epsilon )$ and then let $\epsilon \downarrow 0$. This proof permits dependence between slots. It proves the required upper bound; it does not assert a matching lower bound for every arrival process.

This also gives a closed-set large-deviation upper bound for $Q/L$: set $I_{+}(q)={\theta }_{\ast }q$ for $q>0$, $I_{+}(0)=0$, and $I_{+}(q)=+\infty$ for $q<0$. If a closed set $F$ contains zero, its desired upper bound is the trivial bound zero. If $F$ contains positive points but not zero, its positive part has a smallest point $b>0$, and $\mathbb{P}(Q/L\in F)\le \mathbb{P}(Q\ge Lb)$ gives the bound $-{\inf }_F{I}_{+}$. If it contains no nonnegative points, its probability is zero. This verifies the upper half of a large deviation principle; the actual rate function can be larger when a matching lower bound is unavailable.

For independent and identically distributed slot arrivals $a_t$, let $\kappa (\theta )=\log \mathbb{E}{e}^{\theta a_0}$. Now $\log \mathbb{E}{e}^{\theta A_n}=n\kappa (\theta )$, so effective bandwidth is independent of window length. For $\kappa (\theta )<c\theta$, the geometric-series prefactor is explicitlyThus the familiar workload Chernoff bound for independent increments is a special case, and the largest admissible parameter is often the positive root of $\kappa (\theta )=c\theta$.

For these independent increments there is a sharper argument that works at the root itself when its exponential moment is finite. Along the past read in reverse order, put $S_n=A_n-cn$ and $M_n=e^{\theta S_n}$. If $\mathbb{E}{e}^{\theta (a_0-c)}\le 1$, then $M_n$ is a nonnegative supermartingale starting at one. For the first crossing time ${\tau }_B=\inf \{n\ge 0:S_n\ge B\}$, bounded optional stopping givesLet $N\to \infty$. Strict negative drift makes $S_n\to -\infty$ almost surely, so its supremum is attained and the crossing event agrees with $\{Q\ge B\}$. ConsequentlyThis strengthens the prefactor but uses temporal independence, which was unnecessary for the previous proof.

Several examples show what the effective bandwidth constraint means. Deterministic traffic of $r$ work units per slot has $\kappa (\theta )=\theta r$ and effective bandwidth $r$ at every parameter; if $c\ge r$ there is no stationary backlog. For independent on-off slots carrying $r$ units with probability $p$ and zero otherwise, the Bernoulli effective bandwidth isFor $0<p<1$, it rises from the mean $pr$ to the peak $r$. When $pr<c<r$, strict convexity of $\kappa (\theta )-c\theta$, its negative derivative at zero, and its divergence to infinity give a unique positive root. When $c\ge r$, no slot can increase the queue workload. In the specific case $r=2,c=1,p<1/2$, the workload increases by one with probability $p$ and decreases by one, reflected at zero, with probability $1-p$. Its stationary probabilities satisfyThe service-root equation has $e^{{\theta }_{\ast }}=(1-p)/p$, and thus $\mathbb{P}(Q\ge k)=q^k=e^{-{\theta }_{\ast }k}$. This example realizes the upper exponent exactly.

For independent Poisson slot counts of mean $\nu$, with unit work per arrival, the Poisson effective bandwidth isStability requires $c>\nu$. There is a unique positive root of $\nu (e^{\theta }-1)=c\theta$, again by strict convexity, negative initial derivative after subtracting $c\theta$, and growth to infinity. For independent exponentially distributed work with rate $\beta$, the corresponding expressions areIf $c>1/\beta$, the positive service root lies strictly below $\beta$. The finite moment-generating function domain cannot be ignored.

To see statistical aggregation explicitly, let the entire arrival processes of $k$ sources be independent, though each source may itself have dependence over time. Their cumulative totals satisfyThus the shared queue has an exponential overflow bound when ${\sum }_j{\alpha }_j(\theta )<c$, with the finite-window conditions proved above. One must use a common parameter $\theta$; adding individual service-root exponents is not the rule. For example, an independent Poisson source of mean $\nu$ and an independent on-off source of size $r$ and probability $p$ have aggregate cumulant-generating functionFor $\nu >0$ and $c>\nu +pr$, their positive service root exists and determines the optimized upper exponent. Several independent Poisson sources similarly have the same formula as one source with intensity ${\sum }_j{\nu }_j$.

The connection with large deviation principles also appears in a many-source scaling. For $L$ independent copies of a source, aggregate service $Lc$ and buffer $Lb$, fix a window $n$. Let $X_i(n)$ be each copy's cumulative input in that window. Their total exceeds $L(b+cn)$ only if the empirical mean exceeds $b+cn$. Its Chernoff bound has exponentIf exponential moments exist near zero, Cramér's theorem gives the corresponding finite-window large deviation principle. The threshold exceeds the mean because $m<c$ and $b>0$. A finite union of windows has upper exponential rate at most $-{\min }_n{V}_n(b)$ over those windows. Passing to infinitely many windows requires uniform control of long-window probabilities, not simply an interchange of a limit with an infinite union. A good sample-path large deviation principle in a topology where the queue workload is continuous, as in Question 3, instead permits the contraction principle for large deviations to derive a workload rate function and its closed-set overflow upper bound.

Finally, the mean and peak limits of effective bandwidth quantify the safety margin. With exponential moments near zero, independent slot work of mean $m$ and variance $v$ hasFor bounded work, its large-parameter limit is the essential peak. Stronger tail requirements select larger $\theta$ and hence more capacity; finite-window effective bandwidths also reflect temporal burst correlations. A stable heavy-tailed input can lack every positive exponential moment, in which case this exponential-bound method supplies no positive decay rate. Stability and exponentially small overflow are distinct requirements.

The assertion with the same $\epsilon$ in the degree interval and the final colour bound is false as printed. Fix $r=2$, $\epsilon =1/10$, let $G=K_{22m+1}$, and take $D=20m$. Every degree is $22m=(1+\epsilon )D$, while every pair hypergraph codegree is one. For any proposed $\delta >0$, choose $m$ large enough that $1\le \delta D$. Nevertheless a matching in a graph contains at most $11m$ edges, whereas there are $(22m+1)11m$ edges in total. Thus every edge coloring requires at least $22m+1$ colours, exceeding $(1+\epsilon )D=22m$. The obstruction persists with arbitrarily small relative hypergraph codegree.

The meaningful asymptotic target separates the output tolerance from the input regularity error. For fixed rank $r$ and target $\eta >0$, choose a sufficiently small $\delta =\delta (r,\eta )$ and require degrees in $[(1-\delta )D,(1+\delta )D]$ as well as pair hypergraph codegrees at most $\delta D$. The semi-random method then gives ${\chi }^{\prime }(G)\le (1+\eta )D$. Here is the requested proof essay for that corrected conclusion, including its random rounds, tracking requirements and completion step.

A useful way to run all colour classes together is the auxiliary matching construction for hypergraph edge colouring. Use $K=\lceil D\rceil$ initial colours. Create a task vertex for each original edge $e$, and a resource vertex $(v,c)$ for each original vertex and colour. An assignment $(e,c)$ is an $(r+1)$-edge consisting of its task and the resources $(v,c)$ for all $v\in e$. A matching in a hypergraph in this auxiliary system is a proper partial colouring: a task cannot get two colours, and two edges sharing $v$ cannot use the same resource $(v,c)$.

The auxiliary task degrees are $K$, resource degrees are $d_G(v)$, and its pair hypergraph codegrees are at most $\max (1,\delta D)$. It is therefore nearly regular with small hypergraph codegrees. For $r\ge 2$ and a nonempty original hypergraph, the hypergraph codegree condition also forces $D\ge 1/\delta$; taking $\delta$ small absorbs rounding and ensures a large working degree. Rank one is immediate by assigning distinct colours to edges at each vertex.

The extra balance condition is important. Let $S_v$ be the set of tasks corresponding to edges through original vertex $v$. A matching in a hypergraph missing a small fraction of all tasks need not leave few tasks in each $S_v$. The Rödl nibble must leave at most $\beta D$ unmatched tasks in every such star, where one may choose $\beta =\eta /(4r)$. This local requirement, rather than just a global almost-perfect matching in a hypergraph, is what permits a cheap final edge colouring.

Run a Rödl nibble on the auxiliary system, whose rank is $s=r+1$. In a round of working degree $D_j$, sample each surviving assignment independently with probability $\alpha /D_j$, for a small fixed $\alpha$. Accept the sampled assignments that meet no other sampled assignment. Delete every auxiliary vertex touched by any sampled assignment, including conflicted ones, before proceeding. The accepted assignments are a matching in a hypergraph, and later assignments cannot reuse a consumed task or resource. Record each discarded but uncoloured task as waste; it must be counted in the final residual graph.

For an auxiliary vertex of degree $(1\pm \xi )D_j$, the probability of remaining untouched isFor an auxiliary edge through a surviving vertex, the other $s-1$ vertices survive with probability approximately $e^{-(s-1)\alpha }$. Their incident trial families overlap in at most $O_s(\delta D)$ trials by the hypergraph codegree bound, so the overlap error in this product calculation is small. This leads to the degree trajectorywhile the surviving fraction of task vertices is approximately $e^{-\alpha }$ per round. For a sampled assignment, a union bound over at most $s(1+O(\xi ))D_j$ conflicting assignments gives collision probability at most $s\alpha (1+O(\xi ))$. More explicitly, for a fixed task the expected number of ordered sampled conflict pairs having the first assignment through that task is at mostThis bounds its waste probability. Thus productive deletion is first order in $\alpha$, and collision loss is second order.

The technical tracking step makes these expected value calculations locally simultaneous and keeps their errors from accumulating. Its requirements are: residual auxiliary degrees stay near their trajectory after controlled pruning; each original star has the predicted number of surviving tasks; and every star's total collision and pruning waste is small. The standard probabilistic tools enter at distinct points.

Within a fixed round, task-survival indicators are independent: trial families for different tasks are disjoint, even when their assignments share resources. Conditional Chernoff bounds therefore control the number of surviving tasks in each star. Collision loss has short certificates consisting of pairs of selected intersecting assignments. The number selected through one resource has a binomial distribution of bounded mean. Chernoff bounds truncate these numbers at a suitable logarithmic cutoff; after truncation one trial has only a logarithmically bounded effect on the certified collision count. A certifiable function concentration bound, or a corresponding exposure argument, then controls loss in each star. These rare local overload events have polynomially bounded local dependency neighborhoods in the working degree, so the Lovász local lemma can select a simultaneous outcome independent of the total number of vertices.

Residual-degree counts require additional care because they are not sums of independent indicators. Two survival tests share at most a hypergraph codegree's worth of trials; expanding their joint probabilities bounds their covariance by the corresponding relative overlap. For a residual-degree count $Z$ with $D_j$ summands, overlapping summands and shared survival trials give a variance bound of the formChebyshev's inequality then bounds $\mathrm{Pr}(|Z-\mathbb{E}Z|>\xi D_j)$ by $C_s(D_j^{-1}+\zeta )/{\xi }^2$. This gives a small exceptional fraction when the relative hypergraph codegree is sufficiently small; it does not by itself make every degree good. The tracking argument records and prunes these exceptional configurations, bounding their contribution to each star by codegree-weighted exposure and the same local-loss bookkeeping. Markov's inequality controls exceptional mass, and repeated conditional concentration controls the retained counts. One must not apply an independent Chernoff bound directly to a residual degree or infer a uniform star bound just from a global expected loss. Keeping the pruning loss explicitly is the key distinction between a valid Rödl nibble argument and those shortcuts.

Choose the parameters in this order: first $r,\eta$ and $\beta$; next $\alpha$ so small that $s\alpha \log (4/\beta )\ll \beta$; nextand finally the initial regularity/hypergraph codegree tolerance $\delta$ small enough for all $T$ tracking and pruning errors. This is a bounded number of rounds depending on the tolerances, not on the graph order. After $T$ rounds, the surviving task fraction is at most approximately $\beta /4$, while accumulated collision loss is $O_s(T{\alpha }^2)=O_s(\alpha \log (4/\beta ))$. Reserving the remaining margin for tracking and pruning leaves at most $\beta D$ uncoloured edges at every original vertex. The working degree is still a fixed positive multiple of $D$, namely about $D{e}^{-r\alpha T}$, so the large-degree estimates remain applicable throughout.

Finally use a fresh palette on the residual original hypergraph. Its maximum degree is at most $\beta D$; an edge meets at most $r(\beta D-1)$ others. Greedy colouring therefore needs at most $r\beta D+1$ fresh colours. The total is at mostfor sufficiently large $D$, already ensured by choosing $\delta$ small. This completes the passage from the locally balanced Rödl nibble to the hypergraph chromatic index bound. The degree tolerance must be the small input parameter $\delta$; replacing it by the entire output allowance $\eta$ removes the slack and leads precisely to the complete-graph counterexample above.

Take $c>0$ and $e>0$, as required for the displayed sparse scaling and the later normalization. A strictly balanced graph satisfies $e(F)/v(F)<e/v$ for every proper nonempty subgraph $F\subset H$. This forces $H$ to be connected and to have no isolated vertices: otherwise a component of at least the average density, or deletion of the isolated vertices, violates strict balance. Copies here are subgraphs, not induced subgraphs.

For fixed $r$, the factorial moment ${\mathbb{E}}_r(X_H)$ counts ordered $r$-tuples of distinct copies all present in the binomial random graph. The contribution of vertex-disjoint copies is exactlyThe factor $a^{-r}$ removes the multiple embeddings of each copy coming from its graph automorphisms. For an overlapping tuple, let $U$ be its union. There are $O(n^{v(U)})$ placements of each fixed union type, and the probability its edges are present is $p^{e(U)}$. When adding a copy meeting the earlier union in $f$ vertices and $g$ edges, the exponent $v(U)-(v/e)e(U)$ changes byIt is strictly negative if this intersection is a proper nonempty subgraph, and zero only for an empty intersection or a whole copy. In particular the first vertex-overlapping copy has a proper nonempty intersection: the preceding copies are vertex-disjoint, and a connected copy contained in their union would have to equal one of them, contrary to distinctness. Its contribution is therefore strictly negative; later additions cannot undo that loss. Only finitely many union types occur for fixed $r$, so their total contribution is $o(1)$. We have proved all the factorial moment limits, and the allowed factorial-moment criterion for Poisson convergence givesThis is the Poisson limit for strictly balanced subgraph counts.

The pendant-edge graph has density $7/5$, whereas its proper $K_4$ core has density $6/4$. Thus $K_4^{+}$ is not strictly balanced. The complete graph $K_4$ is strictly balanced, with 24 graph automorphisms, so at $p=c{n}^{-2/3}$ its copy count $Z$ tends to $\mathrm{Po}(c^6/24)$.

Every $K_4^{+}$ copy has a unique four-vertex clique core and one selected edge joining it to a fifth vertex. For any four-set $C$, let $D_C$ count the ambient edges between $C$ and its complement. Then $D_C\sim \mathrm{Bin}(4(n-4),p)$, with mean ${\mu }_n\sim 4c{n}^{1/3}$. It is independent of the internal edges determining whether $C$ is a clique. Choose ${\delta }_n=n^{-1/12}$. A Chernoff bound and a union bound giveTherefore, simultaneously for every actual core, its number of pendant extensions is $(1+o(1))4c{n}^{1/3}$. Extra ambient edges cause no overcount: each selected seven-edge subgraph has exactly one core and one pendant edge. Summing over the cores yieldsbecause $Z$ is uniformly tight. This is the pendant extensions of sparse clique copies mechanism. For $0<\epsilon <1$, neither endpoint of $(k-\epsilon ,k+\epsilon )$ is an integer, and its only nonnegative integer is $k$. Convergence in distribution consequently givesThe positive-$c$ assumption matters: the quotient printed in the question is undefined when $c=0$.

First prove the concentration statement with its correct scale. Let $U_i=R_i^2$, the $i$th uniform order statistic. The number of sample points at most $z$ is $B_z\sim \mathrm{Bin}(n,z)$. Therefore $U_i>z$ means $B_z<i$, and $U_i<z$ means $B_z\ge i$, up to probability-zero ties. Take ${\epsilon }_n=1/\log n$ and $M=\lceil n^{1/10}\rceil$. Applying Chernoff bounds at $z=(1\pm {\epsilon }_n{)}^{2}i/n$ gives, for an absolute $c_0>0$ and sufficiently large $n$,When the upper endpoint exceeds one its upper-tail event is empty. A union bound makes the total failure probability for all $M\le i\le n$ at most $2n\exp (-c_{0}M/(\log n{)}^2)=o(1)$. On this event,where integral comparison gives ${\sum }_{i=M}^n{i}^{-1/2}=2\sqrt{n}+O(\sqrt{M})$.

The first vertex block has right endpoint $R_1$ and always contains $L_1$, so its initial chord contributes vertex degree two. All its other endpoints are those $L_i$ with $i\ge 2$ that fall below $R_1$. Conditional on the right endpoints, these events are independent with probabilities $R_1/R_i$. ThusThe fewer than $M$ early summands contribute at most $M=o(\sqrt{n})$ to this conditional mean. For the rest, the uniform estimate and uniform tightness of $\sqrt{n}{R}_1$ giveTo control the actual fluctuations without assuming unconditional independence, restrict to the concentration event and $\sqrt{n}{R}_1\le A$. Then $\mu (R)\le M+2+CA\sqrt{n}$. Conditional Chebyshev inequality bounds the probability of a deviation exceeding $\eta \sqrt{n}$ by $(M+2+CA\sqrt{n})/({\eta }^{2}n)=o(1)$. The discarded endpoint event has limiting probability $e^{-A^2}$; let $A\to \infty$. ThereforeSince $W$ has a continuous distribution, the corrected first-vertex degree in the LCD model tail isThis disproves the printed exponent $-y^2/8$ for $G_n^{(1)}$. The hint's factor is independently contradicted at $i=n$: its proposed upper bound tends to $1/\sqrt{2}$, whereasThus the printed concentration event has probability tending to zero, not one. Replacing its $2n$ by $n$ leads to the proven exponent $-y^2/4$. The exponent $-y^2/8$ would instead arise for $d_1(2n)/\sqrt{n}$, but then the graph has $2n$ vertices and the part (b) endpoint limit at $x/\sqrt{n}$ becomes $e^{-2x^2}$. It cannot repair all the printed claims with one convention. The literal part (c) is false for the named model; the full corrected limit and the source of the discrepancy are established above.

Use the large-deviation speed $a_N=N^{1+\epsilon }$ from part (a). For every $\eta >0$, the Chernoff bound for a normal distribution gives, for all sufficiently large $N$,Consequentlybecause the exponent has order $N^{1+2\epsilon }$, exceeding $a_N$ by a factor $N^{\epsilon }$. Thus $(A+B_N)/a_N$ and $A/a_N$ satisfy exponential equivalence. This conclusion does not require independence between $A$ and $B_N$, since their difference is exactly $B_N/a_N$.

The exponential equivalence theorem transfers the large deviation principle and its good rate function, givingLarge positive excursions are cheapest through the single exponential random variable; a negative excursion would require the Gaussian random variable sum to move on its faster scale. If $\sigma =0$, the deterministic shift $N\mu /a_N\to 0$ gives the same conclusion directly.

For the amount of work $A_j(0,t]$ offered by one flow in a time interval of length $t$, its effective bandwidth at parameter $\theta >0$ and timescale $t>0$ isIts units are work per unit time. The parameter $\theta$ measures the price placed on bursts: a stringent rare-overflow target generally requires a larger value of $\theta$ than a loose target. The timescale $t$ describes the duration of the congestion episode. When the limit exists, writeThis is the long-time effective bandwidth. It includes a burstiness cost, rather than just the mean offered rate. For a finite-time flow with the required moments, ${\lim }_{\theta \downarrow 0}{\alpha }_j(\theta ,t)=\mathbb{E}{A}_j(0,t]/t$, and effective bandwidth is increasing in $\theta$. If $A_j(0,t]/t$ is bounded, its limit as $\theta \to \infty$ is the essential supremum of that interval's input rate, the peak-rate limit. The analogous long-time mean limit requires the usual interchange or regularity assumptions.

For independent flows their cumulant-generating functions add, soThe Chernoff bound therefore gives, for any $\theta >0$ in the common domain,Optimizing over $\theta$ produces the relevant Legendre-Fenchel transform. The Cramér theorem states that sample means of independent and identically distributed inputs whose moment-generating function is finite near zero have a large deviation principle, with rate function equal to the Legendre-Fenchel transform of their cumulant-generating function. More generally, the Gärtner–Ellis theorem applies to a convergent scaled log moment-generating function when zero lies inside its domain and the limit is lower semicontinuous and essentially smooth. It gives the same transform as a good rate function. A sample-path version, together with the contraction principle for large deviations for the queue workload, translates input deviations into overflow deviations. The compact-time and infinite-horizon continuity/tail hypotheses must be checked for the chosen traffic model.

A particularly useful rigorous queue bound holds for inputs with stationary increments and independent increments, such that $\mathbb{E}{e}^{\theta A(t)}=e^{t\Lambda (\theta )}$. If $\Lambda (\theta )\le C\theta$, thenis a nonnegative supermartingale, since its conditional increment factor is $e^{(t-s)(\Lambda (\theta )-C\theta )}\le 1$. The maximal inequality for a nonnegative supermartingale on $[0,T]$, followed by $T\to \infty$, gives the continuous-time exponential workload boundHere $W$ is the stationary queue workload of the stable infinite-buffer queue, represented by input from the past. This directly bounds the supremum over time; applying a one-time Chernoff bound alone would not establish it.

For a nonzero Compound Poisson process with bounded positive packet sizes and mean input rate less than $C$, a positive root ${\theta }_{\ast }$ of $\Lambda (\theta )=C\theta$ exists and is unique. Here the root theorem can be made explicit:The upper bound was just proved. For the lower bound, use exponential tilting with density $e^{{\theta }_{\ast }(A(t)-Ct)}$ at time $t$. Under the tilted law the net input has positive mean drift ${\Lambda }^{\prime }({\theta }_{\ast })-C>0$, by strict convexity and the positive-root equation. The strong law of large numbers then makes the first crossing time ${\tau }_b$ finite almost surely under that law. Its overshoot is at most $s_{\max }$. Changing measure at ${\tau }_b$, first on $\{{\tau }_b\le T\}$ and then letting $T\to \infty$, givesDividing the logarithmic bounds by $b$ proves ${\lim }_{b\to \infty }{b}^{-1}\log \mathbb{P}(W\ge b)=-{\theta }_{\ast }$.

Thus the familiar admission rule compares ${\sum }_j{a}_j(\theta )$ with $C$, choosing $\theta$ from the desired buffer-tail exponent. For more general inputs, a logarithmic root theorem requires its own light-tail and renewal or sample-path hypotheses; the displayed supermartingale upper bound needs only the moment and increment assumptions stated above.

For any $s\ge 0$, $Y\ge 0$ implies $e^{sY}\ge 1$. Hence $1_{\{Y\ge 0\}}\le e^{sY}$, and taking expected values gives the Chernoff boundAt $s=0$ this is the trivial bound one; an infinite exponential moment merely gives a noninformative bound. For positive $s$ at which all required moment-generating functions are finite, define ${\alpha }_j(s)=s^{-1}\log \mathbb{E}[e^{s{X}_{ji}}]$. Independence of the source random variables impliesApplying the Chernoff bound to $Y=X-C$ givesConsequentlyHere $s>0$ and, for a nontrivial target, $\gamma >0$.

The effective bandwidth ${\alpha }_j(s)$ is the capacity charge of one source for this exponential-moment tail criterion. Independent sources contribute additively. It incorporates variability as well as mean demand: the Jensen inequality gives ${\alpha }_j(s)\ge \mathbb{E}{X}_{ji}$, and, under exponential integrability near zero, ${\alpha }_j(s)\to \mathbb{E}{X}_{ji}$ as $s\downarrow 0$. For bounded traffic its large-$s$ limit is the essential peak, as described by the mean and peak limits of effective bandwidth. Thus larger $s$ gives more weight to rare high demands. This is a one-window demand bound; a queue's overflow probability over many windows requires additional temporal modeling, not just this single-window calculation.

For the normal distribution $X_{ji}\sim N({\lambda }_j,{\sigma }_j^2)$, completing the square in its density gives the moment-generating functionWrite $m={\sum }_j{n}_j{\lambda }_j$ and $v={\sum }_j{n}_j{\sigma }_j^2$ for the aggregate mean and variance. The exponential-moment capacity condition becomesFor $v>0$, the last two terms are minimized at $s=\sqrt{2\gamma /v}$, where their sum is $\sqrt{2\gamma v}$. Therefore Gaussian effective bandwidth yields the sufficient conditionEquivalently, optimizing the exponential bound directly when $C>m$ gives $\exp [-(C-m{)}^2/(2v)]$; when $C\le m$ the best nonnegative-$s$ bound is one. The square-root condition is sufficient rather than necessary because an exponential bound does not equal the exact normal tail.

For the exact condition, independence and multiplication of the normal moment-generating functions show that $X\sim N(m,v)$. For $v>0$, let $\Phi$ be the standard normal distribution function. The normal law is continuous, soSince $\Phi$ is continuous and strictly increasing from zero to one, the exact Gaussian overflow constraint isThe constant depends only on the desired tail exponent $\gamma$, not on the source counts. It is positive when $\gamma >\log 2$, zero when $\gamma =\log 2$, and negative when $0<\gamma <\log 2$. For example, at $\gamma =\log 100$ the exact normal quantile is about $2.32635$, whereas the Chernoff bound uses $\sqrt{2\log 100}\approx 3.03485$; the latter reserves more capacity.

Finally, the positive-variance hypothesis must not be hidden. If $v=0$, then $X=m$ almost surely, and the zero-variance boundary of an overflow constraint gives $\mathbb{P}(X\ge C)=1_{\{m\ge C\}}$. For $\gamma >0$, the exact condition is then $m<C$. In particular $m=C$ does not meet the target even though substituting $v=0$ into the printed non-strict square-root inequalities would allow it. The displayed normal-quantile equivalence applies to nondegenerate Gaussian traffic; the deterministic case requires this strict boundary convention.

For every $s\ge 0$, the pointwise inequality $1_{\{Y\ge 0\}}\le e^{sY}$ holds: on the event the exponential is at least one, and off it the indicator is zero. Taking expected values and then the infimum proves the Chernoff boundAn infinite exponential moment merely gives a vacuous bound at that $s$; no existence assumption on moments is needed for this extended-value inequality.