Math help: probability of multiple d20s

[Spoonist]

Didn't know if I should put it in G&C or SLAM but I figured its a pure math question even though the problem stems from an RPG.

What I would like is a formulaic approach to the probability of rolling a specified number of "successes", ie < or = than X. Then for each success you get a fixed number of second rolls > than X. Where X is a value between 1-19. (If both rolls pass you get an increase of 1 so the % correlates directly to the result given).

What I want to do is show the difference between only getting 1 second roll, and getting either 2, 3 or endless second rolls. With what that implies for lower and higher numbers.

Rolling 1d20 its pretty straightforward. It turns out as a bell curve with '10' as the peak. (Rolling 10 or lower with 1d20 = 50%, then rolling higher than 10 = 50%, so for a combined result of 25%, or an average increase of 0.25). Since there is only the possibility of 1 second roll this shows no trend.

Going to 2d20 I can still crunch it, but going into 3d20 and above is too much crunching for me, and I probably want to go all the way up to 8d20 to show the trend I'm looking for. Which would be far too tedious doing it the way I do it.

Here is how convoluted I solve it for 2d20, first convert X from the 1-19 value into 5%-95%.
**If only one second roll is allowed:
Prob of getting second roll=X+X-(X*X), then prob of second roll being higher=1-X, then multiplying those results.
Example for the peak 10, probability of succeeding with the second roll=(50%+50%-25%)*(100%-50%)=75%*50%=37.5%.So an average increase of 0.375.
**If up to two second rolls are allowed:
Here I don't have the skills so I calculate the scenarios seperately and then add them together, which is why I need your help.
prob of getting 1 second roll=X+X-(X*X)-(X*X), removing the double success
prob of getting 2 second rolls=X*X
prob of 2 second rolls giving one increase=(1-X)+(1-X)-(1-X)(1-X)-(1-X)(1-X)
prob of 2 second rolls giving two increases=(1-X)(1-X), doubling this for average increase.
Average increase=(one success one increase)+(two successes one increase)+2*(two successes, two increases)
=((X+X-(X*X)-(X*X))*(1-X))+((X*X)*((1-X)+(1-X)-(1-X)(1-X)-(1-X)(1-X)))+2*((X*X)*(1-X)(1-X))
Example for 10
=((50%+50%-(50%*50%)-(50%*50%))*(1-50%))+((50%*50%)*((1-50%)+(1-50%)-(1-50%)(1-50%)-(1-50%)(1-50%)))+2*((50%*50%)*(1-50%)(1-50%))=0.5

So now I need to expand that to 3d20 through 8d20, which given my approach would be a pain in the ass. So there must be an easier way.

PS
I do the crunching in excel so once I've tediously worked out the formula I just replicate it to show the trend
DS
PPS
Sorry for the confusing way to try to explain it.
DDS
PPPS
For you who wonder its for Pendragon RPG.
DDDS

[Kuroneko]

I didn't really want to get into this because your description is very vague, in both the rules and what you're even trying to quantify. But since it's the weekend, I might as well try to make sense of it.

Then for each success you get a fixed number of second rolls > than X.

If re-rolls can multiply like that and not have a fixed upper limit, then the expected number of total rolls can be infinite. But I suspect you rather meant something like "for each success, you get an extra roll > X, up to some fixed number of total extra rolls." Which is very different from what was said, which implies that it a single success could generate multiple extra rolls by itself.

Your calculations imply that the rules are basically thus:
(1) For each initial roll under a set threshold, you get an extra roll, but with no more than a fixed number of total extra rolls.
(2) In order to count toward as "an increase", an extra roll has to be higher than the threshold. An extra roll not above the threshold is ignored for the purposes of counting increases (but does count toward the upper limit of total extra rolls), even it is also higher than the initial roll.
Your calcs make sense in light of those rules, but your description is a bit different. For example:

(If both rolls pass you get an increase of 1 so the % correlates directly to the result given).

I don't any idea what that means. What it seems to say, though, is provide an additional rule (2):
(3) If re-roll is under the threshold, it generates another extra roll, just as the initial rolls do.
That would also cohere with "endless second rolls" you described earlier (otherwise, it would automatically be capped to the number of initial dice). But if (3) is true, then your calculations are wrong. You could get more than one extra roll on 1d20 (or not, depending if the extra-chance maximum), and your 2d20 with up to two extra rolls should then be
(one [initial] success one increase) = P(2d20 gives 1 extra roll)[ (1-X) + X(1-X) ],
the X(1-X) term being missing from your calculation, which corresponds to having another re-roll if the first re-roll is ≤X.

This leaves us in an odd position: your description of the rules and your calcs are inconsistent with each other.

