On a limit behaviour of a random walk penalised in the lower half-plane

Let random variables $\{\xi_{n}\}_{n\geq 1}$ be i.i.d. with a generic copy $\xi$ and ${\mathbb{E}}\xi=0,\ {\mathbb{E}}\xi^{2}=\sigma^{2}$; $\{\eta_{n}\}_{n\geq 1}$ are positive i.i.d., independent from the previous ones and with a generic copy $\eta$. We consider a random walk $\tilde{S}$:

(1)

$$\tilde{S}(0)=0,\ \tilde{S}(n+1)=\begin{cases}\tilde{S}(n)+\xi_{n+1}\ \text{if}\ \tilde{S}(n)>0,\\ \tilde{S}(n)+\eta_{n+1}\ \text{if}\ \tilde{S}(n)\leq 0.\end{cases}$$

If $\tilde{S}(n)\in(0,\infty)$, then the random walk has increments distributed as $\xi$ and on $(-\infty,0]$ as $\eta$. Jumps $\{\eta_{n}\}$ pushes the random walk up from the negative half-plane. This can be interpreted as some non-immediate reflection to the positive half-plane. Similar approach for stochastic differential equations is called the penalization method and leads to a reflected diffusion if penalizations below zero are big enough, see for example [Men83] or [Pil14, §1.4].

An interpretation of this model comes from the evaporation of gas from liquid in physics, for example, a model of ballistic evaporation [JLF14]. The usual form of speed distribution of a particle in a medium is Maxwell distribution. But in case when there is a medium change (a particle bounces off liquid) several papers have indicated that super- or sub-Maxwell distributions could apply [JLF14], [HKF16], [KS16].

Another interpretation is the following. Consider an online shop with a warehouse. Assume that the warehouse is replenished every day (e.g. under a long-term contract) and also that the expectation of supply equals the expectation of demand. So, the increments of the number of goods in the warehouse are mean-zero random variables $\{\xi_{k}\}$ if the warehouse is non-empty. In case when the virtual amount of goods in stock is negative, i.e., the warehouse is empty and we have unsatisfied orders, the shop seeks to refill the warehouse by buying batches of goods until it has a positive balance. In our model this refilling corresponds to the sequence $\{\eta_{k}\}$. If we consider a regular shop or a traditional queueing model, then the unsatisfied orders would be discarded and the walk couldn’t overjump a zero-level. While the shortage is not overcome (which may take some time), the shop does not sell any goods.

Our goal is to analyse the limit of the scaled sequence of the processes $\Big{\{}\frac{1}{\sqrt{n}}\tilde{S}(nt),\ t\in[0,1]\Big{\}}_{n\geq 1}$ as $n\to\infty$. Depending on the distribution of $\eta$ we want to distinguish two cases:

1. (1)

   $\eta$ has a finite expectation:

   $${\mathbb{E}}\eta<\infty.$$

2. (2)

   the distribution of $\eta$ has a slowly varying tail

   $${\mathbb{P}}(\eta>x)\sim l(x),\ l\in R_{0},$$

   where $R_{0}$ a set of slowly varying functions (check definition 1.4.2 in [BGT87]).

For the case $\mathrm{E}\eta<\infty$ we assume that $\tilde{S}$ is linearly interpolated for $t\geq 0$:

$$\tilde{S}(t)=\tilde{S}(\left\lfloor t\right\rfloor)+(t-\left\lfloor t\right\rfloor)\tilde{S}(\left\lceil t\right\rceil).$$

For the second case we assume $\tilde{S}$ has a flat-right interpolation for $t\geq 0$:

$$\tilde{S}(t)=\tilde{S}(\left\lfloor t\right\rfloor).$$

Our results show that intuitively understandable things happen: when $\eta$ has an expectation, the process behaves like a Brownian motion with a reflection; otherwise when $\eta$ has a slowly varying tail, the process blows up at the beginning.

Note that model (1) is equivalent (up to recounting of $\xi_{i}$ and $\eta_{i}$) to the following

(3)

$$\tilde{S}(0)=0,\ \tilde{S}(n)=\sum_{i=1}^{n-T(n)}\xi_{i}+\sum_{i=1}^{T(n)}\eta_{i},\ n\geq 1,$$

where $T(n)$ is the number of visits to $(-\infty,0]$ before the time $n$:

(4)

$$T(n)=\#\{k<n:\tilde{S}(k)\leq 0\},\ n\geq 1.$$

