1
$\begingroup$

Bernoulli trials are sequences of 0 and 1. What is the average length, the number of trials, that you need to perform until you reach n ones in sequence?


I tried to make it with a 2D recursion enter image description here

Here first index of $a$ is a counter of trials whereas second index is the level (the row). I have combined diagonals in groups to show that the whole group transits at level 0 at next column with whenever a failure occurs (with prob q).

The initial condition $$a_{00} = 1$$

The other values in the first row, which corresponds to after-failure condition for every number of trials performed so far,

$$a_{col+1,0} = a_{col,0}\cdot q + a_{col,1} \cdot q + \cdots + a_{col,col}\cdot q = q \cdot \sum_0^{col}{a_{col,i}}$$

For instance $a_{2,0}$ corresponds to paths 00 and 10, through $a_{11}$ and $a_{10}$ correspondingly.

The higher rank rows correspond to sequences of 1. If you get to the row n this means that you had n ones in sequence. Therefore, coefficients decay geometrically as we progress downwards along the column:

$$a_{trials,level} = p\cdot a_{trials+1,level+1}$$

We have got 3 equations for the induction:

$$ \begin{cases}\begin{array}{l} a_{0,0} &= 1 \\ a_{m+1,0} &= q \cdot \sum_0^{col}{a_{m,i}} \\ a_{m+1,n+1} &= p\cdot a_{m,n} \end{array}\end{cases}$$

I am familiar with generating functions and can define $X_m(x) = x_0 + x_1 \cdot x + x_2 \cdot x^2 + \cdots$ and transform last equation into

$$a_{m+1,0} + a_{m+1,0} \cdot x + a_{m+1,2} \cdot x^2 + \cdots - p\cdot x \cdot a_{m,0} - p\cdot x^2 \cdot a_{m, 1} - \cdots = a_{m+1,0} + x(a_{m+1,1} - p \cdot a_{m, 0}) + x^2(a_{m+1,2} - p \cdot a_{m, 1}) + \cdots = a_{m+1,0} = X_{m+1} - p\cdot x\cdot X_m$$

Resulting $$a_{m+1,0} = X_{m+1} - p\cdot x\cdot X_m$$ is also a recursion of the kind $X_{m+1} = a\cdot X_m + b$, where $b = a_{m+1,0}$ and $a = p\cdot x$ which has a solution

$$Y(y) = {x_0+y(x_0-b)\over (1-y)(1-ax)} = {X_0 + y(X_0-a_{m+1,0}) \over (1-y)(1-pxy)} = y_0 + y_1\cdot y + y_2 \cdot y^2\ldots.$$

You see, the things are becoming rather complex.

I also ignored the fact that the table must have a limited number of rows because we must stop at the row and compute its average, $E[level] = \sum_{col=0}^\infty{(level + col) \cdot a_{level, col}}$. That is our purpose. Currently, with infinite number of rows, we reset to the first row whenever 0 is Bernoulli despite desired level may be already achieved at the time. This distorts the true $a_{m,n}$ probabilities.

I expect that there is an easier method, along the lines of average tree size, which computes average, bypassing the probability distribution.

$\endgroup$

1 Answer 1

1
$\begingroup$

You are correct that the method used in the solution to the average tree size question is simpler. This is found in Ross' text $\it Introduction \ to \ Probability \ Models,$ 8th Edition. I will follow the approach given there.

Let $T_n$ be the number of trials needed to get $n$ consecutive successes, where the probability of success is $p.$ Let its expected value be $M_n.$ Conditioning on $T_{n-1},$

$$M_n = E[T_n] = E \left[ E \left[ T_n|T_{n-1} \right] \right]$$

Now consider that if you have had $n-1$ successes, you either reach your goal on the next trial or you restart: $$E \left[ E \left[ T_n|T_{n-1} \right] \right] =(T_{n-1}+1)(p)+(T_{n-1}+1+E[T_n])(1-p)$$

This simplifies to

$$ E \left[ E \left[ T_n|T_{n-1} \right] \right] =T_{n-1}+1+(1-p)E[T_n].$$

Taking the expectation of both sides gives $$M_n = M_{n-1} + 1 + (1-p)M_n,$$ which gives the recursive $$M_n = \dfrac{1}{p} + \dfrac{M_{n-1}}{p} $$

But the time $T_1$ until the first success is geometric and so we know $$M_1 = {{1} \over {p}}$$

So $$M_2 = \dfrac{1}{p} + \dfrac{1}{p^2}$$

and in general

$$M_n = \dfrac{1}{p} + \dfrac{1}{p^2} + \cdots + \dfrac{1}{p^n}$$

$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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