This paper was converted on www.awesomepapers.org from LaTeX by an anonymous user.
Want to know more? Visit the Converter page.

Energy saving approximation of Wiener process
under unilateral constraints333The work supported by RSF grant 21-11-00047.

M.A. Lifshits111Saint Petersburg State University, 199034, Saint Petersburg, University Emb., 7/9. [email protected], S.E. Nikitin222Saint Petersburg State University, 199034, Saint Petersburg, University Emb., 7/9. [email protected]
Abstract

We consider the energy saving approximation of a Wiener process under unilateral constraints. We show that, almost surely, on large time intervals the minimal energy necessary for the approximation logarithmically depends on the interval’s length. We also construct an adaptive approximation strategy that is optimal in a class of diffusion strategies and also provides the logarithmic order of energy consumption.

1 Problem setting and main result

Let AC[0,T]AC[0,T] denote the space of absolutely continuous functions on the interval [0,T][0,T]. For hAC[0,T]h\in AC[0,T] let us call kinetic energy

|h|T2:=0Th(t)2𝑑t.|h|_{T}^{2}:=\int_{0}^{T}h^{\prime}(t)^{2}dt.

In the works [1, 3, 7, 8, 9, 10, 11] the approximation of a random process sample path by the function hh of smallest energy was considered under various constraints on closeness between hh and the sample path. In particular, in [9] the energy saving approximation was studied for a Wiener process WW under bilateral uniform constraints.

For T>0,r>0T>0,r>0 let us define the set of admissible approximations as

MT,r±:={hAC[0,T]|t[0,T]:W(t)rh(t)W(t)+r;h(0)=0}M^{\pm}_{T,r}:=\left\{h\in AC[0,T]\,\big{|}\,\forall t\in[0,T]:W(t)-r\leq h(t)\leq W(t)+r;h(0)=0\right\}

and let

IW±(T,r):=inf{|h|T2|hMT,r±}.I^{\pm}_{W}(T,r):=\inf\left\{|h|_{T}^{2}\>\big{|}\>h\in M^{\pm}_{T,r}\right\}.

It was proved in [9] that for every fixed r>0r>0 it is true that

IW±(T,r)Ta.s.𝒞2r2,as T,\frac{I^{\pm}_{W}(T,r)}{T}\stackrel{{\scriptstyle\text{a.s.}}}{{\longrightarrow}}{\mathcal{C}}^{2}\,r^{-2},\qquad\textrm{as }T\to\infty,

where 𝒞0,63{\mathcal{C}}\approx 0,63 is some absolute constant (the exact value of 𝒞{\mathcal{C}} is unknown), i.e. the optimal approximation energy grows linearly in time.

In this work, we are interested in the behavior of a similar quantity under unilateral constraints, i.e. the set of admissible approximations is

MT,r:={hAC[0,T]|t[0,T]:h(t)W(t)r;h(0)=0},M_{T,r}:=\left\{h\in AC[0,T]\,\big{|}\,\forall t\in[0,T]:h(t)\geq W(t)-r;h(0)=0\right\},

and we are now interested in the behavior of

IW(T,r):=inf{|h|T2|hMT,r}.I_{W}(T,r):=\inf\left\{|h|_{T}^{2}\>\big{|}\>h\in M_{T,r}\right\}.

It is technically more convenient to translate the initial value of the approximating function to the point rr, so that this function runs above the trajectory of the approximated process WW. Let

MT,r:={hAC[0,T]|t[0,T]:h(t)W(t);h(0)=r}.M_{T,r}^{\prime}:=\left\{h\in AC[0,T]\,\big{|}\,\forall t\in[0,T]:h(t)\geq W(t);h(0)=r\right\}.

Since the sets of functions MT,rM_{T,r} and MT,rM_{T,r}^{\prime} differ by a constant shift, it is easy to see that

IW(T,r)=inf{|h|T2|hMT,r}.I_{W}(T,r)=\inf\left\{|h|_{T}^{2}\>\big{|}\>h\in M_{T,r}^{\prime}\right\}.

Our main result asserts that, when TT grows, the quantity IW(T,r)I_{W}(T,r) grows merely logarithmically.

Theorem 1

For every fixed r>0r>0 it is true that

IW(T,r)logTa.s.12,as T.\frac{I_{W}(T,r)}{\log T}\stackrel{{\scriptstyle\text{a.s.}}}{{\longrightarrow}}\frac{1}{2},\qquad\textrm{as }T\to\infty. (1)

In Section 2 we establish a connection between the unilateral energy saving approximation of arbitrary continuous function with its minimal concave majorant. In Section 3 we establish the necessary properties of Wiener process minimal concave majorant using the results of Groeneboom [6]. Section 4 contains the proof of Theorem 1.

In Sections 56 we consider a class of adaptive Markovian (diffusion) approximation strategies based on the current and past values of WW. We prove that in this class the optimal strategy is defined by the formula

h(t)=1h(t)W(t).h^{\prime}(t)=\frac{1}{h(t)-W(t)}\,.

For this strategy the energy consumption also has the logarithmic order but is two times larger than that for the optimal non-adaptive strategy using the information about the whole trajectory of WW. Namely,

|h|22logTa.s.1,as T.\frac{|h|_{2}^{2}}{\log T}\stackrel{{\scriptstyle\text{a.s.}}}{{\longrightarrow}}1,\qquad\textrm{as }T\to\infty.

2 Concave majorants as efficient approximations

