# A simple stopping time problem.

This should be rather standard so I hope somebody with a good background in probability theory would give me a quick solution or a reference.

We are given a threshold positive integer $T>0$. Let $a_1=1$ and for all $k$ with probability one half set $a_k=3a_{k-1}$ or else $a_k=2a_{k-1}$. We will stop the process at smallest time $\tau$ when $a_{\tau} \geq T$. We would like to compute the constant $c$ defined to be,

$E[ \sum_{i=1}^{\tau} a_i ] = c T + o(T)$

Could you estimate $c$ ?

-

From the way you ask, I conclude that you can prove that the limit exists (which by itself is by no means trivial), so I'll just show how to compute it under this assumption.

Let $v(t)$ be $\frac 1t$ times the expectation in question if we stop after we exceed $t>0$ (not necessarily an integer). Then $v(t)=\frac 1t$ for $0<t<1$ and $v(t)=\frac 1t+\frac 12[v(t/2)+v(t/3)]$ for $t\ge 1$. Now let $F(s)=\int_1^\infty t^{-s}v(t)\frac{dt}{t}$. Using the recurrence, we get that for every $s>0$, $$F(s)=\frac 1{s+1}+\frac 12\left(\int_{1/2}^1 \frac 1t t^{-s}\frac{dt}t+\int_{1/3}^1 \frac 1t t^{-s}\frac{dt}t\right)+\frac 12(2^{-s}+3^{-s})F(s)$$ The limit we are interested in is the same as $\lim_{s\to 0+}sF(s)$. Putting all terms with $F(s)$ to one side, dividing, and passing to the limit, we get $\frac{5}{\log 6}$, which differs from Will's heuristic answer a bit. I cannot say that I really understood his post but it is quite fascinating that he was somehow right with $\log 6$ in the denominator :).

I apologize for computational mistakes in the original post.

-
Could you comment on how you would establish the existence of the limit ? – Nick B. Nov 16 '11 at 0:57
I think some factors of $t$, etc., may be missing from the working shown here. When I apply the method given above I find $c=5/\log 6=2.79055$, which is in good agreement with an experimental value of $2.79 \pm 0.01$. – David Moews Nov 16 '11 at 1:30
yes I think that is not a $1$ ; rather it is a $\frac{1}{s+1}$ but beside that I don't any possible trivial calculation problem. do you ? – Nick B. Nov 16 '11 at 1:31
Fedja: I got the same answer using a purely probabilistic arguments. I'll try to write it up later... – Ori Gurel-Gurevich Nov 16 '11 at 5:21
please do, Ori ! – Nick B. Nov 16 '11 at 5:52

I think it is possible to find the result using renewal theory. Indeed, the process $(\ln(a_i))$ is a random walk with i.i.d. increments ($\ln(2)$ or $\ln(3)$ with probability $1/2$). The renewal theorem will tell you the structure of the walk when it jumps over a large time (here $\ln(T)$). More precisely when $T \to \infty$ the jump that goes over $\ln(T)$ is a size biaised version of the orignal jump measure, i.e. $\ln(3)$ with probability $\ln(3)/\ln(6)$ and $\ln(2)$ with probability $\ln(2)/\ln(6)$. Furthermore, knowing this jump, the actual position of $\ln(T)$ is uniform in the jump. Easy calculations (if correct) then yield $E[a_\tau] = 3T/\ln(6)$ and $E[a_{\tau-1}]=7T/(6 \ln(6))$. But going down from $a_{\tau-1}$ is easy (the walk is asymptotically the reversed version) and we can compute $E[a_{\tau-1}+ a_{\tau-2}+...]= 12/7 E[a_{\tau-1}]$.

-

I don't believe it. You have $a_k = X_k a_{k-1}$, with$X = 3$or $2$ etc since $log(X)$ actually has positive expectation we'll have $a_k \approx e^{k\mu}$ and $\tau$ no worse than about log(T).

-