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,

  • 0
    Can you please indicate where this problem comes from?2010-11-30
  • 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
    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!2010-11-30
  • 0
    Yes, your differential equation is correct. I'll think about the "related problem" soon.2010-11-30
  • 0
    And yes, we would get exactly the same differential equation for the "related problem" 1).2010-11-30
  • 0
    Thanks. The second related problem doesn't seem to be that directly related. I will keep thinking about how to solve it.2010-11-30
  • 0
    +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.2010-11-30
  • 0
    @Mike: Thanks. Indeed, this approach is very useful.2010-11-30
  • 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).$$