It turns out that the optimal energy saving approximation under unilateral constraints may be described in terms of the minimal concave majorant (MCM) of the approximated function. Let w:[0,T]w:[0,T]\mapsto{\mathbb{R}} be a continuous function. Then the corresponding MCM w¯\overline{w} is the minimal concave function satisfying conditions

w¯(t)w(t),0tT.\overline{w}(t)\geq w(t),\qquad 0\leq t\leq T.
Proposition 2

Let r>w(0)r>w(0). Then the problem |h|T2min|h|_{T}^{2}\to\min under the constraints h(0)=rh(0)=r and

h(t)w(t),0tT,h(t)\geq w(t),\qquad 0\leq t\leq T,

has a unique solution χ\chi_{*} of the following form.

(a) If rmax0tTw(t)r\geq\max_{0\leq t\leq T}w(t), then χ(t)r\chi_{*}(t)\equiv r.

(b) If r<max0tTw(t)r<\max_{0\leq t\leq T}w(t), then χ\chi_{*} is defined differently on three intervals. On the initial interval, χ\chi_{*} is an affine function whose graph contains the point (0,r)(0,r) and is a tangent to the graph of w¯\overline{w}. Then χ\chi_{*} coincides with w¯\overline{w} until the first moment when the maximum of ww is attained. Finally, after that moment, χ\chi_{*} is a constant.

The optimal energy saving majorant χ\chi_{*} is shown in Figure 1.

Refer to caption
Figure 1: The optimal energy saving majorant.

Proof of the proposition: The problem’s solution exists since for every M>0M>0 the set of functions

{hAC[0,T]:h(0)=r,hw,|h|TM}\{h\in AC[0,T]:h(0)=r,h\geq w,|h|_{T}\leq M\}

is compact in the space of continuous functions equipped with the topology of uniform convergence and the functional ||T2|\cdot|_{T}^{2} is lower semi-continuous in this topology.

The uniqueness of the solution follows from the fact that the set of functions satisfying problem’s assumptions is convex and the functional ||T2|\cdot|_{T}^{2} is strictly convex on this set.

Let us describe the solution.

Since case (a) is trivial, we consider case (b).

Let χ()\chi(\cdot) be the solution of our problem. We show first that χ\chi is a convex non-decreasing function. Consider the function

χ1(t):=r+0tg(s)𝑑s,0tT,\chi_{1}(t):=r+\int_{0}^{t}g(s)ds,\qquad 0\leq t\leq T,

where g()g(\cdot) is the non-increasing monotone rearrangement of the function max{χ(),0}\max\{\chi^{\prime}(\cdot),0\}. Then χ1\chi_{1} is a concave non-decreasing function, χ1(0)=r\chi_{1}(0)=r and χ1(t)χ(t)w(t)\chi_{1}(t)\geq\chi(t)\geq w(t) for all t[0,T]t\in[0,T]. Therefore, χ1\chi_{1} satisfies the problem’s constraints. On the other hand,

|χ1|T2=0Tg(s)2ds=0Tmax{χ(),0}2ds|χ|T2.|\chi_{1}|_{T}^{2}=\int_{0}^{T}g(s)^{2}ds=\int_{0}^{T}\max\{\chi^{\prime}(\cdot),0\}^{2}ds\leq|\chi|_{T}^{2}.

Due to the problem solution uniqueness we obtain χ1=χ\chi_{1}=\chi. This equality proves that χ\chi is concave and non-decreasing.

Since χ\chi_{*} is the smallest concave non-decreasing function satisfying problem’s constraints, we have

χ(t)χ(t),0tT.\chi(t)\geq\chi_{*}(t),\qquad 0\leq t\leq T.

Furthermore, let us prove that χ(T)=χ(T)=max0tTw(t)\chi(T)=\chi_{*}(T)=\max_{0\leq t\leq T}w(t). Indeed, in case (b) the function

χ2(t):=min{χ(t),χ(T)},0tT,\chi_{2}(t):=\min\{\chi(t),\chi_{*}(T)\},\qquad 0\leq t\leq T,

satisfies both problem constraints and |χ2|T2|χ|T2|\chi_{2}|_{T}^{2}\leq|\chi|_{T}^{2}; by the uniqueness of the solution, we obtain χ=χ2\chi=\chi_{2}. In particular, χ(T)=χ(T)\chi(T)=\chi_{*}(T).

Finally, assume that the strict inequality χ(t0)>χ(t0)\chi(t_{0})>\chi_{*}(t_{0}) holds for some t0[0,T]t_{0}\in[0,T]. Then, since the function χ\chi_{*} is concave and non-decreasing, there exists a non-decreasing affine function ()\ell(\cdot) such that

χ(t)(t),0tT,\chi_{*}(t)\leq\ell(t),\qquad 0\leq t\leq T,

but (t0)<χ(t0)\ell(t_{0})<\chi(t_{0}). However, at the endpoints of the interval [0,T][0,T] the opposite inequality is true, because

χ(0)=r=χ(0)(0),χ(T)=χ(T)(0).\chi(0)=r=\chi_{*}(0)\leq\ell(0),\qquad\chi(T)=\chi_{*}(T)\leq\ell(0).

Therefore, there exists a non-degenerated interval [t1,t2][0,T][t_{1},t_{2}]\subset[0,T] such that t0[t1,t2]t_{0}\in[t_{1},t_{2}], (t1)=χ(t1)\ell(t_{1})=\chi(t_{1}), (t2)=χ(t2)\ell(t_{2})=\chi(t_{2}).

