The exponential non-uniform bound on the half-normal approximation for the number of returns to the origin

1.   Introduction

A symmetric simple random walk is a discrete-time stochastic process applicable in various fields, including physics, finance, biology, and probability theory. It is used to represent the movement of a particle involving randomness. Let $X_1, X_2, \dots, X_n$ be independent, identically distributed, random variables with

The symmetric simple random walk is a process $\left(S_n\right)_{n\geq 0}$ defined by

Here, $S_n$ represents the position of the walk in the $n^{\text{th}}$ step.

For the sake of convenience, let us assume that $n = 2m$ for natural number $m$. We are interested in the number of returns to the origin, which is defined by

with a probability mass function

for $r = 0, 1, 2, \dots, m$ (see [1, p. 178]).

From the point probability formula (1.1), we are able to compute the probability distribution of the statistic $K_n$ directly, particularly for cases where $n$ is relatively small. For example, we have

In situations where $n$ takes on large values, such as in this work where we assume that $n\geq 4$, the computation of the probability distribution becomes a time-consuming task and requires the utilization of a high-performance computing system. Consequently, this leads us to consider the approximation of the probability distribution of the statistic $K_n$. In ^[4], it is shown that

converges in distribution to a half-normal distribution denoted by $H(z)$ as $n\rightarrow \infty,$ where $H(z)$ is defined by

and $\Phi$ is a distribution function of a standard normal random variable. This implies that we can approximate the distribution of $\mathbb{K}_n$ using the half-normal distribution.

In the context of the approximation problem, it is imperative to establish a rigorous error bound stemming from the approximation. To this end, let $\epsilon_n(z)$ be the distance between the probability distribution of $\mathbb{K}_n$ and a half-normal distribution, i.e.,

and let

A bound on $\epsilon_n$ is termed a uniform bound, while a bound on $\epsilon_n(z)$ is referred to as a non-uniform bound. Döbler ^[1] showed in 2015 that when $n$ is an even positive integer, the following uniform bound holds:

Subsequently, Sama-ae, Chaidee, and Neammanee ^[2] further refined the error bounds by presenting polynomial non-uniform bounds of degree 3, which exhibit greater precision compared to the uniform bound (1.2). Their result states that if $z$ is a nonnegative real number and $n$ is an even positive integer, then,

More recently, Siripraparat and Neammanee ^[3] improved the bound for the number of returns to the origin by introducing polynomial non-uniform bounds with an arbitrary degree $k$ for any positive integer $k$. Presented below is their resultant finding. If $z\geq1$, $k\in \mathbb{N}$ and $n$ is an even positive integer such that $n\geq4$, then,

where $E\mathbb{K}_n^l\leq \prod\limits_{i = 0}^{\lfloor\frac{l}{2}\rfloor-1}(2^{l-2i-1})$ for $l = 2, 3, 4, \ldots$ and $\left\lfloor\frac{l}{2}\right\rfloor$ is the greatest integer less than or equal to $\dfrac{l}{2}$.

Notice that the bound (1.4) decreases as $k$ increases due to the term $\dfrac{1}{z^k}$. However, the bound also incorporates the term $E\mathbb{K}_n^{k+1}$, which increases with $k$. Consequently, in this study, we present a more precise bound in the form of an exponential non-uniform bound. The following represents our primary result.

Theorem 1. Let $z$ be a nonnegative real number. For any even positive integer $n$ such that $n\geq 4$, we have

The rest of this paper is structured as follows: Section 2 introduces Stein's method for half-normal approximation, while Section 3 presents the moment bounds for $K_n$ and $\mathbb{K}_n$. Section 4 is dedicated to proving a concentration inequality. Section 5 provides the proof of the main result. In Section 6, we present the application of $\mathbb{K}_n$, and finally, Section 7 gives a conclusion.

2.   Stein's method on half-normal approximation

The primary technique employed to establish the main result, which provides a half-normal approximation, is Stein's method combined with concentration inequalities, as demonstrated by Döbler ^[1], Sama-ae, Chaidee, and Neammanee ^[2], and Siripraparat and Neammanee ^[3]. Stein ^[5] introduced a method to establish the bounds in the normal approximation for random variables, a technique known as Stein's method. This approach has been extended to various other distributions, including the Poisson distribution ^[6], binomial distribution ^[7], negative binomial distribution ^[8], beta distribution ^[9], variance-gamma distribution ^[10], Laplace distribution ^[11,12], and exponential distribution ^[13,14,15]. Moreover, the Stein's method can also be extended to work with random vectors as well ^[16].

