Suppose that independent trials, each of which is equally likely to have any of $m$ possible outcome, are performed until the same outcome occurs $k$ consecutive times. If $N$ denotes the number of trials, show that $$E[N] = \frac{m^k-1}{m-1}$$
Hello, I'm having a lot of trouble with this question:
Attempt:
Let:
$N_k$ represent the time until the same outcome happens k consecutive times.
Clearly,the probability we get a single possible outcome on a turn is a $1/m$.
Say $N_k$ has already happened ("given: $N_k$"). The probability that the $k+1$ time is the same outcome is $1/m$--thus we only need one more time/turn to get $k$+$1$ outcomes to occur consecutively.
The probability that you don't get the same outcome on the $k+1$ time is $(m-1)/m$. If you don't get the same outcome then you have to start over. The mean number of extra trials you need is then: $E[N_{k+1}]$.
Thus: $E[N_{k+1}|N_k]$=$N_{k}$+$(\frac{1}{m})$+($\frac{(m-1)}{m}$)$E[N_{k+1}]$.
Taking the expectation of both sides yields: $E[N_{k+1}]$=$E[{N_k}]$+$(\frac{1}{m})$+($\frac{(m-1)}{m}$)$E[N_{k+1}]$. Solving for, we get: $E[N_{k+1}]$=$mE[N_k]+1$. Thus we have:
$E[N_{k+1}]$=$1+m(1+mE[N_{k-1}])$
=$1+m+m^2E[N_{k-1}])$
.. ..
$=1+m+.... m^{k}E[N_1]$ --(Not sure if this step) is right.
$=1+m+.... m^{k}$
But then I'm not sure how to get:$$E[N] = \frac{m^k-1}{m-1}$$. Does it have to do with geometric series?
You only want $k$ in a row, so you want $E(N_k),$ not $E(N_{k+1})$. That reduces the terms in your sum by $1$, giving $$E(N_k)=1+m+m^2+\ldots m^{k-1}$$ This is a finite geometric series with sum $$\frac {m^k-1}{m-1}$$ To prove that, multiply both sides by $m$ and subtract the old one from the new one.