We work only with this representation in the paper further.

Denote

(5)

$$S_{\xi}(n)=\sum_{i=1}^{n}\xi_{i},\ S_{\eta}(n)=\sum_{i=1}^{n}\eta_{i}.$$

So

(6)

$$\tilde{S}(n)=S_{\xi}(n-T(n))+S_{\eta}(T(n)).$$

We set by definition $S_{\xi}(t):=S_{\xi}(\left\lfloor t\right\rfloor),\ S_{\eta}(t):=S_{\eta}(\left\lfloor t\right\rfloor),T(t):=T(\left\lfloor t\right\rfloor)$ for all $t\geq 0.$

Although the cases we discuss are very different, we tried to pick out common traits in Section 2.

In Section 3 we prove Theorem 1. We aim to show that $\frac{1}{\sqrt{n}}S_{\eta}(T(nt))$ converges to $-\min_{s\leq t}W(s)$ and do so by showing that the latter lies neatly between $\frac{1}{\sqrt{n}}S_{\eta}(T(nt)-1)$ and $\frac{1}{\sqrt{n}}S_{\eta}(T(nt))+\frac{1}{\sqrt{n}}\max_{i\leq nt}|\xi_{i}|$.

The proof of the second case can be found in Section 4 and is based on the observation that the overshoots above level $n$ of the random walk $S_{\eta}$ are much larger than $n$. This is a known property, proved by Rogozin, see for example Theorem 8.8.2 in [BGT87]. Thus we need to show that this overshoot happens before $T(n)$ because only in this way it could affect $\tilde{S}$.

Let $m$ be a (sign flipped) running minimum of $S_{\xi}$:

(7)

$$m(n)=-\min_{k\leq n}S_{\xi}(k).$$

By the Donsker theorem

$$\frac{1}{\sqrt{n}}S_{\xi}(n\cdot)\stackrel{{\scriptstyle w}}{{\to}}W(\cdot),\ n\to\infty,$$

meaning a weak convergence in $\mathrm{C}[0,1]$. By the Skorokhod Representation theorem (Theorem 6.7 in [Bil99]) we can construct a probability space which supports random elements $\hat{S}_{\xi}^{(n)}$ and $\hat{W}$ such that

$$\hat{S}_{\xi}^{(n)}\stackrel{{\scriptstyle d}}{{=}}S_{\xi},\ \hat{W}\stackrel{{\scriptstyle d}}{{=}}W,\ n\geq 1$$

and the uniform convergence holds

(10)

$$\frac{1}{\sqrt{n}}\hat{S}_{\xi}^{(n)}(nt)\rightrightarrows\hat{W}(t)\ \text{as}\ n\to\infty\ \text{a.s.}$$

for $t\in[0,1]$.

To emphasize that we work on this new space we will write a $\hat{\text{hat}}$ whenever we use random variables dependent on $\hat{S}_{\xi}^{(n)}$. Without loss of generality we may assume that this new probability space is reach enough and contains a copy of the sequence $\{\eta_{k}\}_{k\geq 1}$. We leave the same notation and assume that the original sequence $\{\eta_{k}\}_{k\geq 1}$ belongs to this probability space. Using sequences $\{\hat{S}_{\xi}^{(n)}(k)\}$ and $\{S_{\eta}(k)\}$ we construct copies $\{\hat{T}^{(n)}(k)\},\ \{\hat{\tilde{S}}^{(n)}(k)\},\ \{\hat{m}^{(n)}(k)\}$ of $\{T(k)\},\ \{{\tilde{S}}(k)\},\{m(k)\}$ similarly to formulas (4), (7), (6). Note that in this constructions sequences $\{\hat{S}_{\xi}^{(n)}(k)\}$ depend on $n$ but $\{S_{\eta}(k)\}$ does not. Often we will leave out indexing by $n$, that is $\hat{S}_{\xi}^{(n)}$ becomes $\hat{S}_{\xi}$.

It follows from inequality (8) that

(11)

$$S_{\eta}(\hat{T}(nt)-1)\leq\hat{m}(nt)\ \text{a.s.}$$

for all $t\geq 0$.

Divide both sides by $\sqrt{n}$. By (10) we have

(12)