Since ()\ell^{\prime}(\cdot) is a constant, while χ()\chi^{\prime}(\cdot) is not a constant on [t1,t2][t_{1},t_{2}], it follows from Hölder inequality that

(t2t1)t1t2χ(t)2𝑑t>(t1t2χ(t)𝑑t)2=(χ(t2)χ(t1))2\displaystyle(t_{2}-t_{1})\int_{t_{1}}^{t_{2}}\chi^{\prime}(t)^{2}dt>\left(\int_{t_{1}}^{t_{2}}\chi^{\prime}(t)dt\right)^{2}=(\chi(t_{2})-\chi(t_{1}))^{2}
=\displaystyle= ((t2)(t1))2=(t1t2(t)𝑑t)2=(t2t1)t1t2(t)2𝑑t.\displaystyle(\ell(t_{2})-\ell(t_{1}))^{2}=\left(\int_{t_{1}}^{t_{2}}\ell^{\prime}(t)dt\right)^{2}=(t_{2}-t_{1})\int_{t_{1}}^{t_{2}}\ell^{\prime}(t)^{2}dt.

We obtain

t1t2χ(t)2𝑑t>t1t2(t)2𝑑t.\int_{t_{1}}^{t_{2}}\chi^{\prime}(t)^{2}dt>\int_{t_{1}}^{t_{2}}\ell^{\prime}(t)^{2}dt.

It follows that the function

χ3(t):=min{χ(t),(t)},0tT,\chi_{3}(t):=\min\{\chi(t),\ell(t)\},\qquad 0\leq t\leq T,

satisfies the problem’s constraints and |χ3|T2<|χ|T2|\chi_{3}|_{T}^{2}<|\chi|_{T}^{2} but this is impossible by the definition of χ\chi. Therefore, the assumption χ(t0)>χ(t0)\chi(t_{0})>\chi_{*}(t_{0}) brought us to a contradiction. \square

3 Minimal concave majorant of a Wiener process

We recall some notation and results from the article [6] that will be used in the sequel. Denote

τ(a):=sup{t>0|W(t)t/a=supu>0(W(u)u/a)}.\tau(a):=\sup\left\{t>0\,\big{|}\,W(t)-t/a=\sup_{u>0}\left(W(u)-u/a\right)\right\}.

The function aτ(a)a\mapsto\tau(a) is non-decreasing.

According to [6, Corollary 2.1] for every a>0a>0 the random variable τ(a)a2\frac{\tau(a)}{a^{2}} has the distribution density

q(t)=2𝔼(Xt1)+,t>0,q(t)=2\,{\mathbb{E}\,}\left(\frac{X}{\sqrt{t}}-1\right)_{+},\qquad t>0,

where x+:=x𝟏{x>0}x_{+}:=x{\mathbf{1}}_{\{x>0\}}, XX is a standard normal random variable.

Next, let W¯\overline{W} be the global MCM for the Wiener process W(t),t0W(t),t\geq 0. Define a random process LL as

L(a,b):=τ(a)τ(b)W¯(t)2𝑑t.L(a,b):=\int_{\tau(a)}^{\tau(b)}\overline{W}^{\prime}(t)^{2}dt.

Our study is essentially based on the following result due to Groeneboom.

Lemma 3

[6, Theorem 3.1]. For every a0>0a_{0}>0 the process X(t):=L(ea0,ea0+t),t0X(t):=L(e^{a_{0}},e^{a_{0}+t}),t\geq 0, is a pure jump process with independent stationary increments and 𝔼X(t)=t{\mathbb{E}\,}X(t)=t.

Moreover, there is an explicit description of the Lévy measure of XX in [6] but we do not need it here. We are only interested in the Kolmogorov’s strong law of large numbers for XX which asserts that

X(t)ta.s.1,as t.\frac{X(t)}{t}\stackrel{{\scriptstyle\text{a.s.}}}{{\longrightarrow}}1,\qquad\textrm{as }t\to\infty.

Using the definition of XX, letting a0=0a_{0}=0, and making the variable change V=etV=e^{t}, we may reformulate this result as

L(1,V)logVa.s.1,as V.\frac{L(1,V)}{\log V}\stackrel{{\scriptstyle\text{a.s.}}}{{\longrightarrow}}1,\qquad\textrm{as }V\to\infty. (2)
Lemma 4

For every δ(0,12)\delta\in\left(0,\frac{1}{2}\right) with probability 11 for all sufficiently large TT it is true that

τ(T12+δ)>T>τ(T12δ).\tau\left(T^{\frac{1}{2}+\delta}\right)>T>\tau\left(T^{\frac{1}{2}-\delta}\right). (3)

Proof: The lower bound is based upon the inequalities

(τ(T12δ)T2)\displaystyle{\mathbb{P}}\left(\tau\left(T^{\frac{1}{2}-\delta}\right)\geq\frac{T}{2}\right) =\displaystyle= (τ(T12δ)T12δT2δ2)\displaystyle{\mathbb{P}}\left(\frac{\tau\left(T^{\frac{1}{2}-\delta}\right)}{T^{1-2\delta}}\geq\frac{T^{2\delta}}{2}\right)
=\displaystyle= T2δ/2q(t)𝑑t\displaystyle\int_{T^{2\delta}/2}^{\infty}q(t)\,dt
=\displaystyle= T2δ/22𝔼(Xt1)+𝑑t\displaystyle\int_{T^{2\delta}/2}^{\infty}2\,{\mathbb{E}\,}\left(\frac{X}{\sqrt{t}}-1\right)_{+}dt
=\displaystyle= C1T2δ/2t(xt1)ex2/2𝑑x𝑑t\displaystyle C_{1}\int_{T^{2\delta}/2}^{\infty}\int_{\sqrt{t}}^{\infty}\left(\frac{x}{\sqrt{t}}-1\right)e^{-x^{2}/2}dxdt
\displaystyle\leq C2T2δ/2et/2t1/2𝑑tC2eT2δ/4,\displaystyle C_{2}\int_{T^{2\delta}/2}^{\infty}e^{-t/2}t^{-1/2}dt\leq C_{2}\,e^{-T^{2\delta}/4},

