Estimated no. trials to reach $n$ where Heads = +1 and Tails = -1

Question

I am unsure if this has been asked before, I have looked at some other questions which are close but not exactly this.

This was a problem I thought of a while ago and I am now attempting to solve:

"Let $x$ be the position on the number line where $x$ is initially set to 0. Each round, a standard coin is flipped. On heads, $x$ increases by 1. On tails, $x$ decreases by 1. When we reach $n$ we immediately stop. What is the estimated number of flips to reach $n$, where $n$ is an integer"

I have done some work into this but I am stuck on a portion of it (I have little to no formal Math training in this area). I have considered the answer to be the sum of an infinite series (which I assume, but not sure if, converges. However this isn't the question at hand):

$$ f(x) = \sum_{t=1}^{\infty} (\frac{1}{2})^{n+2t}.(\frac{(n+2t)!}{(n+t)!t!}-M)\ $$

Just to explain my logic. I have considered that the "simplest" way to get to $n$ is with $n$ consecutive flips, hence $ (\frac{1}{2})^{n} $, then from there you have an infinite number of additional combinations to get there, so I considered that the combinations can be expressed by adding a pair of heads and tails (because the final sequence must end up on n). This pair is defined by t where each t is an "extra" pair.

($M$ is a value I have yet to work out which corresponds to the invalid sequences, which are explained further below)

e.g where $n$ = 3, the simplest sequence is:

$$HHH$$

then as we increment $t$ we get:

$$T+HHH+H$$ $$TT+HHH+HH$$

Therefore I defined the number of combinations with respect to t as $(n+2t) C (t)$ or $\frac{(n+2t)!}{(n+t)!t!} $ and the probability for any one of these combinations to be $(\frac{1}{2})^{n+2t}$ (as you are adding 2 flips each time).

Here arrives my issue. While $\frac{(n+2t)!}{(n+t)!t!} $ correctly (I believe) defines the number of combinations with respect to $n$ and $t$, not all sequences are valid.

e.g:

(n=3 t=1)

$$HHHHT$$

Is invalid as you would have stopped after the first 3 ($n$) flips.

Likewise in this example:

($n$ = 3, $t$ = 3)

$$HHTHTHHTH$$

Is invalid as you would have stopped on the third to last flip (if the last T was moved further up in the sequence it would become valid sequence).

I understand why these sequences are invalid, and in the procedural sense, how to work them out. However, I have having issues expressing it Mathematically with respect to t and n.

So my question is simply:

What is $M$ with respect to $t$ and $n$? (and how did you work it out?)

alternatively:

Why I'm completely wrong about everything I've written so far

Either will help me immensely.

Thanks in advance for any help.

Answer 1

What you are describing is a random walk on the integers. This is a well studied topic and knowing the key word, the answer to your question can be found on the wikipedia article on random walks.

The expected number of steps to reach either $b$ or $-a$ (where $a,b>0$) is $a\cdot b$ and the probability that it hits $b$ first is $\frac{a}{a+b}$.

In your question you put only one bound, one can see from the above that then the expected number of steps to hit that bound is infinite as the walk could 'run off to far in the negative direction'. So keep $b$ fixed and consider what happens as $a$ goes to infinity. The number of steps to hit either bound increases to infinity and the proportion of the cases where you hit $b$ first goes to $1$.

Answer 2

I believe this can be considered the problem of computing the expected value of walks in a random walk with equal probability for each step to reach a point ,check this post: Expected number of steps for reaching $K$ in a random walk