Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Given an integer $n$, one does $n$ random selections with repetition one after the other. For each selection there are two possibilities a success $X$ and a failure $O$. For each selection $i\le n$ the probability that it's a success is $p_i$ and the probability that it is a failure is $1-p_i$.

For a possible complete $n$ selections, if there are $m$ strings of $X$'s separated by strings of $O$'s, then the score for that set is $\displaystyle \sum ^m_{j=1} x_j^2 $ where $x_j$ is the length of the $j$-th $X$-string. If there are no $X$ string then the score is zero.


For $n=12$, a possible complete selection is $XOXXOOOXXXXO$, there are $3$ strings of $X$'s and the score is $1^2 +2^2+4^2 = 21$ while the probability is = $\displaystyle \prod^n_ip_i$

I am trying to find a general formula for both the score and its probability, I have done for the small cases where $n=1,2,3,4$ and I can't seem to find a general formula for it when $n$ gets really big, like $1000$ big.

My real goal is to calculate the expected value for any integer $n$ given the probabilities at each level of selections.

share|cite|improve this question
up vote 3 down vote accepted

For every $n\geqslant1$, let $s_n$ and $\ell_n$ denote respectively the mean score and the mean length of the terminating X-string based on the selection with probabilities $(p_k)_{1\leqslant k\leqslant n}$.

If the selection $n+1$ is O, the score does not change and the length of the terminating string becomes zero. If the selection $n+1$ is X, one adds $1$ to the length of the terminating string and the last squared length $\ell_n^2$ is replaced by $(\ell_n+1)^2$, that is, one adds $1$ to the length and $2\ell_n+1$ to the score.

Thus, $s_{n+1}=s_n+p_{n+1}(2\ell_n+1)$ and $\ell_{n+1}=p_{n+1}(\ell_n+1)$ for every $n\geqslant0$, with $s_0=\ell_0=0$. It follows that, for every $n\geqslant1$, $$ \ell_n=\sum_{k=1}^n\prod_{i=k}^np_i,\qquad s_n=\sum_{k=1}^np_k(1+2\ell_{k-1}). $$ The homogenous case when $p_n=p$ for every $n\geqslant1$ yields $$ \ell_n=\frac{p}{1-p}(1-p^n),\qquad s_n=np\frac{1+p}{1-p}-2\frac{p^2}{(1-p)^2}(1-p^n). $$

share|cite|improve this answer
thank you! this is brilliant! – user31280 Oct 31 '12 at 14:40

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.