____
Assuming (3) is false and your calcs are correct in that extra rolls below the threshold are always discarded, the situation isn't too bad. Let p be the probability of generating an extra roll (X/20), q = 1-p, and f(k) = C(n,k) pk qn-k the probability of n rolls generating k extra rolls. For n initial dice, let m = min{n, extra roll limit}. The probability that an extra roll has an effect is then
[1] P = Sumk=1n[ f(k) (1-pmin{m,k}) ],
which is ugly and almost certainly does not give a closed form in the general case. It is, however, a lot more suited to automated calculation. For the specific case of m = n, the distributing and applying the binomial theorem gives a very nice form:
[2] Pn = [(p+q)n - qn] - [(p²+q)n - qn = 1 - (p²+q)n

On the other hand, the k rolls with probability q of producing an increase each, the expected number of increases is kq. So for the total expected number of increases is just
[3] <I> = Sumk=1n[ f(k) min{k,m} q ].
Once again, this doesn't have a simple closed form in general, but is easy enough to calculate for a particular fixed m. Some examples for particular <Im>, valid for 1≤m≤n:
[4] <I1> = q(1-qn)
[5] <I2> = npqn + 2q[1-(qn + npqn-1)] = 2q(1-qn) - 1[npqn]
[6] <I3> = npqn + 2C(n,2)p²qn-1 + 3q[1-(qn+npqn-1+C(n,2)p²qn-2)] = 3q(1-qn) - 2[npqn] - 1[{n(n+1)/2}p²qn-1]
[7] <In-2> = npq - [ f(n-1)q + 2f(n)q ] = npq - npn-1q² - 2pnq
[8] <In-1> = npq - pnq
[9] <In> = npq
You should understand how the binomial theorem was used in the above and check them yourself.

I emphasize again that the basic assumption there is that extra rolls can't breed yet more extra rolls themselves and that extra rolls not higher than X don't contribute to "increases," which is what your calculations assumed. Make sure that's really correct in your ruleset, since your description of the rules appears to contradict that.

[Ariphaos]

Spoonist, the best thing to do is just to present your desired test mechanic and not try to conflate it with your own calculations or interpretations. Excel forces rounding unless you tell it not to (a 1d20 does not 'peak' at 10), has errors of its own on occasion, and any mistakes you make get compounded with that. State the mechanic clearly, then, in a separate section, present what you have worked out so far.

If I'm reading you right, your test mechanic is a check for success mechanic using d20's, someone rolls a number of d20's and anything above a target number (TN) from 1-19 is considered a 'success'. For each success, you get a second roll at the same TN, and this continues indefinitely until the check fails?

[Spoonist]

Thanks, sorry for the confusion. I should have waited with posting it until rereading it the next day.

I think that Kuroneko got it right by looking at the numbers and ignoring my ravings. Maybe except for an less and equal to, I will try his formula and see if it corresponds to my brute force lower numbers.
Thanks a bunch.

Spoonist, the best thing to do is just to present your desired test mechanic and not try to conflate it with your own calculations or interpretations.

Excellent suggestion, that is what I should have done.

Excel forces rounding unless you tell it not to

Yupp, but I've set it to %age and 5 decimals so it should be OK.

(a 1d20 does not 'peak' at 10),

Again sorry for the confusion, the second roll result peaks at 10.

State the mechanic clearly...

You have a skill between 1-19. You roll lower or equal to the skill to succeed. Your skill is usually tested several times (1-8) during a session. If you succeed you get a training check. When the session is over you go to the training phase where you roll 1d20 per training check, if you roll higher than your current skill you increase it by 1.

What I'm trying to test for is whether allowing only one, or allowing multiple training checks is better for low skill or high skill.

[Ariphaos]

Oh right. I was wondering where you pulled the mechanic from.

Pi = X/20 * (20 - X)/20

So you'll have 19/400, 36/400, 51/400, 64/400, 75/400, 84/400, 91/400, 96/400, 100/400, 96/400 ...

The bell curve you were talking about.

When checking multiple rolls, the easiest value to check for is that no 'trigger' at all will occur, which is a bit different than calculating the predicted number of increases, since I don't think there is any clean way of doing that with the second roll's target increasing, but you can instead switch to

Pi = (1 - X/20 * (20 - X)/20)^R

Where R is the number of rolls

1: (381/400)^8 ~= 0.6775...
2: (364/400)^8 ~= 0.4703...
9: (301/400)^8 ~= 0.1028...
10: (300/400)^8 ~= 0.1001...
11: (301/400)^8 ~= 0.1028...
18: (364/400)^8 ~= 0.4703...

The resulting probabilities being the chance that no increase will occur.

[Kuroneko]

The skill level for which the expected training increases is maximum, in terms of probability of success on a single attempt p = 1-q:
m = 1: p = 1-[n+1]-1/n
The subtractand is a monotonically increasing function of n, so low-skilled players will tend to increase their skills more for the same number of attempts. Only for a single attempt do the balances equal, since then <I1> = pq, which is symmetric in p's and q's.
m = n: p = 1/2
The expectation function <In> is symmetric in p'q and q's, so there if every success leads to a training check, middle-ranked (X = 10) players are favored in terms of expected skill increases, with equal drop-off for skill levels away from this middle ground.

---
Let's try a trick: associate with each player of skill level p a mirror twin whose skill level is q (i.e., X = 5 <--> X' = 20-X = 15, etc.). The goal is to compare these two players. Since <Im> = In - q Sumk=m+1n[ f(k)(k-m) ], we can write the difference between them as
Δm = <Im> - <I'm> = Sumk=m+1n[ C(n,k)(k-m){pn-k+1qk - pkqn-k+1} ].
Setting {...}>0, we have (p/q)n-2k > 1. If the player is lower-skilled than the mirror twin, then p/q < 1, so that we should have n-2k<0. Therefore:

-- Whenever m>(n-1)/2, a low-skilled player always has a higher expectation of skill increases than the higher-skilled mirror twin! --

For m≤(n-1)/2, things are more complicated because there is a mixture of positive and negative terms in the summation for Δm, but you might get a workable bound by pairing each k<n/2 with k' = n-k > n/2 and requiring their combined contribution to Δm to still be positive (note that this condition is not necessary for Δm > 0, but it does assures it). C(n,k) = C(n,n-k) means they combine nicely with some extra factor of pq between them.

Then again, it might be easier to write <Im> as mq(1-qn) - {positive terms} (and it's not hard to check that they are, indeed, positive), and get results for the low-m region that way.