How long does it take a person with this "cheating" data-gathering strategy to achieve a desired result?

Solution 1:

Edited Note: From David Speyer's answer the below reaches the correct conclusion -- divergence in the expectation value -- though I haven't verified the intermediate observation about the actual asymptotics. (There was a bit of confusion at one point.)

I ran 10000000 simulations (up to 100000 max tosses each) while watching TV and collected a histogram of where I stopped. I got slightly different numbers to you, but sufficiently similar that I think this is a combination of statistical errors, rounding errors and coding errors! I suspect the basic behaviour is the same, but it's possible there is some extreme sensitivity in the tails. I haven't checked my code for bugs at all.

Haven't thought about why this behaviour arises, but it for $M$ the number of tosses required, the probability looks like it behaves as $$\mathbb{P}(M \ge m) \sim \frac C {m^k}\qquad C\approx 1.41,k\approx 0.13$$

Of course, this might just be a completely misleading line, it's very difficult to tell. This is definitely empirical.

If this holds up to further scrutiny, then we certainly have $$\mathbb{E}(M)=\sum_m^\infty \mathbb P(M\ge m) = \infty$$ If someone else fancies a bit of fun, I think seeing this is the correct behaviour and deriving an expression for $k$ might be a nice challenge!

Edit: Updated with slightly better data.

Also, as I said in the comment above,

This is the expected stopping time of a random walk Markov chain with moving barriers; since random walks move $\sim \sqrt N$ and your barriers are moving at (roughly the same) $\sim \sqrt N$ it's possible the expectation diverges.

You can probably come up with a decent argument as to why this sort of behaviour is to be expected, but I haven't taken taken the time to try it yet, so that might be overly optimistic. If I get round to thinking about this I'll post!

Solution 2:

According to Blackwell and Freedman, A Remark on the Coin Tossing Game, the expected time for the number of heads to get outside $n/2 \pm a \sqrt{n}$ is finite for $a<0.5$ and infinite for $a \geq 0.5$. (As Henry points out below, they use $\pm 1$ instead of $(0,1)$ counting, so their boundary is $0 \pm \sqrt{n}$.) I'm afraid I don't understand their proof, but this means that the expectation time should be infinite, as Sharkos finds.