We introduce Stein's method as applied to the half-normal distribution, which is employed to approximate the distribution of any random variable Döbler ^[1] utilized this approach and presented Stein's equation for the standard half-normal approximation, outlined as follows:

where $f$ and $h$ are continuous, piecewise, differentiable functions on $[0, \infty)$.

To derive an equation for the distribution function from Eq (2.1), we define a function $h_z:[0, \infty)\rightarrow \mathbb{R}$ as follows for $z \geq 0$:

Consequently, for any random variable $W$, we obtain

where $f_z$ is the Stein solution of the differential Eq (2.1) with $h_z$ in (2.2) given by

for $z\geq 0.$ Note that

and

(see Döbler [1,p. 177]). From (2.3), we can bound $|E(f_z'(W))-E(Wf_z(W))|$ instead of $|P(W\leq z)-H(z)|$. This technique is called Stein's method.

In order to prove our main result, we need the following properties of $f_z$ and $f_z'$.

Proposition 1. Let $x, z > 0$.

$1)$ $0 < f_z(x) < e^{\frac{x^2-z^2}{2}}$ for $x\leq z.$

$2)$ $0 < f_z(x) < \min\left(1, \dfrac{1}{z}\right)$.

$3)$ $0\leq f'_z(x)\leq e^{\frac{x^2-z^2}{2}}+1.65e^{-\frac{z^2}{2}}$ for $x\leq z.$

Proof. 1) Let $x\leq z$. By (2.4) and the fact that

we obtain

Next, we consider $z < 1$. By recalling (2.4) and (2.7), we get

where we use the fact that

in the last inequality.

2) By Sama-ae, Chaidee, and Neammanee ([2, p. 781]), we have

for $x, z > 0$ and $z\geq 1.$ In the case that $z < 1$, we divide the proof into two cases.

Case 1: $x > z$ and $z < 1.$

By (2.4), (2.7), and (2.9), we get

Case 2: $x\leq z$ and $z < 1.$

We get immediately from (2.8) that $f_z(x) < 1.$

3) Let $x\leq z$. By Sama-ae, Chaidee, and Neammanee ([2,p. 785]), we obtain

for $z\geq 1.$ By (2.5), (2.7), and $z < 1$, we get

□

3.   Bounds for the moments of $K_n$ and $\mathbb{K}_n$

In this section, we consider the moments of $K_n$, which play a crucial role in establishing the exponential non-uniform bound (1.5).

Let $n = 2m$, where $m$ is a natural number. It is known that the number of returns to the origin $K_n$ with support $[0, m]\cap\mathbb{Z}$ has the following characterization

for all function $g:[-1, m]\cap\mathbb{Z}\to\mathbb{R}$ such that $g(-1) = 0$ ([1, p. 178]).

Following Lemma 3.1 in [1,p. 178], we obtain that

Using (3.1), Sama-ae, Chaidee, and Neammanee ([2, p. 783]) showed that

Siripraparat and Neammanee ([3,p. 46]) improved the moments of $\mathbb{K}_n$ to the general case by using the fact that

and obtained that

where $\left\lfloor\frac{k}{2}\right\rfloor$ is the largest integer less than or equal to $\dfrac{k}{2}$.

In this paper, we need to bound $Ee^{\mathbb{K}_n}$ by some constant. If we used (3.5), then,

which is divergent. Our aim in this section is to enhance the precision of (3.5), as in the following proposition.

Proposition 2. For the even positive integer $n$, we have

$1)$$EK_n^k\leq n \sum\limits_{l = 0}^{\frac{k-2}{2}}{k-1\choose 2l}EK_n^{2l}$, where $k$ is even and $k\geq2$;

$2)$$EK_n^k\leq n \sum\limits_{l = 0}^{\frac{k-3}{2}}{k-1\choose 2l+1}EK_n^{2l+1}$, where $k$ is odd and $k\geq3$.

