What is the expected number of rounds at the first net win?

Question

When i'm playing a game with a certain chance of winning, say $50\%$. What is the expected number of rounds at the first net win? The first net win is the first time that (win - lose) $\geq 1$.

---

Here are the steps of my thought:

1. We can only get the first net win at odd-numbered rounds.
2. If the final winning round is not round $1$, I must win at the last two rounds.
3. In the other rounds of step $2$, i have （win - lose）= $-1$.
4. In the other rounds of step $2$, i have never had a time when (win - lose) $\ge 1$.

In my original solution steps $3$ and $4$ were considered as "the first time when i have the a net lose", which forms a recursion. Then i found i was wrong. Now i'm at a total mess.

---

So here i can only find one of its lower bound and one of its upper bound $(2, O(n^2))$. But i don't know how to solve the problems indeed. Any idea that would narrow the range is appreciated!

Answer 1

The answer is $\infty$.

Let $X_n$ be the number of wins subtracted by number of loses in $n$ rounds.

We let $1$ be the absorbing state.

$$Pr(X_n=1|X_{n-1}=1)=1$$

and for $i \leq 0$,

$$Pr(X_n=i+1|X_{n-1}=i)=Pr(X_n=i-1|X_{n-1}=i)=\frac12$$

Let $t_i$ denote the time until absorption if we start from state $i$.

$$t_1=0$$

$$t_i=\frac12 t_{i-1} +\frac12t_{i+1}+ 1$$

which is a linear recurrence problem. At this point of time, I have converted the problem to the well known random walk problem.

To solve this linear recurrence, let's modify the question our introduce another absorbing state. $$t_{-w}=0$$

where $w > 1$.

That is we want to solve for $t_1, t_0 , \ldots, t_{-w}$ where they satisfy

$$t_1=0$$

$$t_i=\frac12 t_{i-1} +\frac12t_{i+1}+ 1\tag{1}$$

$$t_{-w}=0$$

The charactheristic equation is $x^2-2x+1=0$, hence $(x-1)^2=0$

Hence the homogeneous solution is of the form of $a+bi$.

There is also a non-homogeneous part to equation $(1)$.

check that $$-i^2=\frac12(-(i-1)^2) + \frac12 (-(i+1)^2)+1$$

Hence $t_i = -i^2$ is a particular solution to $(1)$.

Now, let us solve for $t_i=a+bi-i^2$ along with the boundary condition to determine $a$ and $b$.

$$t_1 = 0= a+b(1)-1$$

$$t_{-w}=a+b(-w)-(-w)^2$$

That is we want to solve $$a+b=1$$ $$a-bw=w^2$$

Solving them, we found $$t_i = w+(1-w)i-i^2$$

and

$$t_0=w$$

By letting $w \to \infty$, $t_0$ in our initial problem goes to $\infty$.

That is expected number of rounds at first net win is $\infty$.

Trivia: Even though the expected number of rounds at first net win is $\infty$, the probability of attaining first net win is $1$.