Hostname: page-component-5cf477f64f-r2nwp Total loading time: 0 Render date: 2025-03-26T09:39:50.882Z Has data issue: false hasContentIssue false

Moderate deviations of many–server queues via idempotent processes – Corrigendum

Published online by Cambridge University Press:  24 March 2025

Anatolii Puhalskii*
Affiliation:
Institute for Problems in Information Transmission (IITP)
*
*Postal address: 19 B.Karetny, Moscow, Russia, 127051. Email: [email protected]
Rights & Permissions [Opens in a new window]

Abstract

Type
Corrigendum
Copyright
© The Author(s), 2025. Published by Cambridge University Press on behalf of Applied Probability Trust

A correction to Section 4 in [Reference Puhalskii1] is provided.

The expressions for $I_{x_0}^Q(q)$ in the statement of Theorem 5 and for $\overline I^Q_{q_0,x_0}(q)$ in [Reference Puhalskii1] are incorrect as the solutions of the associated variational problems do not account for the constraints $\int_0^1\dot w^0(x)\,\mathrm{d}x=0$ and $\int_0^1\dot k(x,t)\,\mathrm{d}x=0$ . The contents of Section 4 should be replaced with the following material.

4. Evaluating the deviation functions

This section is concerned with solving for $ I^Q_{x_0}(q)$ and $\overline I^Q_{q_0,x_0}(q)$ .