$$\forall\varepsilon_{1}>0\ \exists n_{1}\ \forall n>n_{1}\quad\frac{1}{\sqrt{n}}S_{\eta}(\hat{T}(nt)-1)\leq-\min_{s\leq t}\hat{W}(s)+\varepsilon_{1}\ \text{a.s.}$$

Note that $\lim_{k\to\infty}\hat{T}(k)=+\infty$ a.s. because $\liminf_{k\to\infty}S_{\xi}(k)=-\infty$ a.s. Thus

(13)

$$\forall\varepsilon_{1}>0\ \exists n^{\prime}_{1}\ \forall n>n^{\prime}_{1}\quad\frac{\hat{T}(nt)-1}{\sqrt{n}}\leq\frac{\hat{T}(nt)-1}{S_{\eta}(\hat{T}(nt)-1)}(-\min_{s\leq t}\hat{W}(s)+\varepsilon_{1})\ \text{a.s.}$$

The strong law of the large numbers for $S_{\eta}$ implies

(14)

$$\limsup_{n\to\infty}\frac{\hat{T}(nt)}{\sqrt{n}}\leq\frac{-\min_{s\leq t}\hat{W}(s)}{{\mathbb{E}}\eta}\ \text{a.s.}$$

When ${\mathbb{E}}\eta=\infty$, the right hand side is $0$.

It suffices to prove uniform convergence over $t\in[0,1]$ as $n\to\infty$

(15)

$$\frac{1}{\sqrt{n}}S_{\eta}(\hat{T}(nt))\rightrightarrows-\min_{s\leq t}\hat{W}(s)\ \text{a.s.}$$

The other part of the statement of Theorem 1 is provided by (10).

From Lemma 1 and Lemma 2 we infer that

(16)		$\displaystyle\limsup_{n\to\infty}\frac{1}{\sqrt{n}}S_{\eta}(\hat{T}(nt)-1)\leq-\min_{s\leq t}\hat{W}(s)\ \text{a.s.}$
(17)		$\displaystyle\liminf_{n\to\infty}\Bigg{(}\frac{1}{\sqrt{n}}S_{\eta}(\hat{T}(nt))+\frac{\max_{i\leq n}|\hat{\xi}_{i}|}{\sqrt{n}}\Bigg{)}\geq-\min_{s\leq t}\hat{W}(s)\ \text{a.s.}$

To prove (15) it suffices to show

(18)

$$\frac{\max_{i\leq n}|\hat{\xi}_{i}|}{\sqrt{n}}\stackrel{{\scriptstyle{\mathbb{P}}}}{{\to}}0,\ n\to\infty.$$

and

(19)

$$\frac{1}{\sqrt{n}}|S_{\eta}(\hat{T}(nt))-S_{\eta}(\hat{T}(nt)-1)|=\frac{1}{\sqrt{n}}\eta_{\hat{T}(nt)}\stackrel{{\scriptstyle{\mathbb{P}}}}{{\to}}0,\ n\to\infty,$$

Observe that for a given $\delta>0$ due to (14) it is always possible to choose $K>0$ such that

$${\mathbb{P}}(\hat{T}(n)\leq K\sqrt{n})>1-\delta.$$

Hence both (18) and (19) follow from Theorem 6.2.1 in [Gut13].

It suffices to prove (2). Set

$$N_{\eta}(x)=\inf\{k:S_{\eta}(k)>x\},\ x\geq 0.$$

Let $c>0$, $K>0$, $0<\varepsilon<K$ and $0<t\leq 1$ be arbitrary real numbers, then

(20)

$\displaystyle\begin{split}\Big{\{}\max_{i\leq nt}\frac{\tilde{S}(i)}{\sqrt{n}}\geq c\Big{\}}&=\Big{\{}\max_{i\leq nt}\Big{(}S_{\xi}(i-T(i))+S_{\eta}(T(i))\Big{)}\geq c\sqrt{n}\Big{\}}\\ &\supset\Big{\{}\min_{i\leq n}S_{\xi}(i)\geq-K\sqrt{n}\Big{\}}\cap\Big{\{}S_{\eta}(T(nt))>(K+c)\sqrt{n}\Big{\}}\\ &=\Big{\{}\min_{i\leq n}S_{\xi}(i)\geq-K\sqrt{n}\Big{\}}\cap\Big{\{}N_{\eta}((K+c)\sqrt{n})\leq T(nt)\Big{\}}\\ &\supset\Big{\{}\min_{i\leq n}S_{\xi}(i)\geq-K\sqrt{n}\Big{\}}\cap\Big{\{}N_{\eta}(\varepsilon\sqrt{n})\leq T(nt)\Big{\}}\\ &\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\cap\Big{\{}\eta_{N_{\eta}(\varepsilon\sqrt{n})}>(K+c)\sqrt{n}\Big{\}}.\end{split}$

