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:
- We can only get the first net win at odd-numbered rounds.
- If the final winning round is not round $1$, I must win at the last two rounds.
- In the other rounds of step $2$, i have （win - lose）= $-1$.
- 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!