Theorem 5. Suppose that the c.d.f. F is an absolutely continuous function and $I_{x_0}^Q(q)<\infty$ . Then q is absolutely continuous, $(\dot q(t)-\int_0^t\dot q(s)\mathbf{1}{q(s)>0}F'(t-s)\,\mathrm{d}s,t\in\mathbb{R}_+)\in\mathbb L_2(\mathbb{R}_+)$ , the infimum in (2.5) is attained uniquely and

\begin{align*} I_{x_0}^Q(q)=\frac{1}{2}\,\int_0^\infty\hat{p}(t)\bigg(\dot q(t)-\int_0^t\dot q(s)\mathbf{1}{q(s)>0}F'(t-s)\,ds+(\beta-x_0^-) F_0'(t)\bigg)\,\mathrm{d}t,\end{align*}

where $\hat{p}(t)$ represents the unique $ \mathbb{L}_2(\mathbb{R}_+)$ solution p(t) of the Fredholm equation of the second kind,

(4.1) \begin{multline} (\mu+\sigma^2)p(t)= \dot q(t)-\int_0^t\dot q(s)\mathbf{1}{q(s)>0}F'(t-s)\,\mathrm{d}s+(\beta-x_0^-) F_0'(t)\\+F'_0(t)\int_0^\infty F_0'(s)p(s)\,\mathrm{d}s+\sigma^2\int_0^\infty F'(\lvert s-t\rvert)p(s)\,\mathrm{d}s\\+(\mu-\sigma^2)\int_0^\infty\int_0^{s\wedge t}F'(s-\tilde s)F'(t-\tilde s)\,\mathrm{d}\tilde s\, p(s)\,\mathrm{d}s,\end{multline}

with $\dot q$ , $F_0'$ and F’ representing derivatives.

Proof. Using that

(4.2) \begin{equation} \int_{\mathbb{R}_+^2} \mathbf{1}{x+s\le t}\,\dot k(F(x),\mu s)\,\mathrm{d}F(x)\,\mu\,\mathrm{d}s= \int_0^{ t}\int_0^{F(t-s)}\dot k(x,\mu s)\,\mathrm{d}x\,\mu\,\mathrm{d}s,\end{equation}

(2.6) can be expressed in the form

\begin{align*} q(t)=f(t)+\int_0^tq(t-s)^+\,\mathrm{d}F(s),\quad t\in\mathbb{R}_+,\end{align*}

with the functions f(t) and F(t) being absolutely continuous. The function q(t) is absolutely continuous by Lemma 8. In addition, (4.2) implies that, almost everywhere,

(4.3) \begin{equation} \frac{\mathrm{d}}{\mathrm{d}t}\,\int_{\mathbb{R}_+^2} \mathbf{1}{x+s\le t}\,{\dot k}(F(x),\mu s)\,\mathrm{d}F(x)\,\mu\,\mathrm{d}s=\int_0^t{\dot k}(F(s),\mu (t-s))F'(s)\,\mu\,\mathrm{d}s.\end{equation}

The infimum in (2.5) is attained uniquely by coercitivity and strict convexity of the function being minimised, cf., Proposition II.1.2 in [5]. By differentiating equation (2.6), in light of equation (4.3), we find that, almost everywhere,

\begin{multline*}\dot w^0(F_0(t))F_0'(t)+\sigma\,\dot w(t)-\int_0^tF'(t-s)\sigma\,\dot w(s)\,\mathrm{d}s+\int_0^t\dot k(F(s),\mu (t-s))F'(s)\,\mu\,\mathrm{d}s\\-\bigg( \dot q(t)-\int_0^t\dot q(s)\mathbf{1}{q(s)>0}F'(t-s)\,\mathrm{d}s+(\beta-x_0^-) F_0'(t)\bigg)=0.\end{multline*}

In addition, the requirements that $w^0(0)=w^0(1)=0$ and $k(0,t)=k(1,t)=0$ give rise to the constraints

(4.4) \begin{equation} \int_0^1\dot w^0(x)\,\mathrm{d}x=0\end{equation}

and

(4.5) \begin{equation} \int_0^1\dot k(x,t)\,\mathrm{d}x=0.\end{equation}

Introduce the map

\begin{multline*} \Phi:\, (\dot w^0,\dot w,\dot k)\to\bigg(\dot w^0(F_0(t))F_0'(t)+\sigma\,\dot w(t)-\int_0^tF'(t-s)\sigma\,\dot w(s)\,\mathrm{d}s\\+\int_0^t\dot k(F(s),\mu (t-s))F'(s)\,\mu\,\mathrm{d}s,t\in\mathbb{R}_+\bigg).\end{multline*}

Since $F_0'(t)$ is bounded by (2.1), $\Phi$ maps $V=\mathbb L_2([0,1])\times\mathbb L_2(\mathbb{R}_+)\times\mathbb L_2( [0,1]\times\mathbb{R}_+)$ to $\mathbb L_2(\mathbb{R}_+)$ . For instance, on using that $\int_0^\infty F'(s)\,\mathrm{d}s=1$ ,

\begin{align*} \int_0^\infty\bigg(\int_0^tF'(t-s)\dot w(s)\,\mathrm{d}s\bigg)^2\,\mathrm{d}t\le \int_0^\infty\int_0^tF'(t-s)\dot w(s)^2\,\mathrm{d}s\,\mathrm{d}t=\int_0^\infty\dot w(s)^2\,\mathrm{d}s<\infty\end{align*}

and

\begin{multline*} \int_0^\infty\bigg(\int_0^t\dot k(F(s),\mu (t-s))F'(s)\,\mu\mathrm{d}s\bigg)^2\,\mathrm{d}t\le \int_0^\infty\int_0^t\dot k(F(s),\mu (t-s))^2F'(s)\,\mu^2\mathrm{d}s\,\mathrm{d}t\\=\mu^2\int_0^\infty\int_0^1\dot k( x,t)^2\,\mathrm{d}x\,\mathrm{d}t<\infty.\end{multline*}

By Lagrange multipliers (see, e.g., Proposition III.5.2 in [5]) with $Y=\mathbb L_2(\mathbb{R}_+)^2\times\mathbb{R}$ and the set of componentwise nonnegative functions as the cone $\mathcal{C}$ ,

(4.6) \begin{multline} I_{x_0}^Q(q)={\sup}_{(p,\tilde p,r)\in \mathbb L_2(\mathbb{R}_+)^2\times\mathbb{R}}\;\inf_{\substack{(\dot w^0,\dot w,\dot k)\in\mathbb L_2([0,1])\\\times\mathbb L_2( \mathbb{R}_+)\times\mathbb L_2( [0,1]\times\mathbb{R}_+)}}\Bigg(\frac{1}{2}\int_0^1\dot w^0(x)^2\,\mathrm{d}x+\frac{1}{2}\int_0^\infty \dot w(t)^2\,\mathrm{d}t\\+\frac{1}{2}\int_0^\infty\int_0^1 \dot k(x,t)^2\,\mathrm{d}x\,\mathrm{d}t+\int_0^\infty p(t)\bigg(\dot q(t)+F'(t)x_0^++(\beta-x_0^-) F_0'(t)\\-\int_0^t\dot q(s)\mathbf{1}{q(s)>0}F'(t-s)\,\mathrm{d}s -\dot w^0(F_0(t))F_0'(t)-\sigma\,\dot w(t)+\int_0^tF'(t-s)\sigma\,\dot w(s)\,\mathrm{d}s\\-\int_0^t\dot k(F(s),\mu (t-s))F'(s)\,\mu\,\mathrm{d}s\bigg)\,\mathrm{d}t+r\int_0^1\dot w^0(x)\, \mathrm{d}x+\int_0^\infty\tilde p(t)\int_0^1\dot k(x,t)\,\mathrm{d}x\,\mathrm{d}t\Bigg).\end{multline}

Minimising in (4.6) yields, with $(\dot{\hat{ w}}^{0}(t),\dot{\hat w}(t), \dot{\hat{k}}(x,t))$ being optimal,

\begin{align*} \dot{\hat w}^0(x)-p(F_0^{-1}(x))+r=0,\\\dot{\hat w}(t)-\sigma p(t)+\sigma\int_0^\infty p(t+s)F'(s)\,\mathrm{d}s=0,\\\dot{\hat k}(x,t)-p\bigg(\frac{t}{\mu}+F^{-1}(x)\bigg)+\tilde p(t)=0.\end{align*}

For the latter, note that

\begin{multline*} \int_0^\infty p(t)\int_0^t\dot k(F(s),\mu (t-s))F'(s)\,\mu\,\mathrm{d}s\,\mathrm{d}t=\int_0^\infty\int_s^\infty p(t)\dot k(F(s),\mu (t-s))F'(s)\,\mu\,\mathrm{d}t\, \mathrm{d}s\\=\int_0^\infty\int_0^\infty p(t+s)\dot k(F(s),\mu t)F'(s)\,\mu\,\mathrm{d}t\,\mathrm{d}s=\int_0^\infty\int_0^1 p\bigg(\frac{t}{\mu}+F^{-1}(x)\bigg)\dot k( x,t)\,\mathrm{d}x\,\mathrm{d}t.\end{multline*}

Hence,

\begin{multline*} \!\!I_{x_0}^Q(q)={\sup}_{(p,\tilde p,r)\in \mathbb L_2(\mathbb{R}_+)^2\times\mathbb{R}}\bigg(\!\int_0^\infty\!\! p(t)\bigg(\dot q(t)-\!\!\int_0^t\!\!\dot q(s)\mathbf{1}{q(s)>0}F'(t-s)\,\mathrm{d}s+(\beta-x_0^-) F_0'(t)\!\bigg)\mathrm{d}t\\-\frac{1}{2}\bigg(\int_0^1(p(F_0^{-1}(x))-r)^2\,\mathrm{d}x+\sigma^2\int_0^\infty\bigg( p(t)-\int_0^\infty p(t+s)F'(s)\,\mathrm{d}s\bigg)^2\,\mathrm{d}t\\+\int_0^\infty\int_0^1 \bigg(p\bigg(\frac{t}{\mu}+F^{-1}(x)\bigg)-\tilde p(t))^2\,\mathrm{d}x\,\mathrm{d}t\bigg)\bigg).\end{multline*}

Given p, the optimal r is $\hat r=\int_0^1 p(F_0^{-1}(x))\,\mathrm{d}x$ and the optimal $\tilde p(t)$ is $\hat{\tilde p}(t)=\int_0^1p(t/\mu+F^{-1}(x))\,\mathrm{d}x$ . (As a by-product, $\hat w^0$ and $\hat k$ satisfy the constraints in (4.4) and (4.5).) Therefore,

(4.7) \begin{multline} I_{x_0}^Q(q)=\sup_{p\in \mathbb L_2(\mathbb{R}_+)}\bigg(\int_0^\infty p(t)\bigg(\dot q(t)-\int_0^t\dot q(s)\mathbf{1}{q(s)>0}F'(t-s)\,\mathrm{d}s+(\beta-x_0^-) F_0'(t)\bigg)\,\mathrm{d}t\\-\frac{1}{2}\bigg(\int_0^1(p(F_0^{-1}(x))-\int_0^1 p(F_0^{-1}(\tilde x))\,\mathrm{d}\tilde x)^2\,\mathrm{d}x+\sigma^2\int_0^\infty\bigg( p(t)-\int_0^\infty p(t+s)F'(s)\,\mathrm{d}s\bigg)^2\,\mathrm{d}t\\+\int_0^\infty\int_0^1 \bigg(p\bigg(\frac{t}{\mu}+F^{-1}(x)\bigg)-\int_0^1p\bigg(\frac{t}{\mu}+F^{-1}(\tilde x)\bigg)\,\mathrm{d}\tilde x\bigg)^2\,\mathrm{d}x\,\mathrm{d}t\bigg)\bigg).\end{multline}

As the function in the $\sup$ is strictly concave in p, a maximiser in (4.7) is specified uniquely; see, e.g., Proposition II.1.2 in [5]. The existence of the maximiser follows from Proposition III.5.2 in [5].

The function in the $\sup$ can be simplified if one notes that

\begin{multline*} \int_0^1(p(F_0^{-1}(x))-\int_0^1 p(F_0^{-1}(\tilde x))\,\mathrm{d}\tilde x)^2\,\mathrm{d}x=\int_0^\infty p(s)^2F_0'(s)\,\mathrm{d}s-\bigg(\int_0^\infty p(s)F'_0(s)\,\mathrm{d} s\bigg)^2,\end{multline*}
\begin{multline*} \int_0^1 \bigg(p\bigg(\frac{t}{\mu}+F^{-1}(x)\bigg)-\int_0^1p\bigg(\frac{t}{\mu}+F^{-1}(\tilde x)\bigg)\,\mathrm{d}\tilde x\bigg)^2\,\mathrm{d}x\\=\int_0^\infty p\bigg(\frac{t}{\mu}+s\bigg)^2F'(s)\,\mathrm{d}s-\bigg(\int_0^\infty p\bigg(\frac{t}{\mu}+s\bigg)F'(s)\,\mathrm{d} s\bigg)^2,\end{multline*}

and that

\begin{align*} \int_0^\infty p(s)^2F_0'(s)\,\mathrm{d}s+\mu\int_0^\infty\int_0^\infty p(t+s)^2\,F'(s)ds\,\mathrm{d}t=\mu\int_0^\infty p(s)^2\,\mathrm{d}s.\end{align*}

As a result,

(4.8) \begin{multline} I_{x_0}^Q(q)=\sup_{p\in\mathbb L_2(\mathbb{R}_+)}\bigg(\int_0^\infty p(t)\bigg(\dot q(t)-\int_0^t\dot q(s)\mathbf{1}{q(s)>0}F'(t-s)\,\mathrm{d}s+(\beta-x_0^-) F_0'(t)\bigg)\,\mathrm{d}t\\-\frac{1}{2}\bigg(\mu\int_0^\infty p(s)^2\,\mathrm{d}s-\bigg(\int_0^\infty p(s)F'_0(s)\,\mathrm{d} s\bigg)^2+\sigma^2\int_0^\infty\bigg(p(t)-\int_0^\infty p(t+s)F'(s)\,\mathrm{d}s\bigg)^2\,\mathrm{d}t\\-\mu\int_0^\infty\bigg(\int_0^\infty p(t+s)F'(s)\,\mathrm{d} s\bigg)^2\,\mathrm{d}t\bigg)\bigg).\end{multline}

Varying p in (4.8) implies (4.1). As the maximiser in (4.8) is unique, so is an $\mathbb L_2(\mathbb{R}_+)$ solution of the Fredholm equation (4.1).

It is noteworthy that the integral operator on $\mathbb L_2(\mathbb{R}_+)$ that appears on the right-hand side of (4.1) is not generally either Hilbert–Schmidt or compact, so the existence and uniqueness of $\hat p(t)$ is not a direct consequence of the general theory. Solving Fredholm equations numerically, such as (4.1), is discussed at quite some length in the literature. For instance, the collocation method with a basis of ‘hat’ functions could be tried: for $i\in\mathbb{N}$ and $n\in\mathbb{N}$ , let $t_i=i/n$ and $\ell_i(t)=(1-\lvert t-t_i\rvert)\mathbf{1}{t_{i-1}\le t\le t_i}$ , with $t_0=0$ . Then an approximate solution is

\begin{align*} p_n(t)=\sum_{i=1}^{n^2}p_n(t_i)\ell_i(t)\end{align*}

where the $p_n(t_i), i=1,\ldots,n^2$ , satisfy the linear system

\begin{multline*} (\mu+\sigma^2)p_n(t_i)-\sigma^2\sum_{j=1}^{n^2}p_n(t_j)\int_0^{n^2} \tilde K(t_i,s)\ell_j(s)\,\mathrm{d}s\\= \dot q(t_i)-\int_0^{t_i}\dot q(s)\mathbf{1}{q(s)>0}F'(t_i-s)\,\mathrm{d}s+(\beta-x_0^-) F_0'(t_i),\end{multline*}

with $\tilde K$ denoting the kernel of the integral operator in (4.1). For more background, see [3] and references therein.

Evaluating $\overline I^Q_{q_0,x_0}$ is done similarly:

\begin{multline*} \overline I^Q_{q_0,x_0}(q)=\sup_{(p,\tilde p,r)\in \mathbb{L}_2(\mathbb{R}_+)^2\times \mathbb{R}}\; \inf_{ \substack{(\dot w^0,\dot w,\dot k)\in \mathbb{L}_2([0,1])\\\times\mathbb L_2( \mathbb{R}_+)\times \mathbb L_2([0,1]\times\mathbb{R}_+)}}\bigg(\frac{1}{2}\int_0^1\dot w^0(x)^2\,\mathrm{d}x+\frac{1}{2}\int_0^\infty \dot w(t)^2\,\mathrm{d}t\\+\frac{1}{2}\int_0^\infty\int_0^1 \dot k(x,t)^2\,\mathrm{d}x\,\mathrm{d}t+\int_0^\infty p(t)\bigg(\dot q(t) +x_0 F_0'(t) -\sqrt{q_0}\dot w^0(F_0(t))F_0'(t) -\sigma\,\dot w(t)\\ +\int_0^tF'(t-s)\sigma\,\dot w(s)\,\mathrm{d}s -\int_0^t\dot k(F(s),\lambda (t-s))F'(s)\lambda\, \mathrm{d}s\bigg)\,\mathrm{d}t+r\int_0^1\dot w^0(x)\,\mathrm{d}x\\+\int_0^\infty\tilde p(t)\int_0^1\dot k(x,t)\,\mathrm{d}x\,\mathrm{d}t\bigg).\end{multline*}

Calculations as previously imply that

\begin{multline*} \overline I^Q_{q_0,x_0}(q)=\sup_{p\in \mathbb{L}_2(\mathbb{R}_+)}\bigg(\int_0^\infty p(t)(\dot q(t) +x_0 F_0'(t))\,\mathrm{d}t-\frac{1}{2}\bigg(q_0\int_0^\infty p(s)^2F_0'(s)\,\mathrm{d}s\\-q_0\bigg(\int_0^\infty p(s)F'_0(s)\,\mathrm{d} s\bigg)^2+\lambda\int_0^\infty p(t+s)^2F'(s)\,\mathrm{d}s-\lambda\bigg(\int_0^\infty p(t+s)F'(s)\,\mathrm{d} s\bigg)^2\\+\sigma^2\int_0^\infty\bigg( p(t)-\int_0^\infty p(t+s)F'(s)\,\mathrm{d}s\bigg)^2\,\mathrm{d}t\bigg)\bigg)=\frac{1}{2}\int_0^\infty\overline p(t)(\dot q(t) +x_0 F_0'(t))\,\mathrm{d}t,\end{multline*}

with $\overline p(t)$ being the $\mathbb L_2(\mathbb{R}_+)$ solution p(t) to the Fredholm equation of the second kind

\begin{align*} (\lambda+\sigma^2)p(t)=\dot q(t)+x_0F^{\prime}_0(t)+q_0F^{\prime}_0(t)\int_0^{\infty}F^{\prime}_0(s)p(s)\,\mathrm{d}s+\sigma^{2}\int_0^\infty F^{\prime}(\lvert s-t\rvert)p(s)\,\mathrm{d}s\\+(\lambda-\sigma^2)\int_0^\infty \int_0^{s\wedge t}F'(s-\tilde s)F^{\prime}(t-\tilde s)\,\mathrm{d}\tilde s\, p(s)\,\mathrm{d}s.\end{align*}

Competing interests

There were no competing interests to declare which arose during the preparation or publication process of this article.

References

Puhalskii, A. (2024). Moderate deviations of many–server queues via idempotent processes. Adv. Appl. Prob. Published online 20 December 2024 DOI: https://doi.org/10.1017/apr.2024.62 CrossRefGoogle Scholar