0
$\begingroup$

If I have a stream of integers from 0 to 9(each with equal probability and repetition is allowed) that are spewed out until I get the first instance of 4-5 next to each other in this order, how do I find the expected value of the number of integers that will be printed?

I set up a random variable, $X$, that is the number of integers printed, and an indicator random variable, $X_i$, that is 1 if the $I^{th}$ number does not complete the first instance of 4-5, and 0 otherwise. I think that the probability that $X_i$ = 1 is calculated as $1 - (1/10)^2$, so would the expected value of $X$ just be $1/p$?

$\endgroup$
0
$\begingroup$

I don't understand your computation. It would appear that the expected value of the $i^{th}$ term would be a function of $i$, since you would need to ensure that the game wasn't over before the $i^{th}$ move. Anyway, here is another approach:

There are three states here...$\emptyset,4,\{4,5\}$ according to how much of the $4,5$ block occurs at the end of the running string. Letting $E_S$ deonte the expected number it will take to finish assuming you are starting in state $S$, we note that the answer we want is $E=E_{\emptyset}$. Of course $E_{\{4,5\}}=0$.

Noting that $\emptyset$ can only transition to $\emptyset$ (probability .9) or $4$ (probability .1) we compute $$E_{\emptyset}=\frac 9{10}\times (E_{\emptyset}+1)+\frac 1{10}\times (E_4+1)\implies E_{\emptyset}=E_4+10$$

Similarly $$E_4=\frac 1{10}\times 1+\frac 1{10}(E_4+1)+\frac 8{10}\times (E_{\emptyset}+1)\implies 9E_4=8E_{\emptyset}+10$$

This system is easy to solve and we get $$\boxed {E_{\emptyset}=100}\quad \&\quad \boxed {E_4=90}$$

$\endgroup$

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.