Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Consider a particle starting at the the origin and moving along the positive real line at a constant speed of 1. Suppose there is a counter which clicks at random time intervals following the exponential distribution with parameter $\lambda$ and whenever the counter clicks, the position $x > 0$ of the particle at that time instantaneously changes to the position $x/2$. We wish to calculate the expected average speed of the particle.

I don't really have any idea of how to go about solving this. Here are a couple of related problems which seem even more difficult to me:

  1. Modify the puzzle so that when the counter clicks, the particle moves from $x$ to a point chosen uniformly at random from $[0,x]$.
  2. The particle starts moving as above but whenever the counter clicks, its speed increases by 1 (the initial speed was 1). What is the expected time when the particle hits the position 1? What is the expected speed when the particle hits the position 1?

This is not a homework problem. Any solutions, hints, thoughts will be appreciated.


share|cite|improve this question
Can you please indicate where this problem comes from? – Shai Covo Nov 30 '10 at 0:20
I'm sorry I should have mentioned the source, especially since it is sort of plagiarized without consent. – Preyas Popat Nov 30 '10 at 1:16
up vote 3 down vote accepted

Sketch of solution: Let $X_t$ denote the location of the particle at time $t$, and set $f(t) = {\rm E}(X_t)$. Consider the time $t + \Delta t$, $\Delta t \approx 0+$. With probability of about $1 - \lambda \Delta t$ the particle continues to position $X_t + \Delta t$, whereas with probability of about $\lambda \Delta t$ it moves to position of about $X_t/2$. This leads straightforwardly to an elementary differential equation in terms of $f(t)$, from which you obtain $f(t)$. The expected average speed is then $f(t)/t$.

share|cite|improve this answer
I will write down my calculations since I am not completely sure of them. $$f(t + dt) - f(t) \sim (1 - \lambda dt) dt - \lambda dt f(t)/2 $$ This gives rise to the equation $$ f' + \lambda f /2 =1 $$ and solving this gives that the expected average speed $f(t)/t$ varies with time. Does that look correct? If yes, wouldn't we also get exactly the same differential equation for the "related problem" 1) mentioned in the question? Thanks! – Preyas Popat Nov 30 '10 at 1:22
Yes, your differential equation is correct. I'll think about the "related problem" soon. – Shai Covo Nov 30 '10 at 1:40
And yes, we would get exactly the same differential equation for the "related problem" 1). – Shai Covo Nov 30 '10 at 1:56
Thanks. The second related problem doesn't seem to be that directly related. I will keep thinking about how to solve it. – Preyas Popat Nov 30 '10 at 3:53
+1: I really like this answer. I did a long, drawn-out probability calculation and ended up with the same solution as that given here. It would never have occurred to me to solve this problem with a differential equation. – Mike Spivey Nov 30 '10 at 4:34

Just for the record, I like Shai Covo's answer better. But the OP asked me to post my solution as well, so here it is.

Let $X_t$ be the position of the object at time $t$. Given $N$ clicks in $[0,t]$, let $\tau_1, \tau_2, \ldots \tau_N$ be the times of those clicks. Let $T_i$ be the $i$th interarrival time, so that $T_1 = \tau_1$, $T_{N+1} = t - \tau_N$, and $T_i = \tau_i - \tau_{i-1}$ otherwise. Thus $t = \sum_{i=1}^{N+1} T_i$.

By properties of the exponential distribution, $E[T_i|N] = E[T_j|N]$ for all $i, j$. Thus $$t = \sum_{i=1}^{N+1} E[T_i|N] = E[T_i|N] (N+1) \Rightarrow E[T_i|N] = \frac{t}{N+1}.$$

If $N=0$, then $X_t = T_1$. If $N = 1$, $X_t = \frac{1}{2}T_1 + T_2$. If $N = 2$, $X_t = \frac{1}{4}T_1 + \frac{1}{2}T_2 + T_3$, and, in general, $X_t = \sum_{i=0}^N \frac{T_{N+1-i}}{2^i} $. Thus $$E[X_t|N] = \sum_{i=0}^N \frac{E[T_{N+1-i}|N]}{2^i} = \frac{t}{N+1}\left(2 - \frac{1}{2^N}\right).$$

Since $E[X_t] = E[E[X_t|N]]$, we just have to calculate $E\left[\frac{1}{N+1}\right]$ and $E\left[\frac{1}{(N+1)2^N}\right]$. Since $N$ is Poisson$(\lambda t)$, we have $$E\left[\frac{1}{N+1}\right] = \sum_{n=0}^{\infty} \frac{(\lambda t)^{n} e^{-\lambda t}}{(n+1) n!} = e^{-\lambda t} \sum_{n=0}^{\infty} \frac{(\lambda t)^{n} }{(n+1)!} = \frac{e^{-\lambda t}}{\lambda t} \sum_{n=0}^{\infty} \frac{(\lambda t)^{n+1} }{(n+1)!} $$ $$= \frac{e^{-\lambda t}}{\lambda t} \left(\sum_{n=0}^{\infty} \frac{(\lambda t)^n }{n!} - 1 \right) = \frac{e^{-\lambda t}}{\lambda t} \left(e^{\lambda t} - 1 \right) = \frac{1}{\lambda t} - \frac{e^{-\lambda t}}{\lambda t}.$$

Similarly, $$E\left[\frac{1}{(N+1)2^N}\right] = \frac{2e^{-\lambda t}}{\lambda t} \sum_{n=0}^{\infty} \frac{(\frac{\lambda t}{2})^{n+1} }{(n+1)!} = \frac{2e^{-\lambda t}}{\lambda t} \left(e^{\lambda t/2} - 1 \right) = \frac{2e^{-\lambda t/2}}{\lambda t} - \frac{2e^{-\lambda t}}{\lambda t}.$$


$$E[X_t] = E\left[\frac{2t}{N+1}\right] - E\left[\frac{t}{(N+1)2^N}\right] = \frac{2}{\lambda}\left(1 - e^{-\lambda t/2}\right),$$ which is exactly what you get if you solve the differential equation in Shai Covo's answer.

So the expected average speed (velocity, actually, since the average speed is technically 1) is $$\frac{2}{\lambda t}\left(1 - e^{-\lambda t/2}\right).$$

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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