where C1,C2C_{1},C_{2} are some positive absolute constants.

Let Tn:=nT_{n}:=n, then the events Dn:={τ(Tn12δ)Tn2}D_{n}:=\left\{\tau\left(T_{n}^{\frac{1}{2}-\delta}\right)\geq\frac{T_{n}}{2}\right\} satisfy

n=1(Dn)<.\sum\limits_{n=1}^{\infty}{\mathbb{P}}(D_{n})<\infty.

Therefore, by Borel–Cantelli lemma, with probability 11 for all sufficiently large nn the event DnD_{n} does not hold, i.e. with probability 11 for all sufficiently large nn we have

τ(Tn12δ)<Tn2.\tau\left(T_{n}^{\frac{1}{2}-\delta}\right)<\frac{T_{n}}{2}. (4)

Let n2n\geq 2 be such that (4) holds for TnT_{n} and let T[Tn1,Tn]T\in[T_{n-1},T_{n}]. Since τ()\tau(\cdot) is non-decreasing, we have

τ(T12δ)τ(Tn12δ)<Tn2=n2n1=Tn1T.\tau\left(T^{\frac{1}{2}-\delta}\right)\leq\tau\left(T_{n}^{\frac{1}{2}-\delta}\right)<\frac{T_{n}}{2}=\frac{n}{2}\leq n-1=T_{n-1}\leq T.

This provides us with a required lower bound for sufficiently large TT.

In the same way, for the upper bound we have

(τ(T12+δ)2T)\displaystyle{\mathbb{P}}\left(\tau\left(T^{\frac{1}{2}+\delta}\right)\leq 2T\right) =\displaystyle= 02T2δ2𝔼(Xt1)+𝑑t\displaystyle\int_{0}^{2T^{-2\delta}}2\,{\mathbb{E}\,}\left(\frac{X}{\sqrt{t}}-1\right)_{+}dt
\displaystyle\leq C302T2δet/2t1/2𝑑tC4Tδ,\displaystyle C_{3}\int^{2T^{-2\delta}}_{0}e^{-t/2}t^{-1/2}dt\leq C_{4}T^{-\delta},

where C3,C4C_{3},C_{4} are some positive absolute constants.

Consider the sequence Tn:=2nT^{\prime}_{n}:=2^{n}. For the events Dn:={τ(Tn12+δ)2Tn}D^{\prime}_{n}:=\left\{\tau\left(T_{n}^{\frac{1}{2}+\delta}\right)\leq 2T_{n}\right\} we have

n=1(Dn)<.\sum\limits_{n=1}^{\infty}{\mathbb{P}}(D^{\prime}_{n})<\infty.

Therefore, by Borel–Cantelli lemma with probability 11 for all sufficiently large nn the event DnD^{\prime}_{n} does not hold, i.e. with probability 11 for all sufficiently large nn it is true that

τ(Tn12+δ)>2Tn.\tau\left(T_{n}^{\frac{1}{2}+\delta}\right)>2\,T_{n}. (5)

Let (5) be satisfied for some TnT_{n} and let T[Tn,Tn+1]T\in[T_{n},T_{n+1}]. Since τ()\tau(\cdot) is non-decreasing, we have

τ(T12+δ)τ(Tn12+δ)>2Tn=Tn+1T.\tau\left(T^{\frac{1}{2}+\delta}\right)\geq\tau\left(T_{n}^{\frac{1}{2}+\delta}\right)>2\,T_{n}=T_{n+1}\geq T.

This provides us with a required upper bound for all sufficiently large TT.

\square

The next theorem describes the asymptotic behavior of the energy of the minimal concave majorant for a Wiener process. For some r>0r>0 let W¯(r)\overline{W}^{(r)} denote MCM of a Wiener process WW on the whole real line, starting from the height rr. Then the majorant W¯(r)\overline{W}^{(r)} is an affine function on some initial interval [0,θ(r)][0,\theta(r)], its graph contains the point (0,r)(0,r) and is a tangent to the graph of W¯\overline{W}, while on [θ(r),)[\theta(r),\infty) the functions W¯(r)\overline{W}^{(r)} and W¯\overline{W} coinсide.

Theorem 5

Let W¯(r)\overline{W}^{(r)} be the global minimal concave majorant of WW starting from a height rr. Then, for every fixed rr it is true that

|W¯(r)|T2logTa.s.12,as T.\frac{|\overline{W}^{(r)}|_{T}^{2}}{\log T}\stackrel{{\scriptstyle\text{a.s.}}}{{\longrightarrow}}\frac{1}{2},\qquad\textrm{as }T\to\infty. (6)

Proof: Compare the quantities

|W¯(r)|T2=(W¯(r))(0)2θ(r)+θ(r)TW¯(t)2𝑑t,Tθ(r),|\overline{W}^{(r)}|_{T}^{2}=(\overline{W}^{(r)})^{\prime}(0)^{2}\theta(r)+\int_{\theta(r)}^{T}\overline{W}^{\prime}(t)^{2}\,dt,\qquad T\geq\theta(r),

