# Is there a generalised version of the Donsker invariance principle for a “sort-of continuous-time-random-walk”?

(The following question arises from my Math.SE question https://math.stackexchange.com/questions/3643865.)

Let $$\rho$$ be a probability measure on $$\mathbb{R} \times (0,\infty)$$, and writing $$\ \pi_1 \colon \mathbb{R} \times (0,\infty) \to \mathbb{R}\$$ and $$\ \pi_2 \colon \mathbb{R} \times (0,\infty) \to (0,\infty)\$$ for the coordinate projections, suppose that $$\int \pi_2^2 \, d\rho < \infty$$, $$\int \pi_1^2 \, d\rho=\int \pi_2 \, d\rho$$ and $$\int \pi_1 \, d\rho = 0$$.

For each $$\lambda>0$$, consider the one-dimensional stochastic process $$(W^{(\lambda)}_t)_{t \geq 0}$$ which, for each sample point $$\omega$$, linearly interpolates the discrete-point-mapping \begin{align*} t_n(\omega) \ \mapsto \ &\frac{1}{\sqrt{\lambda}} \sum_{i=1}^n X_i(\omega) \\ t_n(\omega) \ := \ &\frac{1}{\lambda} \sum_{i=1}^n \Delta_i(\omega) \quad \text{for each n \geq 0} \end{align*} where the random vectors $$\begin{pmatrix} X_i \\ \Delta_i \end{pmatrix}$$, $$i \geq 1$$, are i.i.d. with law $$\rho$$.

Equipping $$C([0,\infty),\mathbb{R})$$ with the topology of uniform convergence on bounded sets, is it the case that the $$C([0,\infty),\mathbb{R})$$-valued random variable $$(W^{(\lambda)}_t)_{t \geq 0}$$ converges in distribution to a Wiener process as $$\lambda \to \infty$$?

The case where $$\pi_2$$ projects $$\rho$$ onto a Dirac mass is essentially Donsker's invariance principle; so I am wondering about the more general case. I emphasise that I do not wish to assume that $$\pi_1$$ and $$\pi_2$$ are independent under $$\rho$$.

I realise it would probably be good to say a bit more about the motivation behind this question.

The Wiener process has some nice properties, such as increments that are stationary and memoryless. Donsker's theorem describes one way in which a Wiener process can physically arise, namely as a random walk with small step distance $$\sqrt{\Delta}$$ and high step frequency $$\frac{1}{\Delta}$$. But as a continuous-time process, this random walk does not have increments that are both stationary and exhibit decay of correlations.

There may be situations in which one wishes to work with a Donsker-like approximation to Brownian motion (e.g. SDEs driven by "bounded noise", to avoid extreme events in the long-term behaviour of the system), but keeping some of the nice properties of Brownian motion, such as increments that are stationary and exhibit decay of correlations. The raw form of Donsker's theorem will not achieve this, and so some modified version such as described above can be used.

• @IosifPinelis For each $\lambda$, if we define the set $S_\lambda(\omega):=\left\{\frac{1}{\lambda}\sum_{i=1}^n\Delta_i(\omega):n\in\mathbb{N}\cup\{0\}\right\}\subset [0,\infty)$, then the map $t\mapsto W^{(\lambda)}_t(\omega)$ on $[0,\infty)$ is defined to be linear between each consecutive pair of points in $S_\lambda(\omega)$, with $W^{(\lambda)}_{\frac{1}{\lambda}\sum_{i=1}^n\Delta_i(\omega)}(\omega)=\frac{1}{\sqrt{\lambda}}\sum_{i=1}^n X_i(\omega)$ for each $n \in \mathbb{N}\cup\{0\}$. Do you think that how I phrased it in the post wasn't clear enough? – Julian Newman May 14 '20 at 20:13
• So in words, you want to start with a process $Z_t$ that waits for time $\Delta_i$ and then jumps by an amount $X_i$, where $\Delta_i$ is not necessarily independent of $X_i$? Then $W_t^{(\lambda)}$ is the linearly interpolated and rescaled version of this process, and you want to see if this converges weakly to Brownian motion in the scaling limit? – Nate Eldredge May 14 '20 at 21:11
• @JulianNewman : I had misread some of your post, sorry. However, I think the limit process should be $t\mapsto(B_t,t)$, rather than a Brownian motion $t\mapsto B_t$. – Iosif Pinelis May 14 '20 at 21:49
• @NateEldredge Exactly! – Julian Newman May 14 '20 at 22:01
• @IosifPinelis No $(W_t^{(\lambda)})$ is not an $(\mathbb{R} \times (0,\infty))$-valued process, it is simply an $\mathbb{R}$-valued process. – Julian Newman May 14 '20 at 22:08

I think Iosif Pinelis is correct, but his comment should be expanded as follows.

Notation: let $$p(t) = \lfloor t + 1\rfloor - t , \qquad q(t) = t - \lfloor t\rfloor .$$ Whenever we have a discrete-time process $$Z_n$$, we extend it into a continuous one, piecewise linear, defined by: $$Z_t = p(t) Z_{\lfloor t\rfloor} + q(t) Z_{\lfloor t + 1\rfloor} .$$ With no loss of generality assume that $$\mathbb{E} \Delta_n = 1$$ to simplify the notation.

Step 1. The bi-variate process $$(Y_n,Z_n) = (\sum_{i=1}^n (\Delta_i - 1), \sum_{i=1}^n X_i)$$ satisfies Donsker's invariance principle, that is, $$(Y^{(\lambda)}_t, Z^{(\lambda)}_t) = (\lambda^{-1/2} Y_{\lambda t}, \lambda^{-1/2} Z_{\lambda t})$$ converges weakly (in the Banach space of continuous functions on $$[0,T]$$, for any given $$T > 0$$) to a two-dimensional Brownian motion $$(\tilde Y_t, \tilde Z_t)$$.

Step 2. Let $$(T_n,Z_n) = (\sum_{i=1}^n \Delta_i, \sum_{i=1}^n X_i) = (Y_n + n, Z_n)$$ and consider $$(T^{(\lambda)}_t, Z^{(\lambda)}_t) = (\lambda^{-1} T_{\lambda t}, \lambda^{-1/2} Z_{\lambda t}) = (\lambda^{-1/2} Y^{(\lambda)}_t + t , Z^{(\lambda)}_t) .$$ It is then easy to see that $$(T^{(\lambda)}_t, Z^{(\lambda)}_t)$$ converges weakly (in the same sense) to $$(\tilde T_t, \tilde Z_t) = (t, \tilde Z_t),$$ where $$\tilde Z_t$$ is the Brownian motion.

This is somewhat technical, but relatively standard, I think: one can use the characterisation of weak convergence of processes in terms of convergence of finite-dimensional distributions and equicontinuity (or $$J$$-compactness if one prefers the more general approach via Shorokhod topology). See Theorem 1.6.2 in [Silvestrov D.S. (2004) Weak convergence of stochastic processes. In: Limit Theorems for Randomly Stopped Stochastic Processes. Probability and its Applications. Springer, London] for details.

Step 3. The process $$W_t^{(\lambda)}$$ is a continuous, piecewise linear process defined by $$W^{(\lambda)}_t = Z^{(\lambda)}_{(T^{(\lambda)})^{-1}_t} .$$ Our claim is: this process converges weakly $$\tilde W_t = \tilde Z_{\tilde T^{-1}_t} = \tilde Z_t.$$

Here we use the very definition of weak convergence. Let $$\Phi$$ be a continuous functional on the space of paths $$\omega_t$$ of $$W^{(\lambda)}_t$$ or $$\tilde W_t$$. Then $$\Phi$$ induces a functional $$\Psi$$ on the space of paths $$(\tau_t, \zeta_t)$$ of $$(T^{(\lambda)}_t, Z^{(\lambda)}_t)$$ and $$(\tilde T_t, \tilde Z_t)$$, in the following sense: $$\Psi((\tau_t), (\zeta_t)) = \Phi((\tau_{\zeta^{-1}_t})) ,$$ where $$\zeta^{-1}_t = \inf \{ s : \tau_s \ge t \}$$ is the generalised inverse of $$\zeta_t$$.

Of course $$\Psi$$ is no longer continuous. However, it is easy to see that the set of discontinuities of $$\Psi$$ has zero measure with respect to the law of $$(\tilde T_t, \tilde Z_t)$$. Roughly speaking: the paths of $$(\tilde T_t, \tilde Z_t)$$ are of the form $$((\tilde \tau_t), (\tilde \zeta_t))$$, where $$\tau_t = t$$ for all $$t$$. Given such a path and $$\varepsilon > 0$$, choose $$\delta > 0$$ so that the $$\delta$$-modulus of continuity of $$\tilde \zeta_t$$ is less than $$\varepsilon$$. If $$(\tau_t)$$ is $$\delta$$-close to $$(\tilde \tau_t) = (t)$$ and $$(\zeta_t)$$ is $$\varepsilon$$-close to $$(\tilde \zeta_t)$$, then $$|\tau_t^{-1} - t| < \delta$$ (by a simple calculus exercise), and hence $$|\omega_t - \tilde \omega_t| = |\zeta_{\tau_t^{-1}} - \tilde \zeta_t| \leqslant |\zeta_{\tau_t^{-1}} - \tilde \zeta_{\tau_t^{-1}}| + |\tilde Z_{\tau_t^{-1}} - \tilde Z_t| \le 2 \varepsilon .$$ This proves continuity of $$\Psi$$ at $$((\tilde \tau_t), (\tilde \zeta_t))$$, as desired.

This is perfectly sufficient for our needs: weak convergence of $$(T^{(\lambda)}_t, Z^{(\lambda)}_t)$$ to $$(\tilde T_t, \tilde Z_t)$$ implies that $$\mathbb{E} \Psi((T^{(\lambda)}_t), (Z^{(\lambda)}_t)) = \mathbb{E} \Phi((W^{(\lambda)}_t))$$ converges to $$\mathbb{E} \Psi((\tilde T_t), (\tilde Z_t)) = \mathbb{E} \Phi((\tilde W_t) ,$$ and consequently $$W^{(\lambda)}_t$$ converges weakly to $$\tilde W_t$$.

I am sure the above argument is well-known, for instance, in the literature on "Lévy flights", "continuous-time random walks", or similar. There are still some details missing, but I hope the idea is now clear.

• Thank you. I think my intuition had already pretty much arrived at where you got to, and my real trouble is justifying the last step - which you say you believe should be easy? Essentially your logical format is "we know $f_n(x_\ast)\to a$ and $x_n\to x_\ast$, and we need to deduce $f_n(x_n)\to a$". My crude visual intuition is that this holds in our case, but it's certainly not obvious to me; when we multiply the deviation of $T_{\lfloor\lambda t\rfloor/\lambda}$ away from $t\mathbb{E}\Delta_1$ by the unsigned gradient $\sqrt{\lambda}$ of $W^{(\lambda)}$, the result doesn't tend to $0$. – Julian Newman May 18 '20 at 0:40
• Time permitting, I will try to expand my comment later this week. – Mateusz Kwaśnicki May 18 '20 at 6:50
• I expanded the answer, but there are still details missing. Sorry for that, this is the best I can do now. – Mateusz Kwaśnicki May 22 '20 at 13:12
• Thank you very much, I'm now certainly satisfied. I have added an answer that essentially follows your argument with a slightly different structure. – Julian Newman May 24 '20 at 2:15

Having read Mateusz Kwaśnicki's answer, I will now write it in my own way:

Lemma. Let $$S_\infty$$ and $$T$$ be separable metric spaces, and let $$(S_j)_{j \in \mathbb{N}}$$ be a sequence of Borel subsets of $$S_\infty$$. Let $$\{F_j\}_{j \in \mathbb{N} \cup \{\infty\}}$$ be a family of Borel-measurable functions $$F_j \colon S_\infty \to T$$, with $$F_\infty$$ being continuous. Suppose that for every $$(x_j)_{j \in \mathbb{N} \cup \{\infty\}} \in \prod_{j \in \mathbb{N} \cup \{\infty\}} S_j$$, if $$x_j \to x_\infty$$ as $$j \to \infty$$ then $$F_j(x_j) \to F_\infty(x_\infty)$$ as $$j \to \infty$$. Then for any family $$(\Xi_j)_{j \in \mathbb{N} \cup \{\infty\}}$$ of $$S_\infty$$-valued random variables $$\Xi_j$$ with $$\Xi_j \in S_j$$ almost surely, if $$\Xi_j$$ converges in law to $$\Xi_\infty$$ then $$F_j(\Xi_j)$$ converges in law to $$F_\infty(\Xi_\infty)$$.

Proof of the result given the Lemma.

Let $$M=\mathbb{E}[\Delta_i]=\mathbb{E}[X_i^2]$$. Let $$S_\infty=C([0,\infty),\mathbb{R}^2)$$, and for each $$\lambda \in (0,\infty)$$ let $$S_\lambda \ = \ \left\{ t \mapsto \begin{pmatrix} \sqrt{\lambda}(w(t)-Mt) \\ v(t) \end{pmatrix} \, : \, w \in \mathrm{Homeo}([0,\infty)), v \in C([0,\infty),\mathbb{R}) \right\}.$$ For each $$\lambda \in (0,\infty)$$ and $$n \in \mathbb{N}$$, let $$\Xi_\lambda(\tfrac{n}{\lambda}) \ = \ \begin{pmatrix} \frac{1}{\sqrt{\lambda}} \sum_{i=1}^n (\Delta_i - M) \\ \frac{1}{\sqrt{M\lambda}} \sum_{i=1}^n X_i \end{pmatrix}$$ and extend by linear interpolation: for $$r \in (0,1)$$, writing $$t=\frac{n+r}{\lambda}$$, we define \begin{align*} \Xi_\lambda(t) \ &= \ r\Xi_\lambda(\tfrac{n+1}{\lambda})+(1-r)\Xi_\lambda(\tfrac{n}{\lambda}) \\ &= \begin{pmatrix} \left( \frac{1}{\sqrt{\lambda}} \left( r\Delta_{n+1} + \sum_{i=1}^n \Delta_i \right) \right) - \sqrt{\lambda}Mt \\ \frac{1}{\sqrt{M\lambda}} \left( rX_{n+1} + \sum_{i=1}^n X_i \right). \end{pmatrix} \end{align*} Hence, for each $$\lambda \in (0,\infty)$$, we have that $$\Xi_\lambda\overset{\mathrm{def}}{=}(\Xi_\lambda(t))_{t \geq 0}$$ belongs almost surely to $$S_\lambda$$, with the corresponding $$w \in \mathrm{Homeo}([0,\infty))$$ given by $$w(\tfrac{n}{\lambda}) \ = \ \frac{1}{\lambda} \sum_{i=1}^n \Delta_i .$$ The Donsker invariance principle gives that as an $$S_\infty$$-valued random variable, $$\Xi_\lambda$$ is convergent in distribution as $$\lambda \to \infty$$, to a two-dimensional Brownian motion $$\Xi_\infty\!=\!(\Xi_\infty(t))_{t \geq 0}$$ whose second-coordinate projection is a one-dimensional Wiener process (i.e. standard Brownian motion).

Now for each $$\lambda \in (0,\infty)$$, define $$F_\lambda \colon S_\lambda \to C([0,\infty),\mathbb{R})$$ by $$F_\lambda\!\begin{pmatrix} u \\ v \end{pmatrix} \ = \ \sqrt{M}v \circ \left( M.\mathrm{id}_{[0,\infty)} + \tfrac{1}{\sqrt{\lambda}} u \right)^{\!-1},$$ and define $$F_\infty \colon S_\infty \to C([0,\infty),\mathbb{R})$$ by $$F_\infty\!\begin{pmatrix} u \\ v \end{pmatrix}(t) \ = \ \sqrt{M}v\!\left( \tfrac{1}{M} t \right).$$ So $$F_\lambda(\Xi_\lambda) = (W_t^{(\lambda)})_{t \geq 0}$$ for each $$\lambda \in (0,\infty)$$, and $$F_\infty(\Xi_\infty)$$ is a one-dimensional Wiener process.

Now for any $$\lambda_n \nearrow \infty$$, any $$(x_n)_{n \in \mathbb{N}}=\!\left( \begin{pmatrix} u_n \\ v_n \end{pmatrix} \right)_{\!\!n \in \mathbb{N}} \in \prod_{n \in \mathbb{N}} S_{\lambda_n}$$ and any $$x_\infty=\!\begin{pmatrix} u_\infty \\ v_\infty \end{pmatrix} \in S_\infty$$, if $$x_n$$ converges uniformly on bounded sets to $$x_\infty$$, then $$M.\mathrm{id}_{[0,\infty)} + \frac{1}{\sqrt{\lambda_n}} u_n$$ converges uniformly on bounded sets to $$M.\mathrm{id}_{[0,\infty)}$$, so $$\left( M.\mathrm{id}_{[0,\infty)} + \frac{1}{\sqrt{\lambda_n}} u_n \right)^{\!-1}$$ converges uniformly on bounded sets to $$\frac{1}{M}\mathrm{id}_{[0,\infty)}$$; and also $$v_n$$ converges uniformly on bounded sets to $$v_\infty$$; and therefore $$F_{\lambda_n}(x_n)$$ converges uniformly on bounded sets to $$F_\infty(x_\infty)$$.

Hence the Lemma gives the desired result.

Proof of the Lemma.

For convenience of notation, assume that all the random variables are over a probability space $$(\Omega,\mathcal{F},\mathbb{P})$$.

Let $$d$$ be the metric on $$T$$. For each $$\varepsilon>0$$, define the decreasing sequence $$(G_j(\varepsilon))_{j \in \mathbb{N}}$$ of subsets of $$S_\infty$$ by $$G_j(\varepsilon) \ = \ \overline{\bigcup_{i=j}^\infty \{x \in S_i : d(F_i(x),F_\infty(x)) \geq \varepsilon \}}.$$ We first show that for all $$\varepsilon>0$$, $$\bigcap_{j \in \mathbb{N}} G_j(\varepsilon)=\emptyset$$. If we have $$x_\infty \in \bigcap_{j \in \mathbb{N}} G_j(\varepsilon)$$, we can construct a sequence $$n_j \nearrow \infty$$ and a sequence $$x_{n_j} \in S_{n_j}$$ converging to $$x_\infty$$ such that $$d(F_{n_j}(x_{n_j}),F_\infty(x_{n_j})) \geq \varepsilon$$ for all $$j \in \mathbb{N}$$; and since $$F_\infty(x_{n_j}) \to F_\infty(x_\infty)$$ (by continuity of $$F_\infty$$), it follows that $$F_{n_j}(x_{n_j})$$ does not converge to $$F_\infty(x_\infty)$$, contradicting our assumption.

Now fix any family $$(\Xi_j)_{j \in \mathbb{N} \cup \{\infty\}}$$ of $$S_\infty$$-valued random variables $$\Xi_j$$ with $$\Xi_j \in S_j$$ almost surely, such that $$\Xi_j$$ converges in law to $$\Xi_\infty$$. For each $$\varepsilon>0$$ we have that $$\mathbb{P}(\Xi_j \in G_j(\varepsilon)) \to 0$$, since \begin{align*} \limsup_{j \to \infty} \mathbb{P}(\Xi_j \in G_j) \ &\leq \ \lim_{m \to \infty} \limsup_{j \to \infty} \mathbb{P}(\Xi_j \in G_m) \\ &\leq \ \lim_{m \to \infty} \mathbb{P}(\Xi_\infty \in G_m) \quad \text{since \Xi_j converges in law to \Xi_\infty} \\ &= \ 0 \quad \text{since } \bigcap_{m \in \mathbb{N}} G_m=\emptyset. \end{align*} Now to show the desired convergence, fix a bounded Lipschitz function $$g$$ on $$T$$ which, without loss of generality, we assume to map into $$[0,1]$$ and to have Lipschitz constant $$1$$. Fix $$\varepsilon>0$$. Let $$N$$ be sufficiently large that for all integers $$j \geq N$$, $$\mathbb{P}(\Xi_j \in G_j(\tfrac{\varepsilon}{3})) \ < \ \tfrac{\varepsilon}{3}$$ and $$\big| \mathbb{E}[g(F_\infty(X_j))] - \mathbb{E}[g(F_\infty(X_\infty))] \big| < \tfrac{\varepsilon}{3},$$ where the latter is possible by the convergence in law of $$X_j$$ to $$X_\infty$$, since $$g \circ F_\infty$$ is a bounded continuous function on $$S_\infty$$. Using the former of these two statements, an easy calculation yields $$\big| \mathbb{E}[g(F_j(X_j)) - g(F_\infty(X_j))] \big| < \tfrac{2\varepsilon}{3},$$ and combining this with the latter gives $$\big| \mathbb{E}[g(F_j(X_j))] - \mathbb{E}[g(F_\infty(X_\infty))] \big| < \varepsilon$$ as required.