A simple stopping time problem. - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-25T18:29:33Z http://mathoverflow.net/feeds/question/81012 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/81012/a-simple-stopping-time-problem A simple stopping time problem. Nick B. 2011-11-15T23:01:34Z 2012-04-12T08:48:27Z <p>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.</p> <p>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,</p> <p>$E[ \sum_{i=1}^{\tau} a_i ] = c T + o(T)$</p> <p>Could you estimate $c$ ?</p> http://mathoverflow.net/questions/81012/a-simple-stopping-time-problem/81019#81019 Answer by fedja for A simple stopping time problem. fedja 2011-11-15T23:56:23Z 2011-11-16T04:31:11Z <p>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.</p> <p>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 <code>$0&lt;t&lt;1$</code> 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 :). </p> <p>I apologize for computational mistakes in the original post.</p> http://mathoverflow.net/questions/81012/a-simple-stopping-time-problem/93809#93809 Answer by mike for A simple stopping time problem. mike 2012-04-11T23:42:42Z 2012-04-11T23:42:42Z <p>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).</p> http://mathoverflow.net/questions/81012/a-simple-stopping-time-problem/93841#93841 Answer by NC for A simple stopping time problem. NC 2012-04-12T08:48:27Z 2012-04-12T08:48:27Z <p>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}]$.</p>