Proof. By (3.4), we have

where

and

By the facts that

and (3.7), we obtain

$1)$ If $k$ is even, then by the fact that $(n+1)P(K_n = 0) = EK_n+1$ ([1,p. 178]) and (3.8), we obtain that

Next, we utilize the facts (3.9) and (3.10) to eliminate the odd moment in the second term and the backward terms. This results in the remaining terms being even moments as follows:

$2)$ Suppose that $k$ is odd. By (3.8), we establish

Using a similar technique as in (3.12), we retain the odd moments while eliminating even moments, and thus, we establish

From (3.6) and (3.11)–(3.13), we complete the proof. □

Note that we can bound additional moments by employing Proposition 2, transforming $K_n$ into $\mathbb{K}_n$, and utilizing the initial moments presented in (3.2), (3.3), and taking into account the condition $n\geq4$. Below are the fifth, sixth, and seventh moments for $\mathbb{K}_n$:

and

From the demonstration above, it is evident that one can calculate all moments dependent on the forward moments. However, these calculations can be straightforward in contrast to complex. In the next proposition, we offer a bound for the moments of $\mathbb{K}_n$ that relies solely on the parameter $k$ and does not depend on other moments. The technique used to derive this proposition is mathematical induction.

Proposition 3. Let $n\geq 4$. Then,

for $k\in\mathbb{N}$ and $k\geq6.$

Proof. Let $k\in\mathbb{N}$ with $k\geq 6$. The proof is divided into two cases.

Case 1: $k$ is even and $k\geq6$.

By (3.15), we see that

Assume that

is true for $k = 6, 8, 10, \ldots$. By Proposition 2(1), and the fact that

we have

where

and

To derive a bound for $B_{k+2}$, we apply the initial moments bound (3.3) while considering the conditions $k\geq6$ and $n\geq4$. This results in the bound (3.20) taking the form $\dfrac{(k+1)!}{(k-2)(k-3)}$ as follows:

Next, to obtain a bound for $C_{k+2}$, one can prove that, for a fixed $l\in\mathbb{N}$ such that $l\geq 3$, we have $\dfrac{k(k-4)(k-5)}{(k-2l+1)!(2l)(2l-4)(2l-5)}\leq 1$ for $k\geq 2l$. From this fact, (3.21), and $n\geq4$, we obtain that

By (3.22), we obtain

From (3.19), (3.8), (3.24), and (3.25), we conclude that

By mathematical induction, we have (3.17) when $k$ is an even positive integer and $k\geq6$.

Case 2: $k$ is odd and $k\geq7$.

By (3.16), we observe that

Therefore, the basic step is true.

To use mathematical induction, we assume that (3.17) is true for $k = 7, 9, 11, \ldots$.

By Proposition 2(1) and (3.18), we obatin

where

and

To bound $E_{k+2}, F_{k+2}$, and $G_{k+2}$, we can directly modify the technique in (3.8), (3.24), and (3.25) to obtain the following results:

and

By (3.26)–(3.29), we conclude that

From these two cases, we have completed the proof. □

4.   Concentration inequality

To prove our main theorem, we establish a concentration inequality for $\mathbb{K}_n$. Notably, Döbler ^[1] was the first mathematician providing a uniform concentration inequality for $\mathbb{K}_n$. His result is

(see [1,p. 181]). The term "uniform concentration inequality" indicates that the obtained bound is independent of $z$. Subsequently, the concentration inequality (4.1) is extended to a non-uniform concentration inequality in terms of $z^k$ for $k\in\mathbb{N}$, as detailed in ^[2,3]. In this section, we enhance the concentration inequality for $\mathbb{K}_n$ in terms of $e^z$, presented in Proposition 4.

Proposition 4. For $z\geq0$ and $n\geq4,$ we have

Proof. Let $f:\mathbb{R}\rightarrow \mathbb{R}$ be defined by

Then, we have $f'(t)\geq e^z > 0$ for $z-\frac{1}{\sqrt{n}} < t < z+\frac{1}{\sqrt{n}}$, which implies that $f$ is increasing.

We follow the argument of Sama-ae, Chaidee, and Neammanee ([2,pp. 784-785]) to obtain that

