5
$\begingroup$

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.

Thanks,

  • 1
    I'm sorry I should have mentioned the source, especially since it is sort of plagiarized without consent. http://www.wilmott.com/messageview.cfm?catid=26&threadid=80877 http://www.wilmott.com/messageview.cfm?catid=26&threadid=808082010-11-30

2 Answers 2

3

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$.

  • 0
    @Mike: Can you tell me what your drawn-out calculation was?2010-11-30
3

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}.$

Therefore,

$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).$