# Walk with randomised boosts

The classical random walk can be described as the evolution of the position $X_t$ of a walker for integers $t \geqslant 0$, where $X_0 = 0$ and $X_t = X_{t-1} + V_t$ for $t \geqslant 1$, where the "speed" $V_t$ at each time step is uniformly random $V_t \in_{\mathrm R} \{-1,+1\}$ and independent at each time step. It is well-known that this process yields a position which obeys a symmetric binomial distribution with mean $0$ and variance $t$, and that $t^{-1/2} X_t$ tends to a Gaussian distribution with variance $1$.

I am interested in a variant in which the speed itself increases or decreases by random "boosts", behaving like a classical random walk, and where the position is governed by the speed as it evolves over time. That is, we have \begin{aligned} X_0 &= 0 & V_0 &= 0 \\ X_t &= X_{t-1} + V_t & V_t &= V_{t-1} + A_t & A_t \in_{\mathrm R} \{-1,+1\}. \end{aligned} Question. What is the probability distribution of $X_t$ as a function of $t$?

Remark #1. This process is in effect a discrete-time variant of a second-order stochastic differential equation of a form \begin{aligned} \frac{\mathrm dx}{\mathrm dt} &= v, & \frac{\mathrm dv}{\mathrm dt} = \xi_t \end{aligned} where $W_t = \int_{0}^t \mathrm d\tau \, \xi_\tau\,$; though I do not know enough to be able to distil what probability density function one would expect for $x(T)$ from the references I found.

Remark #2. I originally requested an answer regarding the density function of the continuous version $x(t)$ as a fall-back. I have accepted an answer on that question for now; and that answer implicitly provides an answer for the discrete-time version in which the steps are normally distributed instead of being of fixed size. However, I will preferentially accept and reward any answer on the discrete-time version of the problem.

The position process $x_t$ satisfies $$x_t = x_0 + t v_0 + \int_0^t W_s ds \;.$$ Because $\int_0^t W_s ds \sim \mathcal{N}(0,\frac{1}{3} t^3)$, a simple change of variables shows that $$x_t \sim \mathcal{N}( x_0 + t v_0, \frac{t^3}{3}) \;.$$

The following relates $x_t$ to a discrete-time weak approximation $X_N$, which is obtained by weakly approximating the Brownian increments in the velocity process $v_t$ by Rademacher random variables.

Claim. Given $t>0$ and $N \in \mathbb{N}$, set $$\tag{\star} X_n = X_{n-1} + h V_n \;, \quad V_n = V_{n-1} + \sqrt{h} A_n \;, \quad 1 \le n \le N$$ with initial conditions $X_0 = x_0$, $V_0 = v_0$, and where $\{ A_i \}_{i=1}^N$ are independent Rademacher random variables and $h=\frac{t}{N}$. For any $t>0$, $$X_{N} \overset{d}{\to} x_t \quad \text{as N \to \infty} \;.$$

Proof. Unraveling the recurrence relation ($\star$) yields, $$X_N = x_0 + t v_0 + \frac{t^{3/2}}{N^{1/2}} S_N$$ where $S_N = \sum_{i=1}^N A_i \frac{(N-i+1)}{N}$. Note that $S_N$ is a sum of independent and uniformly bounded random variables each with mean zero. Moreover, the variance $s_N^2$ of $S_N$ goes to $\infty$ as $N \to \infty$ since $$s_N^2 = \operatorname{Var}(S_N) = \frac{1+3 N + 2 N^2}{6 N} \;.$$ By the Lyapunov Central Limit Theorem, $$\frac{S_N}{s_n} \overset{d}{\to} \mathcal{N}(0,1) \;,$$ from which it follows that, $$X_N \overset{d}{\to} \mathcal{N}(x_0 + t v_0, \frac{t^3}{3} ) \;.$$

• To make sure I've correctly understood what the continuous analogon is, and can understand the result in your answer, would you happen to have an introductory reference which also shows this result? It would be very good news indeed if the pdf were simply a Gaussian. – Niel de Beaudrap Jan 9 '18 at 18:08
• The fact that the time integral of Brownian motion is Gaussian is nicely explained in wiley.com/legacy/wileychi/brownianmotioncalculus/supp/… (online supplementary material to the book wiley.com//legacy/wileychi/brownianmotioncalculus). For change of variables, see en.wikipedia.org/wiki/… – Nawaf Bou-Rabee Jan 9 '18 at 18:18
• Thanks! That supplementary material answers a variation on the discrete-time version of the problem as well (with normally-distributed steps rather than steps of fixed size); that's a bonus. – Niel de Beaudrap Jan 10 '18 at 13:50
• I related a bit more the discrete and continuous time versions. – Nawaf Bou-Rabee Jan 10 '18 at 13:52