6
$\begingroup$

Let $U_1,U_2,\ldots$ be iid random variables distributed uniformly on $[0,1]$. I am interested in the random walk $X_i = \sum_{j \leq i} U_j$. In particular,

What is the expected number of points appearing in an interval $[x,x+1]$?

Experimentally, this seems to converge to $2$.

Here is an intuitive explanation. Suppose that $x+1-\delta$ is the first point within the interval $[x,x+1]$ which the random walk hits. One can calculate that the expected number of points within the interval is $e^\delta$. To estimate the distribution of $\delta$, consider the point $x-\epsilon$ just preceding $x+1-\delta$. Assuming that $\epsilon$ is uniformly distributed (which is close to the truth when $x$ is large), the density of $\delta$ at a point $\delta'$ is proportional to $\Pr[\epsilon \leq \delta'] = \delta'$, and so it is $2\delta'$. Therefore the expected number of points in $[x,x+1]$ is $$ \int_0^1 2\delta e^\delta \, \mathrm{d}\delta = 2. $$

$\endgroup$
  • $\begingroup$ If you call the number of arrivals/points up to $t$, $X_t$, then $\{X_t\}$ is a renewal process. Let $m(t) = E[X(t)]$. Then renewal theorem says that $m(t+h) - m(t) \to h/\mu$, as $t \to \infty$, where $\mu$ is the mean of the increments (here $E[U_1]=1/2]$). Hence with $h =1$, for large $t$ you get your answer. $\endgroup$ – passerby51 Aug 31 '13 at 21:19
  • $\begingroup$ Many thanks! What I was missing was the term "renewal theory". If you convert your comment to an answer I will be happy to accept it. $\endgroup$ – Yuval Filmus Aug 31 '13 at 21:24
9
$\begingroup$

Let $X_t$ be the number of points in $[0,t]$. Then, $X_t$ is a renewal process. Let $m(t) = E[X_t]$. Then renewal theorem says $$ m(t+h) -m(t) \stackrel{t \to \infty}{\longrightarrow} \frac{h}{\mu} $$ where $\mu = E[U_1]$ is the expected increment.

With $\mu = 1/2$ and $h = 1$ in this case, one gets $2$ for the limit.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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