and

L(1,T1/2±δ)=τ(1)τ(T1/2±δ)W¯(t)2𝑑t.L(1,T^{1/2\pm\delta})=\int_{\tau(1)}^{\tau(T^{1/2\pm\delta})}\overline{W}^{\prime}(t)^{2}\,dt.

They differ by a term (independent of TT) corresponding to the initial segment of W¯(r)\overline{W}^{(r)} and by the lower and upper integration limits; notice that the lower integration limits do not depend on TT in both cases.

By using Lemma 4 for comparing the upper integration limits, we obtain

lim infT|W¯(r)|T2logT\displaystyle\liminf\limits_{T\to\infty}\frac{|\overline{W}^{(r)}|_{T}^{2}}{\log{T}} \displaystyle\geq lim infTL(1,T1/2δ)logT;\displaystyle\liminf\limits_{T\to\infty}\frac{L\left(1,T^{1/2-\delta}\right)}{\log{T}};
lim supT|W¯(r)|T2logT\displaystyle\limsup\limits_{T\to\infty}\frac{|\overline{W}^{(r)}|_{T}^{2}}{\log{T}} \displaystyle\leq lim infTL(1,T1/2+δ)logT.\displaystyle\liminf\limits_{T\to\infty}\frac{L\left(1,T^{1/2+\delta}\right)}{\log{T}}.

Taking into account the law of large numbers (2) we have

12δlim infT|W¯(r)|T2logTlim supT|W¯(r)|T2logT12+δ.\frac{1}{2}-\delta\leq\liminf\limits_{T\to\infty}\frac{|\overline{W}^{(r)}|_{T}^{2}}{\log{T}}\leq\limsup\limits_{T\to\infty}\frac{|\overline{W}^{(r)}|_{T}^{2}}{\log{T}}\leq\frac{1}{2}+\delta.

Letting δ0\delta\searrow 0 yields the required result. \square

4 Proof of Theorem 1

Upper bound. The restriction of the global MCM starting from the height rr onto the interval [0,T] belongs to the set of admissible functions: W¯(r)MT,r\overline{W}^{(r)}\in M_{T,r}^{\prime}. We derive from Theorem 5 that

lim supTIW(T,r)logTlim supT|W¯(r)|T2logT12a.s.\limsup\limits_{T\to\infty}\frac{I_{W}(T,r)}{\log{T}}\leq\limsup\limits_{T\to\infty}\frac{|\overline{W}^{(r)}|_{T}^{2}}{\log{T}}\leq\frac{1}{2}\qquad\textrm{a.s.}

Lower bound. For r>0,T>0r>0,T>0 let W¯(r,T)\overline{W}^{(r,T)} denote the local MCM of the Wiener process W(t),t[0,T]W(t),t\in[0,T], starting from the height rr. Let χ\chi be the unique solution of the problem we are interested in, |h|T2min,hMT,r|h|_{T}^{2}\to\min,h\in M^{\prime}_{T,r}. Recall that its structure is described in Proposition 2. Since for large TT it is true that max0sTW(s)>r\max_{0\leq s\leq T}W(s)>r, for such TT the assumption of case (b) of that proposition is verified. In particular, it follows that

χ(t)=W¯(r,T)(t),0ttmax,\chi(t)=\overline{W}^{(r,T)}(t),\qquad 0\leq t\leq t_{\max},

where

tmax=tmax(T):=min{t:W(t)=max0sTW(s)}.t_{\max}=t_{\max}(T):=\min\{t:W(t)=\max_{0\leq s\leq T}W(s)\}.

Notice that the function τ()\tau(\cdot) can not take values from the interval (tmax,T)(t_{\max},T). Therefore, if for some aa it is true that τ(a)<T\tau(a)<T, then it is also true that τ(a)tmax\tau(a)\leq t_{\max}. In this case we have

χ(t)=W¯(r,T)(t)=W¯(r)(t),0tτ(a).\chi(t)=\overline{W}^{(r,T)}(t)=\overline{W}^{(r)}(t),\qquad 0\leq t\leq\tau(a).

It follows that

IW(T,r)=|χ|220τ(a)χ(t)2𝑑t=|W¯(r)|τ(a)2.I_{W}(T,r)=|\chi|_{2}^{2}\geq\int_{0}^{\tau(a)}\chi^{\prime}(t)^{2}\,dt=|\overline{W}^{(r)}|_{\tau(a)}^{2}.

Let us fix δ(0,1/2)\delta\in(0,1/2). Let a=a(T):=T1/2δa=a(T):=T^{1/2-\delta}. Then by Lemma 4 we have

T12δ1+2δ<τ(a)<TT^{\frac{1-2\delta}{1+2\delta}}<\tau(a)<T

a.s. for all sufficiently large TT. Furthermore, it follows from Theorem 5 that, as TT\to\infty,

|W¯(r)|τ(a)2logτ(a)2(1+o(1))12δ2(1+2δ)logT(1+o(1))a.s.|\overline{W}^{(r)}|_{\tau(a)}^{2}\geq\frac{\log\tau(a)}{2}\,(1+o(1))\geq\frac{1-2\delta}{2(1+2\delta)}\,\log T\,(1+o(1))\qquad\textrm{a.s.}

By combining these estimates, we obtain

IW(T,r)12δ2(1+2δ)logT(1+o(1))a.s.I_{W}(T,r)\geq\frac{1-2\delta}{2(1+2\delta)}\,\log T\,(1+o(1))\qquad\textrm{a.s.}

