4

In a test with a series of trials, you'd fail the test if you fail 2 out of the last 3 trials (i.e. window of 3).

For example, for a series of trials (starting from index 0, 1, ..., 7), we have results: 0, 1, 0, 0, 0, 1, 0, 1 (Fail is 1, Not failing is 0). Thus you fail the test at trial number 7.

Now assume the probability of failure in each trial is 1/3 (each trial is independent of each other), and call the trial where you fail the test Y (so in the example above Y = 7). Find P(Y = y) for y = 0, 1, 2, ..., 20. In other words, the probability you fail the test in each of those years.

By default then we know P(Y=0) = P(Y=1) = 0, and P(Y=2) = (1/3)^2. However, I have no idea how to proceed from here to higher values of Y. I've tried multiple values but they just don't work. I'm also given as a hint that E(Y) over that range is around 8.5. You can use this as a sanity check for your answer....

1 Answers1

1

The easiest way to tackle the problem is probably to treat the series of trials as a $4$-state Markov chain, in which the states are outcomes of the previous two tests if these have been $00$, $01$ or $10$, or the state $F$ of failure. Numbering these states $\ 1,2,3,4\ $, respectively, the chain starts in state $1$, and the transition matrix is $$ P=\begin{pmatrix} \frac{2}{3}&\frac{1}{3}&0&0\\ 0&0&\frac{2}{3}&\frac{1}{3}\\ \frac{2}{3}&0&0&\frac{1}{3}\\ 0&0&0&1 \end{pmatrix}\ . $$ The probability that the chain is in state $\ j\ $ after $\ y\ $ tests is $\ \delta_1^TP^y\delta_j\ $, where $\ \delta_j\ $ is the $\ j^\mathrm{\,th}\ $ column of the $\ 4\times 4\ $ identity matrix. The probability that $\ Y \le y\ $ is just the probability that the chain is in state $\ 4\ $ after $\ y\ $ tests—that is, $\ \delta_1^TP^y\delta_4\ $. Thus, the probability that $\ Y=y\ $ is $\ \delta_1^TP^y\delta_4-\delta_1^TP^{y-1}\delta_4=\delta_1^TP^{y-1}\left(P-I\right)\delta_4\ $. If $\ z_y=\delta_1^TP^{y-1}\left(P-I\right)\delta_4\ $, then, since $\ x^4-\frac{5}{3}x^3+ \frac{2}{3}x^2-\frac{4}{27}x+\frac{4}{27}\ $ is the characteristic polynomial of $\ P\ $ it follows that $\ z_y\ $ satisfies the recursion $\ z_{y+4}=\frac{5}{3}z_{y+3}+ \frac{2}{3}z_{y+2}-\frac{4}{27}z_{y+1}+\frac{4}{27}z_y\ $. Once the first four values of $\ z_y\ $ have been calculated, this recursion enables the subsequent values to be calculated without needing to do any further matrix multiplications.

Here's a table of the values of $\ \mathrm{Prob}\left(Y=y\right)\ $ for $\ y\ $ from $1$ to $20$: $$ \begin{matrix} y & \mathrm{Prob}\left(Y=y\right) \mbox{(exact)} &\mbox{(approx.)}\\ 1&0&0\\ 2&\frac{1}{9}& 0.11\\ 3&\frac{4}{27}& 0.15\\ 4&\frac{8}{81}& 0.099\\ 5&\frac{20}{243}&0.082\\ 6&\frac{56}{3^6}&0.077\\ 7&\frac{144}{3^7}&0.066\\ 8&\frac{368}{3^8}&0.056\\ 9&\frac{960}{3^9}&0.49\\ 10&\frac{2,946}{3^{10}}&0.042\\ 11&\frac{6,464}{3^{11}}&0.036\\ 12&\frac{16,768}{3^{12}}&0.032\\ 13&\frac{43,520}{3^{13}}&0.027\\ 14&\frac{112,896}{3^{14}}&0.023\\ 15&\frac{292,864}{3^{15}}&0.020\\ 16&\frac{759,808}{3^{16}}&0.018\\ 17&\frac{1,971,200}{3^{17}}&0.015\\ 18&\frac{5,113,856}{3^{18}}&0.013\\ 19&\frac{13,266,944}{3^{19}}&0.011\\ 20&\frac{34,418,688}{3^{20}}&0.0099\\ \end{matrix} $$

If $\ e_1, e_2, e_3\ $ are the expected number of tests from states $\ 1,2,3\ $, respectively, until ultimate failure, then these $\ e_i\ $ must satisfy the equations \begin{eqnarray} e_1&=&1 + \frac{2}{3}e_1 + \frac{1}{3}e_2\\ e_2&=&1 + \frac{2}{3}e_3 \\ e_3&=&1 + \frac{2}{3}e_1\ , \end{eqnarray} Which give $\ e_1 = 3 + e_2 = 4+ \frac{2}{3}e_3=\frac{14}{3}+\frac{4}{9}e_1\ $. Thus, $\ \frac{5}{9}e_1=\frac{14}{3}\ $, or $\ e_1=\frac{42}{5}=8.4\ $. This is probably where your hint comes from, but it's a little misleading, because the approximation $\ \sum_\limits{y=1}^{20} y\,\mathrm{Prob}\left(Y=y\right)\ $ is only about $\ 6.7\ $. You need to take $\ n=68\ $ for $\ \sum_\limits{y=1}^n y\,\mathrm{Prob}\left(Y=y\right)\ $ to approximate $8.4$ correctly to two decimal places.

lonza leggiera
  • 28,646
  • 2
  • 12
  • 33