A simple stopping time problem.

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

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

-

3 Answers

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 2011 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 2011 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 2011 at 1:31

1
Fedja: I got the same answer using a purely probabilistic arguments. I'll try to write it up later... – Ori Gurel-Gurevich Nov 16 2011 at 5:21

2
please do, Ori ! – Nick B. Nov 16 2011 at 5:52
show 3 more comments

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.

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

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 49, "mathjax_display_tex": 1, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": false, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9355209469795227, "perplexity_flag": "head"}