Finally, by letting δ0\delta\searrow 0, we arrive at

IW(T,r)12logT(1+o(1))a.s.,I_{W}(T,r)\geq\frac{1}{2}\,\log T\,(1+o(1))\qquad\textrm{a.s.,}

as required.

5 Adaptive Markovian approximation

In practice, it is often necessary to arrange an approximation (a pursuit) in real time (adaptively), when the trajectory of the approximated process is known not on the entire time interval but only before the current time instant. In view of the Markov property of Wiener process, a reasonable strategy is to define the speed of a pursuit hh as a function of current positions of the processes hh and WW, without taking past trajectories into account, i.e. let

h(t):=b(h(t),W(t),t).h^{\prime}(t):=b(h(t),W(t),t). (7)

On the qualitative level the function b(x,w,t)b(x,w,t) must tend to infinity, as xw0x-w\searrow 0, i.e. when the approximating process approaches the dangerous boundary it accelerates its movement trying to escape from a dangerous position. One has to optimize the function bb trying to reach the smallest average energy consumption. It is possible to reach the same logarithmic in time order of energy consumption as in the case of non-adaptive approximation but with somewhat larger coefficient. The difference of the coefficients represents the price we pay for not knowing the future of the process we try to approximate.

It is interesting to compare (7) with the form of the optimal adaptive strategy in the case of bilateral constraints [9] where

h(t)=b(h(t)W(t)).h^{\prime}(t)=b(h(t)-W(t)). (8)

The latter strategy is more simple because the speed is governed only by the distance between the approximated and the approximating processes and does not depend on time.

Let us make a time and space change

U(τ)\displaystyle U(\tau) :=\displaystyle:= eτ/2W(eτ),\displaystyle e^{-\tau/2}W(e^{\tau}),
z(τ)\displaystyle z(\tau) :=\displaystyle:= eτ/2h(eτ).\displaystyle e^{-\tau/2}h(e^{\tau}).

Recall that U()U(\cdot) is an Ornstein–Uhlenbeck process and therefore satisfies the equation

dU=Udτ2+dW~,dU=-\frac{U\,d\tau}{2}+d\widetilde{W}, (9)

where W~\widetilde{W} is a Wiener process. We have the following expression for the derivative of zz

z(τ)=12z(τ)+eτ/2h(eτ),z^{\prime}(\tau)=-\frac{1}{2}z(\tau)+e^{\tau/2}h^{\prime}(e^{\tau}), (10)

which yields

h(eτ)=eτ/2(z(τ)+z(τ)2).h^{\prime}(e^{\tau})=e^{-\tau/2}\left(z^{\prime}(\tau)+\frac{z(\tau)}{2}\right). (11)

Let us consider the distance between the approximated and approximating processes

Z(τ)\displaystyle Z(\tau) :=\displaystyle:= z(τ)U(τ).\displaystyle z(\tau)-U(\tau). (12)

We will study time-homogeneous diffusion strategies

dZ=b(Z)dτdW~.dZ=b(Z)d\tau-d\widetilde{W}. (13)

From equations (9) and (13) it follows that this is equivalent to

z(τ)+U(τ)2=b(Z(τ)),z^{\prime}(\tau)+\frac{U(\tau)}{2}=b(Z(\tau)),

which also implies

z(τ)+z(τ)2=b(Z(τ))+Z(τ)2.z^{\prime}(\tau)+\frac{z(\tau)}{2}=b(Z(\tau))+\frac{Z(\tau)}{2}. (14)

Before proceeding to optimization, let us see how the diffusion strategies act in the initial framework. By (11) and (14) we have

h(eτ)\displaystyle h^{\prime}(e^{\tau}) =\displaystyle= eτ/2(b(Z(τ))+Z(τ)2):=eτ/2b~(Z(τ))\displaystyle e^{-\tau/2}\left(b(Z(\tau))+\frac{Z(\tau)}{2}\right):=e^{-\tau/2}\ \widetilde{b}(Z(\tau)) (15)
=\displaystyle= eτ/2b~(eτ/2(h(eτ)W(eτ))),\displaystyle e^{-\tau/2}\ \widetilde{b}\left(e^{-\tau/2}\left(h(e^{\tau})-W(e^{\tau})\right)\right), (16)

where b~(x):=b(x)+x2\widetilde{b}(x):=b(x)+\tfrac{x}{2}. In other words, the form of the strategy is

h(t)=1tb~(1t(h(t)W(t))).h^{\prime}(t)=\frac{1}{\sqrt{t}}\ \widetilde{b}\left(\frac{1}{\sqrt{t}}\left(h(t)-W(t)\right)\right). (17)

We see that this class of strategies is space-homogeneous but, in general, not time-homogeneous.

Now we proceed to the optimization of the shift coefficient b()b(\cdot) determining the pursuit strategy. Let us use some basic facts about one-dimensional time-homogeneous diffusion, cf. [2, Ch.IV.11] and [5, Ch.2]. Let

B(x)\displaystyle B(x) :=\displaystyle:= 2xb(u)𝑑u,\displaystyle 2\int^{x}b(u)du, (18)
p0(x)\displaystyle p_{0}(x) :=\displaystyle:= eB(x).\displaystyle e^{B(x)}. (19)

Assume that condition

0dxp0(x)=\int_{0}\frac{dx}{p_{0}(x)}=\infty (20)

