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
* * * * * * * * * * * * * * * * * * * * * * * * *
<HEAD>
<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++)
{
alert(arrayV[j]);
}
}
//-->
</SCRIPT>
</HEAD>
<BODY>
<A HREF="javascript:displayChances( arrayChances( [0.5,0.25] ) )">
Click here</A>
</BODY> |
,
0 Comments
)