Calculating the probability of succeeding on multiple checks

[Jeff the Green]

I love incantations (http://www.d20srd.org/srd/variant/magic/incantations.htm). Love them. But they're hard to balance.

The way it works is that you make skill checks to cause a magic effect. If you fail two in a row, the incantation fails and there's some dire consequence, and you have to make 6-9 successful checks to complete the incantation.

Now, I know how I'd calculate the probability of succeeding at at least x out of y checks, but the number of attempts at the skill checks is potentially variable, and I really don't know how I calculate the probability of succeeding at x checks before failing y in a row. Anybody on the Playground feel like teaching me a bit of math?

[limejuicepowder]

Basically, multiply the percent chance of each check together. For example, there is a 1/400 chance of rolling two 20's in a row on a 20 sided die.

1/20 x 1/20 = 1/400

To figure out your total chance of success for multiple roles, figure out the fraction for each by what numbers you can roll to succeed over 20 (all skill checks right?)

Example:

Three skill checks that need to be made. On the first the character must roll at least a 13, the second at least a 7, and the third at least a 10. Converted in to fractions, we get 8/20, 14/20, and 11/20, respectively

Now multiple those fractions together, and we get 1232/8000. Convert that in to decimal form gives .154, or a 15% chance of success (ouch!)

[SimonMoon6]

I love incantations (http://www.d20srd.org/srd/variant/magic/incantations.htm). Love them. But they're hard to balance.

The way it works is that you make skill checks to cause a magic effect. If you fail two in a row, the incantation fails and there's some dire consequence, and you have to make 6-9 successful checks to complete the incantation.

Now, I know how I'd calculate the probability of succeeding at at least x out of y checks, but the number of attempts at the skill checks is potentially variable, and I really don't know how I calculate the probability of succeeding at x checks before failing y in a row. Anybody on the Playground feel like teaching me a bit of math?

There's always the ugly way of considering the possibilities. Suppose your chance of success is A and your chance of failure is B (both written as decimals, so 50% is 0.5). Then consider all the possibilities. I'll assume you need 6 successful checks for this example:

Possibility 1: 6 successes in a row
Probability: A*A*A*A*A*A

Possibility 2: 7 rolls, one of which is a failure.

Example: 5 successes, a failure, a success
Probability: A*A*A*A*A*B*A

It's similar for the other possibilities of getting exactly one failure. If the failure is the fifth roll (instead of the 6th as above) it'd be A*A*A*A*B*A*A, which works out to be the same thing. There are six ways to get exactly one failure, so we'll just take that probability we found in possibility 2 and multiply it by 6.

Possibility 3: You make eight rolls, two of which are failures, neither of which are adjacent. I'm sure there's a method using combinations or permutations to figure this out, but we can just list them:

Failing first:
B*A*B*A*A*A*A*A
B*A*A*B*A*A*A*A
B*A*A*A*B*A*A*A
B*A*A*A*A*B*A*A
B*A*A*A*A*A*B*A

First failure is second roll:
A*B*A*B*A*A*A*A
A*B*A*A*B*A*A*A
A*B*A*A*A*B*A*A
A*B*A*A*A*A*B*A

First failure is third roll:
A*A*B*A*B*A*A*A
A*A*B*A*A*B*A*A
A*A*B*A*A*A*B*A

First failure is fourth roll:
A*A*A*B*A*B*A*A
A*A*A*B*A*A*B*A

First failure is fifth roll:
A*A*A*A*B*A*B*A

So, there are fifteen ways that can happen.

Possibility 4: Nine rolls, three of which are failures.

(to be filled in later)

Possibility 5: Ten rolls, four of which are failures

Like B*A*B*A*B*A*B*A*A*A

Possibility 6: Eleven rolls, five of which are failures

Like B*A*B*A*B*A*B*A*B*A*A

Possibility 7: Twelve rolls, six of which are failures

Like B*A*B*A*B*A*B*A*B*A*B*A

Possibility 8: Thirteen rolls, seven of which are failures. This can't happen without two adjacent failures, so forget this. We've come to the end of the possibilities.

So, to compute the chance of success, you'll just have to take our results from possibilities one through seven:

1*A^6 + 6*(A^5*B) + 15*(A^4*B^2) + (probably 20)*(A^3*B^3) + (probably 15)*(A^2*B^4) + (probably 6)*(A*B^4) + 1*(B^6).

I'm writing "probably" because I'm predicting based on Pascal's Triangle (which I could justify using permutations or combinations if I felt like it, I think) rather than counting.

And then, if you want to know your chance of failure, take 1 minus the probability of success.

------------------------

If you want to do this again, needing more than 6 successes, the pattern is pretty obvious. You have coefficients in front of A raised to a power times B raised to a power. The powers of A decrease as the powers of B increase. (So with 7 successes needed, you'd go with 1*A^7 + ?*A^6*B^1 + ..., for example.) To figure out the coefficients needing n successes, just take the entries in the n+1 st row in Pascal's triangle.

[ahenobarbi]

Actually this is quite complicated. I could write a simple script that would estimate the probability (try many times, divide number of successes by number of trials).

[ahenobarbi]

There's always the ugly way of considering the possibilities. Suppose your chance of success is A and your chance of failure is B (both written as decimals, so 50% is 0.5). Then consider all the possibilities. I'll assume you need 6 successful checks for this example:

It escalates pretty quickly. You'd need to consider something between 2^{required number of successes} and 2^{(required number of successes)*(number failures in a row failing the attempt - 1)}...

[asnys]

Let p be your probability of success, n the number of successes you need, and k the number of failures before you succeed. The probability of rolling a given string of successes and failures such that you have n successes, k failures, and no adjacent failures is:

(p^n) * ((1-p)^k)

The number of such possible strings is:

n! / (k! * (n-k)!)

Because this is the same as choosing k objects out of n possible choices without regard to order. This formula is also written C(n, k).

Therefore, the probability of getting k failures before you get n successes is:

C(n, k) * (p^n) * ((1 - p) ^ k)

We then sum over k = 0 (all successes in a row) to k = n. We can use the binomial formula to make this simpler. The binomial formula is:

SUM(from k = 0 to k = n) of C(n, k) * a^k * b^(n-k) = (a+b)^n

Let a = 1 - p, b = 1. This gives us:

SUM(from k = 0 to k = n) of C(n, k) * (1 - p)^k = (2 - p)^n

Now multiply both sides by p^n to get:

SUM(from k = 0 to k = n) of C(n, k) * p^n * (1 - p)^k = (p^n)((2 - p)^n)

I think that should work.

Edit: Corrected algebra error; since you can, in fact, have k = n (FSFSFSFS...).

[ahenobarbi]

Here ya go: http://codepad.org/U6wby56h

[ahenobarbi]

Let p be your probability of success, n the number of successes you need, and k the number of failures before you succeed. The probability of rolling a given string of successes and failures such that you have n successes, k failures, and no adjacent failures is:

(p^n) * ((1-p)^k)

This is probability of getting n successes and k failures, without taking order into account.

Well if you really want to count exact probability I'd do it like that:

p - probability of success
n - needed successes
f - number of failures in a row that fail the attempt

F_k - random event - there were k successes in a row and than one success (and nothing and success before that)
F - random event - there were 1 to (f-1) failures than one success
S_l - random event - the attempt succeeded, there were l F-events
S - the attempt succeeded

P(F_k) = (1-p)^k p
P(F) = sum( P(F_k) for k =1..(f-1))
S_l = ((P(F))^l) * (p^(n-l) ) * (n!/(l! (n-l)!))
S = sum(P(S_l) for l = 0..n))

[asnys]

This is probability of getting n successes and k failures, without taking order into account.

No, that does take order into account. (p^n)((1-p)^k) is the probability of getting a specific string of S and F containing n S's and k F's. The number of possible strings of n S's and k F's such that no two F's are adjacent and the string ends with an S is C(n, k), because choosing such a string is equivalent to choosing k S's to put an F in front of. Multiplying the two together gives the probability of getting n S's and k F's, ending with an S, with no two F's adjacent.

[ahenobarbi]

No, that does take order into account. (p^n)((1-p)^k) is the probability of getting a specific string of S and F containing n S's and k F's. The number of possible strings of n S's and k F's such that no two F's are adjacent and the string ends with an S is C(n, k), because choosing such a string is equivalent to choosing k S's to put an F in front of. Multiplying the two together gives the probability of getting n S's and k F's, ending with an S, with no two F's adjacent.

Ah... you convinced me I think.