View Question
Q: Probability of achieving 0 to n objectives in with n chances of varying probabil ( Answered ,   0 Comments )
 Question
 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. Thanks!```
 ```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 * * * * * * * * * * * * * * * * * * * * * * * * * Click here ```
 mnesin-ga rated this answer: 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.```