How far away is

$$\max_{x: x \in \{0, \ldots, N\}} \left|W\left(\frac{x}{N}\right)\right|$$

from

$$\max_{0 \leq t \leq 1} |W(t)|$$

In other words, if you simulate a Wiener process over a finite set of equidistant rational numbers in $[0,1]$ and take the maximum of the Wiener process at those points, how far away is that maximum away from the true maximum of the Wiener process (in any sense you want, be it probability, distribution, expectation, almost surely, etc.)?

This matters because I need to simulate this maximum and since I cannot do so over a continuous set on a computer I would like to know how much of an error I make by working with the next-best thing: a very fine discretization of $[0,1]$.

Another approach to simulating the maximum would be to find the maximum over the discrete set, take the two closest neighboring points, then simulate Brownian bridges connecting the points and computing a new maximum. This seems like a lot of computational work, though, and also seems to just move the problem elsewhere.

Any results appreciated.

New contributor
cgmil is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
  • In view of your previous question, is $W(t)$ one-dimensional or multidimensional? – Nate Eldredge Dec 7 at 4:21
  • @NateEldredge I was thinking single-dimensional, but a multidimensional answer would also be good. I was thinking that an answer in the univariate case would be basically just as informative. – cgmil Dec 7 at 20:13
  • Well, a cdf-based approach, like Iosif suggests, would tend to be harder in two or more dimensions. – Nate Eldredge Dec 7 at 21:00

The convergence of the discretized version $\max_{x \in \{0, \ldots, N\}} |W(x/N)|$ of $M:=\max_{0 \le t \le 1} |W(t)|$ to $M$ will be very slow -- at the rate of $1/\sqrt N$, according to Korolyuk 1961 and Nagaev 1970 (Korolyuk 1961 apparently exists only in Russian, but can be rather easily read using e.g. Google Translate), and then you will have to simulate a very large number $N$ of normal random variables -- just to get one realization of $M$.

A much more efficient way is to use the following explicit expression for the cdf of $M$: \begin{equation} P(M\le x)=\frac4\pi\, \sum _{k=0}^{\infty } \frac{(-1)^k}{2 k+1}\, \exp \left(-\frac{(2 k+1)^2 \pi ^2}{8 x^2}\right) \tag{1} \end{equation} for $x>0$; see e.g. page 3. The series in (1) converges very fast unless $x$ is very large. On the other hand, if $x$ is large, then $P(M\le x)$ is very close to $1$.

More specifically, if $x>x_0$, where $x_0=5.8471\ldots$ is the root of the equation $4(1-\Phi(x_0))=1/10^8$ and $\Phi$ is the standard normal cdf, then
\begin{equation} 0<1-P(M\le x)=P(M>x)\le P(M^+>x)+P(M^->x)=2P(M^+>x)=4(1-\Phi(x))<1/10^8, \end{equation} where $M^\pm:=\max_{0\le t\le1}(\pm W(t))$; the last displayed equality follows immediately from another formula on the same page 3.

On the other hand, for $x\in(0,x_0]$, retaining only the first $11$ summands of the alternating series in (1), we will get the approximation \begin{equation} P(M\le x)\approx F(x):=\frac4\pi\, \sum _{k=0}^{10} \frac{(-1)^k}{2 k+1}\, \exp \left(-\frac{(2 k+1)^2 \pi ^2}{8 x^2}\right) \end{equation} with an error less in absolute value than \begin{equation} \frac4\pi\,\frac1{2\times11+1}\, \exp \Big(-\frac{(2\times11+1)^2 \pi ^2}{8x_0^2}\Big)<3/10^{10}. \end{equation}

Now, using the inverse transform sampling method, we can get very close approximations $m_1,m_2,\dots$ to iid realizations of $M$ as solutions of the equations $F(m_i)=u_i$ for $m_i$, where $u_1,u_2,\dots$ are iid realizations of a random variable uniformy distributed between $0$ and $1$. It then takes under a second in Mathematica to simulate $1000$ very close approximations $m_1,\dots,m_{1000}$ to iid realizations of $M$:

enter image description here

  • You make good points. When I needed to work with this random variable, I used the CDF since I had access to it; I did not try to estimate it with simulation. My recent interest in this again was due to the need to work with the max of the norm of a multivariate Wiener process, and I didn't know there was a closed form for that CDF (in fact I told there neither was nor would be one) until a few days ago. But I don't want to call this question "answered" because I'm not sure if you literally actually answered the question. What would you say if the CDF were not known explicitly? – cgmil Dec 9 at 5:58
  • Basically I would like my mathematical curiosity satisfied with some answer to the literal question. Is that in your first sentence? Are the two maxima different by about $1/\sqrt{N}$? – cgmil Dec 9 at 6:06
  • I have added references concerning the rate $1/\sqrt N$. – Iosif Pinelis Dec 9 at 18:51

Your Answer

cgmil is a new contributor. Be nice, and check out our Code of Conduct.

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.