is verified. Then, in Feller classification, the point 0 is the entrance-boundary and not an exit-boundary for diffusion (13). This means that the diffusion ZZ remains forever in [0,)[0,\infty). Moreover, the function

p(x):=Q1p0(x),p(x):=Q^{-1}p_{0}(x), (21)

where Q=0p0(x)𝑑xQ=\int_{0}^{\infty}p_{0}(x)dx, is the density of the unique stationary distribution for ZZ. For the energy, by using (11) and (14), we obtain (a.s., as TT\to\infty)

1Th(t)2𝑑t\displaystyle\int_{1}^{T}h^{\prime}(t)^{2}dt =\displaystyle= 0logTh(eτ)2eτ𝑑τ=0logT(z(τ)+z(τ)2)2𝑑τ\displaystyle\int_{0}^{\log T}h^{\prime}(e^{\tau})^{2}e^{\tau}d\tau=\int_{0}^{\log T}\left(z^{\prime}(\tau)+\frac{z(\tau)}{2}\right)^{2}d\tau
=\displaystyle= 0logT(b(Z(τ))+Z(τ)2)2𝑑τ\displaystyle\int_{0}^{\log T}\left(b(Z(\tau))+\frac{Z(\tau)}{2}\right)^{2}d\tau
\displaystyle\sim logT0(b(x)+x2)2p(s)𝑑x\displaystyle{\log T}\int_{0}^{\infty}\left(b(x)+\frac{x}{2}\right)^{2}p(s)dx
=\displaystyle= logT0((logp2)(x)+x2)2p(x)𝑑x\displaystyle{\log T}\int_{0}^{\infty}\left(\left(\frac{\log p}{2}\right)^{\prime}(x)+\frac{x}{2}\right)^{2}p(x)dx
=\displaystyle= logT0(p(x)24p(x)+xp(x)2+x2p(x)4)𝑑x\displaystyle{\log T}\int_{0}^{\infty}\left(\frac{p^{\prime}(x)^{2}}{4p(x)}+\frac{xp^{\prime}(x)}{2}+\frac{x^{2}p(x)}{4}\right)dx
=\displaystyle= logT(12+0(p(x)24p(x)+x2p(x)4)𝑑x)\displaystyle{\log T}\left(-\frac{1}{2}+\int_{0}^{\infty}\left(\frac{p^{\prime}(x)^{2}}{4p(x)}+\frac{x^{2}p(x)}{4}\right)dx\right)
:=\displaystyle:= logT2+logT4J(p).\displaystyle-\frac{\log T}{2}+\frac{\log T}{4}J(p).

Taking into account condition (20), it remains to solve the variational problem

min{J(p)|0p(x)𝑑x=1,p(0)=0}\min\left\{J(p)\Big{|}\int_{0}^{\infty}p(x)dx=1,p(0)=0\right\}

over the class of densities concentrated on [0,)[0,\infty). After the variable change

y(x):=p(x)1/2,y(x):=p(x)^{1/2},

the variational problem transforms into

min{0(4y(x)2+x2y(x)2)𝑑x|0y(x)2𝑑x=1,y(0)=0}.\min\left\{\int_{0}^{\infty}\left(4y^{\prime}(x)^{2}+x^{2}y(x)^{2}\right)dx\ \Big{|}\int_{0}^{\infty}y(x)^{2}dx=1,y(0)=0\right\}.

We show in the next section that this minimum equals 66; it is attained at the function

y(x)=(2/π)1/4xexp(x2/4).y(x)=(2/\pi)^{1/4}\,x\,\exp(-x^{2}/4).

It follows that the asymptotic energy behavior for the optimal strategy is

1Th(t)2𝑑tlogT,T,\int_{1}^{T}h^{\prime}(t)^{2}dt\sim\log T,\quad T\to\infty,

i.e. the optimal choice of the shift in the adaptive setting leads to two times larger energy consumption than for the optimal strategy in the non-adaptive setting.

In order to find the optimal shift, write

p(x)=y(x)2=(2/π)1/2x2exp(x2/2)p(x)=y(x)^{2}=(2/\pi)^{1/2}\,x^{2}\,\exp(-x^{2}/2)

and we find from (18) – (21)

b(x)=12(lnp)(x)=1xx2.b(x)=\frac{1}{2}\,(\ln p)^{\prime}(x)=\frac{1}{x}-\frac{x}{2}.

Note that the density pp indeed satisfies the necessary condition (20).

Returning to the initial problem, we obtain the shift b~(x)=1x\widetilde{b}(x)=\tfrac{1}{x}, thus the strategy (17) takes the form

h(t)=1h(t)W(t).h^{\prime}(t)=\frac{1}{h(t)-W(t)}\,.

Curiously, the optimal diffusion strategy is not only space-homogeneous but also time-homogeneous, unlike arbitrary strategies of this class.

6 Solution of the variational problem

6.1 Quantum harmonic oscillator

Consider the Sturm–Liouville problem on the eigenvalues of a differential operator

