Google Answers Logo
View Question
Q: Probability of achieving 0 to n objectives in with n chances of varying probabil ( Answered 5 out of 5 stars,   0 Comments )
Subject: Probability of achieving 0 to n objectives in with n chances of varying probabil
Category: Science > Math
Asked by: mnesin-ga
List Price: $25.00
Posted: 11 Sep 2003 12:34 PDT
Expires: 11 Oct 2003 12:34 PDT
Question ID: 254700
Probability question:
Several objectives need to be achieved. There are several chances (n),
of varying probablility, to achieve an objective. Success is rated by
the number of objectives achieved.

If none of the chances work out, no objectives are achieved. If all of
the chances work out, n objectives are achieved. Obviously there is
everything in between. Therefore, the success is rated by the n+1
possible outcomes of 0 to n objectives achieved.

What is the algorithm to calculate the probability of each of the
possible outcomes?

If the answer comes with pseudo-code, great, I need a function. 

I'd like to pass that function a variable length array of
probabilities (each between 0 and 1 inclusive) and have it return an
array, whose length is one greater than that passed in, of
probabilities (each between 0 and 1 inclusive) for each of the
possible outcomes.

For example, say I have 2 chances, each at 50% probability. I would
pass the function an array [0.5, 0.5]. The returned array should be
[0.25, 0.5, 0.25] (25% of 0, 50% of 1, and 25% of 2 objectives
achieved). I probably don't need to point out that the sum of the
elements of the returned array should add up to 1.

More examples:
5 chances at 100%: [1,1,1,1,1] -> [0,0,0,0,0,1]
3 chances at 0%: [0,0,0] -> [1,0,0,0]
One chance at 50% and a second at 25%: [0.5,0.25] -> [?,?,?]

If the answer comes with a JavaScript function, tip-o-rama.

Subject: Re: Probability of achieving 0 to n objectives in with n chances of varying probabil
Answered By: mathtalk-ga on 11 Sep 2003 23:42 PDT
Rated:5 out of 5 stars
Hi, mnesin-ga:

Algorithm Description

The algorithm can be given in very simple terms.  To throw a bit
of perspective on it, this sort of probability problem can be
called a Markov process.

Let's start by giving names to the two vectors that appear in
your problem statement.  On one hand we are given as an input
the "probability vector" of variable length, which contains in
each entry a "chance of success" for its respective objective:

P = [p_1,p_2, ... , p_n]  if there are n objectives

On the other hand we have a "state vector" which also contains
probabilities, but of a cumulative nature:

V = [Pr(0 objectives),Pr(1 objective), ... , Pr(n objectives)]

The initial "state" before any "chance" is taken must consist of
the entire probability being concentrated in the "no objectives"
acheived category, i.e. the state vector looks like:

V = [1,0, ... , 0]

Taking the first chance at acheiving an objective amounts to a
linear transformation on the state vector.  That is, if the
try succeeds with probability p and fails with probability 1-p:

Pr(k objectives after try) := p*Pr(k-1 objectives before try)

                      + (1-p)*Pr(k objectives before try)

This could be expressed in matrix notation, as always for linear
transformations, but that would really be overkill.  Mainly you
just need to understand that we start with V = [1,0, ... ,0] and
then do some arithmetic to update its entries repeatedly for each
of the "objectives" whose chances of success are detailed in P.

Pseudo-code Outline

As you already noted, the length of vector V is always one more
than the length of P.  So I'll write the pseudo-code like this,
assuming as inputs the floating point vector P and its length n.

0. Intialize a floating point array V of length n+1 so that its
first entry V[0] = 1.0 and otherwise all entries of V are zero.

1. Next we loop over the entries in P, from "left to right", i.e.
let i = 0 to n-1 be a loop index, and assign local variable p to
contain P[i], the probability of success for the i+1'st chance.

2. Then we perform a second "inner loop" over the entries in V,
but it will be convenient to work from "right to left", i.e. to
update the higher entries before updating any lower ones.  This
is a minor detail but avoids the need of an extra variable.  We
take advantage of the "boundary conditions" by writing the loop
in a slight unrolled form, doing the first & last steps outside
the loop proper:

let V[i+1] := p*V[i]

if i > 0, for k = i to 1, let V[k] := p*V[k-1] + (1-p)*V[k]

let V[0] := (1-p)*V[0]

3. Continue the "outer loop" on i described in step 1.  When we
finish the loop on i, we are done.

Worked Example

Let's solve the last illustration given in your question:

One chance at 50% and a second at 25%: [0.5,0.25] -> [?,?,?] 

We initially set V = [1,0,0].

After the first chance at 50% is applied, we get:

V = [0.5,0.5,0]

After the second chance at 25% is applied, we get:

V = [0.375,0.5,0.125]

Javascript Implementation

Cut and paste from below the line of asterisks into a text
file and save it as C://document.htm or whatever you want.

I've tested this with IE 6, so let me know if there are any
quirks with your browser.

regards, mathtalk-ga

* * * * * * * * * * * * * * * * * * * * * * * * *


<SCRIPT language="JavaScript">

function arrayChances( arrayP )

  var n = arrayP.length;  // get length of P

  var V = new Array(n+1);

  var i=0;

  // initialize V = [1,0,...,0]

  V[0] = 1.0;

  for (i = 1; i <= n; i++)
    V[i] = 0.0;

  // perform outer loop over P

  for (i = 0; i < n; i++)
    var p = arrayP[i];

    // perform inner loop over V

    V[i+1] = p*V[i];

    if (i > 0)
      for (var k = i; k > 0; k--)
        V[k] = p*V[k-1] + (1-p)*V[k];

    V[0] = (1-p)*V[0];

  return V;

function displayChances( arrayV )
  // loop over elements of V

  var m = arrayV.length  // get length of V

  for (var j = 0; j < m; j++)




<A HREF="javascript:displayChances( arrayChances( [0.5,0.25] ) )">
Click here</A>
mnesin-ga rated this answer:5 out of 5 stars and gave an additional tip of: $31.25
Perfect. Your function works great, the explination is thourough. Fast
answer, fast algorithm. Best money I've spent in a long time.

There are no comments at this time.

Important Disclaimer: Answers and comments provided on Google Answers are general information, and are not intended to substitute for informed professional medical, psychiatric, psychological, tax, legal, investment, accounting, or other professional advice. Google does not endorse, and expressly disclaims liability for any product, manufacturer, distributor, service or service provider mentioned or any opinion expressed in answers or comments. Please read carefully the Google Answers Terms of Service.

If you feel that you have found inappropriate content, please let us know by emailing us at with the question ID listed above. Thank you.
Search Google Answers for
Google Answers  

Google Home - Answers FAQ - Terms of Service - Privacy Policy