where

and

By Proposition 3, we have

and

From these facts, (3.2), (3.3), (3.14), and (3.15), we obtain:

and

By (4.2)–(4.6), we conclude that for $n\geq4$,

□

5.   Proof of Theorem 1

In this section, we give an exponential non-uniform bound for $\mathbb{K}_n$. From this point forward, we use $f$ to denote $f_z$, which is the unique solution of (2.4).

Proof of Theorem 1: By (1.2), we see that Theorem 1 is true for $z = 0$. Now, we assume $z > 0$ and $n\geq4$. Döbler ([1,p. 179]) and Siripraparat and Neammanee ([3,p. 51]) showed that

where

and

Bounding $|J_1|$: Applying the fundamental theorem of calculus and employing a truncation technique, we partition $|J_1|$ into two terms. By utilizing Proposition 1(3) in the first term and applying (2.6) in the second term, we can then obtain the following:

By (3.2) and (4.6), we obtain

Bounding $|J_2|$: By Markov's inequality, we obtain that

By employing a truncation technique together with the argument of $|J_1|$, and utilizing Proposition 1(1), Proposition 1(2), (4.5), and (5.3), we establish

Bounding $|J_3|$: Through the application of a truncation technique again, we represent $J_3$ in the following form:

where

and

From Proposition 1(1), Proposition 1(3), and (3.2), we obtain

where we use (3.2) and $n\geq4$ in the last inequality.

Using (2.6), (3.3), Proposition 1(2), (4.5), and (5.3), we have

Hence, we obtain that

Bounding $|J_4|$: It follows immediately from Proposition 4 that

By Stein's equation (2.3), (5.1), and (5.2)–(5.6), we conclude that

□

6.   Application

In this section, we provide an application of Theorem 1. Consider an option pricing following the binomial model (see ^[18,19] for more details) where the possible price of an option called "premium" is either increasing or decreasing. Let the initial premium be $S_0 = 0$, which means that there is no change in the price. Let a random variable $X_i$ be the change in the premium with distribution

Then, $S_n = \sum\limits_{i = 1}^n X_i$ represents the total change of the premium at period $n$. The premium is the same as at the initial state if $S_n = 0$ for some period of time $n$. If we need to forecast the chance that the premium is the same as the initial state in a fixed period of time, we can approximate this by the half-normal distribution.

By applying Theorem 1, we obtain an error bound for the half-normal approximation. We present numerical results for (1.2)–(1.5) to emphasize the sharpness of our result compared to other bounds. The results are displayed in Table 1. It is worth noting that our exponential non-uniform bound rapidly decreases, especially when $z$ is large.

In addition, when $k = 7$ is fixed and the value of $z$ varies from 30 to 200, we obtain the constants $C$ in the form of $\frac{C}{\sqrt{n}}$ for each error bound, as shown in Figure 1. The graph is plotted on a semi-log scale on the vertical axis. We observe that the constant $C$ for the bound (1.3) is approximately $10^{-5}$, and the bound (1.4) is approximately $10^{-9}$. However, our constant $C$ for (1.5) ranges between $10^{-65}$ and $10^{-9}$, steadily decreasing as $z$ increases. Indeed, the constant $C$ for (1.5) provides the best error bound.

7.   Conclusions

By utilizing Stein's method, this study derived an exponential non-uniform bound for the difference between the number of returns to the origin and a half-normal distribution in a symmetric simple random walk. Comparing our exponential non-uniform bound with (1.2), (1.3), and (1.4), it is evident that our bound of this study is sharper as shown in Table 1. Consequently, Theorem 1 is more suitable for evaluating the accuracy of this approximation. We finally provided an example, an option pricing, that supported our research and illustrated the significance of the result. In future work, we will attempt to generalize these criteria to the scenario involving an asymmetric random walk.

Author contributions

All authors contributed equally to this work. They have read and approved the final version of the manuscript for publication.

Use of AI tools declaration

The authors declare they have not used Artificial Intelligence (AI) tools in the creation of this article.

Acknowledgments

The authors would like to thank the referees for all of the valuable comments and suggestions that helped to improve the quality of the manuscript.

Conflict of interest

All authors declare that they have no conflicts of interest.