MathOverflow is a question and answer site for professional mathematicians. 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

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

share|cite|improve this question
up vote 7 down vote accepted

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.

share|cite|improve this answer
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}]$.

share|cite|improve this answer

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

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.