For the second inclusion observe that if

$$\eta_{N_{\eta}(\varepsilon\sqrt{n})}>(K+c)\sqrt{n},$$

then automatically

$$N_{\eta}((K+c)\sqrt{n})=N_{\eta}(\varepsilon\sqrt{n}).$$

Apply Lemma 3 with $j=l=\frac{nt}{2}$ and $a=\varepsilon\sqrt{n}$ to further inclusion (20)

(21)

$$\begin{split}&\Big{\{}\max_{i\leq nt}\frac{\tilde{S}(i)}{\sqrt{n}}\geq c\Big{\}}\\ \supset\Big{\{}\min_{i\leq n}S_{\xi}(i)\geq-K\sqrt{n}\Big{\}}&\cap\Big{\{}N_{\eta}(\varepsilon\sqrt{n})\geq T(nt)\Big{\}}\cap\Big{\{}\eta_{N_{\eta}(\varepsilon\sqrt{n})}>(K+c)\sqrt{n}\Big{\}}\\ \supset\Big{\{}\min_{i\leq n}S_{\xi}(i)\geq-K\sqrt{n}\Big{\}}&\cap\Big{\{}\min_{i\leq nt/2}S_{\xi}(i)\leq-\varepsilon\sqrt{n}\Big{\}}\cap\Big{\{}T(n)<\frac{nt}{2}\Big{\}}\\ &\cap\Big{\{}\eta_{N_{\eta}(\varepsilon\sqrt{n})}>(K+c)\sqrt{n}\Big{\}}.\\ \end{split}$$

Hence

(22)

$\displaystyle\begin{split}\mathbbP\Big{(}\max_{i\leq nt}\frac{\tilde{S}(i)}{\sqrt{n}}\geq c\Big{)}&\geq\mathbbP\Big{(}\text{r.h.s. of \eqref{broader_road}}\Big{)}\\ &=1-\mathbbP\Big{(}\text{complement to the r.h.s. of \eqref{broader_road}}\Big{)}\\ &\geq 1-\mathbbP\Big{(}\min_{i\leq n}S_{\xi}(i)\leq-K\sqrt{n}\Big{)}-\mathbbP\Big{(}\min_{i\leq nt/2}S_{\xi}(i)\geq-\varepsilon\sqrt{n}\Big{)}\\ &-\mathbbP\Big{(}T(n)>\frac{nt}{2}\Big{)}-\mathbbP\Big{(}\eta_{N_{\eta}(\varepsilon\sqrt{n})}<(K+c)\sqrt{n}\Big{)}.\end{split}$

Let $\delta>0$ be an arbitrary small number. We proceed by proving that every negative term in the r.h.s. of the last inequality is greater than $-\delta$ for $n$ big enough.

Choose $K>0$ and $0<\varepsilon<K$ so that

$$\mathbbP\Big{(}|N_{\eta}(0,1)|>K\Big{)}<\delta,\quad\mathbbP\Big{(}|N_{\eta}(0,1)|<\varepsilon\sqrt{\frac{2}{t}}\Big{)}<\delta.$$

Since

$$-\min_{i\leq nt}\frac{S_{\xi}(i)}{\sqrt{n}}\overset{w}{\to}|N_{\eta}(0,t)|,\ n\to\infty,$$

we get

$$\limsup_{n\to\infty}\Bigg{(}\mathbbP\Big{(}\min_{i\leq n}S_{\xi}(i)\leq-K\sqrt{n}\Big{)}+\mathbbP\Big{(}\min_{i\leq nt/2}S_{\xi}(i)\leq-\varepsilon\sqrt{n}\Big{)}\Bigg{)}\leq 2\delta.$$

It follows from Theorem 8.8.2 in [BGT87] that

(23)

$$\frac{\eta_{N_{\eta}(\varepsilon\sqrt{n})}}{\sqrt{n}}\stackrel{{\scriptstyle{\mathbb{P}}}}{{\to}}\infty,\ n\to\infty.$$

So the last term in the right hand side of (22) converges to 0.

Corollary 1 concludes the proof.