{4y′′(x)+x2y(x)=γy(x),x0,y(0)=0.\begin{cases}-4y^{\prime\prime}(x)+x^{2}y(x)=\gamma\,y(x),&x\geq 0,\\ y(0)=0.\end{cases}

It represents a special case of the quantum harmonic oscillator equation, extensively studied by physicists, see [4, §23]. Its solution is well known. Usually one considers this equation on the entire real line. When performing the restriction to [0,)[0,\infty), one should take into account the boundary condition y(0)=0y(0)=0, hence, to keep the restrictions to [0,)[0,\infty) of odd solutions on {\mathbb{R}} and multiply them by 2\sqrt{2} in order to keep the normalization. We arrive at the orthonormal base L2[0,)L_{2}[0,\infty) that consists of the functions ψk,k21\psi_{k},k\in 2{\mathbb{N}}-1, given by

ψk(x)=(2kk!)1/2(2/π)1/4Hk(x/2)exp(x2/4),\psi_{k}(x)=(2^{k}k!)^{-1/2}(2/\pi)^{1/4}H_{k}(x/\sqrt{2})\exp(-x^{2}/4),

where Hk(x)=(1)kex2dkdxk(ex2)H_{k}(x)=(-1)^{k}e^{x^{2}}\tfrac{d^{k}}{dx^{k}}(e^{-x^{2}}) are Hermite polynomials; these functions satisfy

4ψk′′(x)+x2ψk(x)=γkψk(x),-4\psi_{k}^{\prime\prime}(x)+x^{2}\psi_{k}(x)=\gamma_{k}\psi_{k}(x),

where γk=2(2k+1)\gamma_{k}=2(2k+1).

In particular, the minimal eigenvalue is γ1=6\gamma_{1}=6, H1(x)=2xH_{1}(x)=2x, while the corresponding eigenfunction is ψ1(x)=(2/π)1/4xexp(x2/4)\psi_{1}(x)=(2/\pi)^{1/4}\,x\,\exp(-x^{2}/4).

6.2 Minimization

Consider quadratic form

G(y,z):=0(4y(x)z(x)+x2y(x)z(x))𝑑x.G(y,z):=\int_{0}^{\infty}\left(4y^{\prime}(x)z^{\prime}(x)+x^{2}y(x)z(x)\right)dx.

For twice differentiable functions satisfying additional assumption y(0)=0y(0)=0 integration by parts yields

G(y,z):=0(4y′′(x)+x2y(x))z(x)𝑑x.G(y,z):=\int_{0}^{\infty}\left(-4y^{\prime\prime}(x)+x^{2}y(x)\right)z(x)dx.

In particular,

G(ψk,ψl)=0γkψk(x)ψl(x)𝑑x={γk,k=l,0,kl,G(\psi_{k},\psi_{l})=\int_{0}^{\infty}\gamma_{k}\psi_{k}(x)\psi_{l}(x)dx=\begin{cases}\gamma_{k},&k=l,\\ 0,&k\not=l,\end{cases}

since (ψk)(\psi_{k}) is an orthonormal base.

If y=k21ckψky=\sum_{k\in 2{\mathbb{N}}-1}c_{k}\psi_{k}, then

0(4y(x)2+x2y(x)2)𝑑x=G(y,y)=k21ck2γkk21ck2γ1=γ10y(x)2𝑑x,\int_{0}^{\infty}\left(4y^{\prime}(x)^{2}+x^{2}y(x)^{2}\right)dx=G(y,y)=\sum_{k\in 2{\mathbb{N}}-1}c_{k}^{2}\gamma_{k}\geq\sum_{k\in 2{\mathbb{N}}-1}c_{k}^{2}\gamma_{1}=\gamma_{1}\int_{0}^{\infty}y(x)^{2}dx,

and for y=ψ1y=\psi_{1} the equality is attained in this chain. Therefore,

min{0(4y(x)2+x2y(x)2)𝑑x|0y(x)2𝑑x=1}=γ1=6.\min\left\{\int_{0}^{\infty}\left(4y^{\prime}(x)^{2}+x^{2}y(x)^{2}\right)dx\ \Big{|}\int_{0}^{\infty}y(x)^{2}dx=1\right\}=\gamma_{1}=6.

The authors are grateful to A.I. Nazarov for useful advice.

References

  • [1] D.I. Blinova, M.A. Lifshits. Energy of taut strings accompanying Wiener process and random walk in a band of variable width. J. Math. Sci., 2022, 268, No. 5, 573–588.
  • [2] A.N. Borodin. Stochastic processes. Birkhäuser, 2017.
  • [3] Z.A. Kabluchko, M.A. Lifshits. Adaptive energy saving approximation for stationary processes. Izvestia: Mathematics, 2019, 83, no. 5, 932–956.
  • [4] L.D. Landau, E.M. Lifshitz. Quantum Mechanics: Non-Relativistic Theory. Course of Theoretical Physics, Vol.3. 3rd Edition. Elsevier, 2013.
  • [5] A.N. Borodin, P. Salminen. Handbook of Brownian motion. Facts and Formulae. Birkhäuser, Basel, 1996.
  • [6] P. Groeneboom. The concave majorant of Brownian motion. Ann. Probab., 1983, 11, no.4, 1016–-1027.
  • [7] I. Ibragimov, Z. Kabluchko, M. Lifshits. Some extensions of linear approximation and prediction problems for stationary processes. Stoch. Proc. Appl., 2019, 129, 2758–2782.
  • [8] Z. Kabluchko, M. Lifshits. Least energy approximations for processes with stationary increments. J. Theor. Probab., 2017, 30, no. 1, 268–296.
  • [9] M. Lifshits, E. Setterqvist. Energy of taut string accompanying Wiener process. Stoch. Proc. Appl., 2015, 125, 401–427.
  • [10] M.A. Lifshits, A.A. Siuniaev. Energy of taut strings accompanying random walk. Probab. Math. Stat., 2021, 41, no.1, 9–23.
  • [11] E. Schertzer. Renewal structure of the Brownian taut string. Stoch. Proc. Appl., 2018, 128, 487–504.