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$
2
  • $\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
    Commented Aug 31, 2013 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$ Commented Aug 31, 2013 at 21:24

1 Answer 1

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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .