0
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ I am not sure I understand the Question.// If you are tossing a fair coin and waiting for the first Head, the expected wait is 2 tosses. If you are rolling a fair die and waiting for the first 1, then the expected wait is 6 rolls. // Both of these are special cases of a geometric distribution, which you can read about in a probability text or google. // If 'trials' are independent and the probability of the desired event is $p$ on each trial, then the expected wait is $1/p$ trials. $\endgroup$ – BruceET Oct 27 '17 at 7:14
  • $\begingroup$ @BruceET I mean the first time when the number of wins minus the number of loses is one or positive. $\endgroup$ – Duli Oct 27 '17 at 12:25
0
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ I don’t quite get it. It seems like a method to consider only the number of wins. And it must be the first time tht (win - lose) = 1. A quick method to see a solution is wrong or not is to see whether the probability to get it at even rounds is zero (it should be since in this case (win - lose) can only be even numbers). $\endgroup$ – Duli Oct 27 '17 at 12:43
  • $\begingroup$ The approach doesn't just consider number of wins. When you win, difference between win minus loss increase by $1$. If you loses, the difference between win minus loss decrease by $1$. $\endgroup$ – Siong Thye Goh Oct 27 '17 at 17:17
  • $\begingroup$ My approach doesn't disclose the probability at even round, it just use total law of expectation, the model agrees that the probability to get it at even rounds is zero. You mean win minus lose can only be odd. $\endgroup$ – Siong Thye Goh Oct 27 '17 at 17:29
  • $\begingroup$ I understand it now. Thank you very much! ( came up with this question just because I want to see how much I will play to get my dota mmr rising every day ;D) $\endgroup$ – Duli Oct 28 '17 at 19:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.