Expected number of coin tosses to get a skewed score EDITED. You toss a fair coin $n$ times. After each toss $i$ you record the score so far: $s_i = (1000+totalHeadsRecorded)/(2000+i)$. 
What is the expected number for $n$ in order to get a score greater than some value $s$ ?
For $s<0.5$, $n$ should be $0$.
For $s>0.5$, $n$ appears to grow very quickly. I wonder when does it "jump" to either infinity or to "impossible", and what happens just before the jump? How big are those numbers?  For me, this problem seems somewhat similar to the Halting Problem.
 A: Here's a partial answer:
Let $X_i$ be the number of heads after $i$ tosses and $s$ your target ratio.
We can define a stochastic process $s_i:=\frac{1000+X_i}{2000+i}$
Define a stopping time, $\tau_s:=\{\inf i: s_i>s\}$
Note that $E[s_i|s_{i-1}]=0.5\left(s_{i-1}\frac{2000+i-1}{2000+i}\right)+0.5\left(s_{i-1}\frac{2000+i-1}{2000+i}+\frac{1}{2000+i}\right)=s_{i-1}\frac{2000+i-1}{2000+i}+\frac{1}{4000+2i}=s_{i-1}+\frac{1-2s_{i-1}}{4000+2i}$ 
As you've pointed out, $s<=0.5 \implies \tau_s=0$, so we can focus on the case $s>0.5$. Note that this process is not any type of martingale, as its conditional expectation can be above, at, or below the current value, depending on whether its current value is below, at, or above $0.5$ (i.e., we see regression towards the mean). However, it is both approximately and asymptotically a martingale.
Thus, you need to find $E[\tau_s]$ for $s>0.5$. 
Let's define a new stopping time: $\tau'_s:=\{\inf i: s_i>s>0.5\text{ or } s_i<t<0.5\}$. Since $s_i$ is approximately a martingale, lets try using the Optional Stopping Theorem, to conclude
$E[s_{\tau'_s}]\approx E[s_0]=0.5=sP(s_{\tau'_s}=s)+t[1-P(s_{\tau'_s}=s)]=(s-t)P(s_{\tau'_s}=s)-t$
Thus:
$P(s_{\tau'_s}=s) = \frac{0.5+t}{s-t}$ Since we only care about $s$, lets set $t=0$:
$P(s_{\tau'_s}=s) = \frac{1}{2s}$. Unfortunately, $t=0,s>0.5 \implies P(s_{\tau'_s}=0)>0 \implies E[\tau'_s]=\infty$
The assumption of approximate martingale was actually conservative, since the regression-to-mean behavior will simply slow the processes approach to the cutoff. It looks like you can expect to stop immediately, or never (although there is a positive probability of stopping sometime before forever).
