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



A simple stopping time problem.
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.


