Using convolution to calculate session tap out probability
February 28th, 2023 at 12:37:07 PM
permalink
I tried to answer this question in MBJ's original thread. I am starting a new thread because I don't want my response to MBJ to get lost in a longer thread. My terse explanation in the original thread made sense to me but it was probably incomprehensible to people who have never worked with discrete convolutions.Quote: MichaelBluejaySUMMARY: How to calculate or simulate how much to bet per round for casino games given a starting bankroll, hours of play, rounds per hour, and risk of ruin (RoR)?
link to original post
I finally got around to working up an explanation that hopefully makes my comments about discrete convolution clearer. If MBJ still doesn't understand it or doesn't need something this accurate, perhaps someone else will find it interesting or helpful. This was the Wiki reference I cited as background:
https://en.wikipedia.org/wiki/Convolution_of_probability_distributions
The point of this reference is that if two variables are independent, then the convolution of the sum is just the product of the convolutions. We can play a fair coin-flip for one unit 9 times and get a probability distribution function (PDF9 or P9) for the result with respect to the starting bankroll. If we get another P7 for 7 games, then we can get the PDF16 by convolving P9 @ P7 = P16 (where I am using @ to represent the PDF convolution operator).
I think my example of the convolution method will be easier to understand with graphical output. I realized I could represent PDFs with ascii output if I used integers for the PDFs and just printed the last digit in the column representing the number of bet units. In these examples, I assume the bettor starts with 25 units. Column zero represents zero, so the bettor is tapped out.
In the first example, Convolution Test #1, I start with a population of 1 in column 26, P1 has N=1 at 0. I create the PDF1 which has two elements, N=1 at -1 (1,-1) and N=1 at +1 (1,1). Now, I convolve P1 @ P1 = P2. P2 has three elements (1,-2)(2,0)(1,2) where I am using a more compact (n,v) notation for the unnormalized PDF. If I had normalized P2, then 1/4th of bettors are at +2 and -2 units and 2/4ths are at 0 units. P3 needs to be normalized by a factor of 8, P4 by 16, etc. It take a lot of space to present floating point numbers, so I use the unnormalized number (modulo 10) in my output.
Round limit: 64 Convolve Pn with P1
Prob::size: 2 count: 2 min: -1 max: 1
N: 1 V: -1
N: 1 V: 1
1 0 EV: 0
1 1 1 EV: 0
1 2 1 2 EV: 0
1 3 3 1 3 EV: 0
1 4 6 4 1 4 EV: 0
1 5 0 0 5 1 5 EV: 0
1 6 5 0 5 6 1 6 EV: 0
1 7 1 5 5 1 7 1 7 EV: 0
1 8 8 6 0 6 8 8 1 8 EV: 0
1 9 6 4 6 6 4 6 9 1 9 EV: 0
1 0 5 0 0 2 0 0 5 0 1 10 EV: 0
1 1 5 5 0 2 2 0 5 5 1 1 11 EV: 0
1 2 6 0 5 2 4 2 5 0 6 2 1 12 EV: 0
1 3 8 6 5 7 6 6 7 5 6 8 3 1 13 EV: 0
1 4 1 4 1 2 3 2 3 2 1 4 1 4 1 14 EV: 0
1 5 5 5 5 3 5 5 5 5 3 5 5 5 5 1 15 EV: 0
1 6 0 0 0 8 8 0 0 0 8 8 0 0 0 6 1 16 EV: 0
1 7 6 0 0 8 6 8 0 0 8 6 8 0 0 6 7 1 17 EV: 0
1 8 3 6 0 8 4 4 8 0 8 4 4 8 0 6 3 8 1 18 EV: 0
1 9 1 9 6 8 2 8 2 8 8 2 8 2 8 6 9 1 9 1 19 EV: 0
1 0 0 0 5 4 0 0 0 0 6 0 0 0 0 4 5 0 0 0 1 20 EV: 0
1 1 0 0 5 9 4 0 0 0 6 6 0 0 0 4 9 5 0 0 1 1 21 EV: 0
1 2 1 0 5 4 3 4 0 0 6 2 6 0 0 4 3 4 5 0 1 2 1 22 EV: 0
1 3 3 1 5 9 7 7 4 0 6 8 8 6 0 4 7 7 9 5 1 3 3 1 23 EV: 0
1 4 6 4 6 4 6 4 1 4 6 4 6 4 6 4 1 4 6 4 6 4 6 4 1 24 EV: 0
1 5 0 0 0 0 0 0 5 5 0 0 0 0 0 0 5 5 0 0 0 0 0 0 5 1 25 EV: 0
6 5 0 0 0 0 0 5 0 5 0 0 0 0 0 5 0 5 0 0 0 0 0 5 6 1 26 EV: 0
7 1 5 0 0 0 0 5 5 5 5 0 0 0 0 5 5 5 5 0 0 0 0 5 1 7 1 27 EV: 0
8 6 5 0 0 0 5 0 0 0 5 0 0 0 5 0 0 0 5 0 0 0 5 6 8 8 1 28 EV: 0
6 4 1 5 0 0 5 5 0 0 5 5 0 0 5 5 0 0 5 5 0 0 5 1 4 6 9 1 29 EV: 0
0 5 6 5 0 5 0 5 0 5 0 5 0 5 0 5 0 5 0 5 0 5 6 5 0 5 0 1 30 EV: 0
5 5 1 1 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 1 1 5 5 5 1 1 31 EV: 0
0 6 2 6 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 6 2 6 0 0 6 2 1 32 EV: 0
0 6 8 8 6 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 6 8 8 6 0 6 8 3 1 33 EV: 0
6 4 6 4 6 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 6 4 6 4 6 6 4 1 4 1 34 EV: 0
2 0 0 0 0 6 0 0 0 0 0 0 0 0 0 0 0 0 0 0 6 0 0 0 0 2 0 5 5 5 1 35 EV: 0
2 0 0 0 6 6 0 0 0 0 0 0 0 0 0 0 0 0 0 6 6 0 0 0 2 2 5 0 0 6 1 36 EV: 0
4 2 0 0 6 2 6 0 0 0 0 0 0 0 0 0 0 0 0 6 2 6 0 0 2 4 7 5 0 6 7 1 37 EV: 0
6 2 0 6 8 8 6 0 0 0 0 0 0 0 0 0 0 0 6 8 8 6 0 2 6 1 2 5 6 3 8 1 38 EV: 0
7 8 2 6 4 6 4 6 0 0 0 0 0 0 0 0 0 0 6 4 6 4 6 2 8 7 3 7 1 9 1 9 1 39 EV: 0
5 0 8 0 0 0 0 6 0 0 0 0 0 0 0 0 0 6 0 0 0 0 8 0 5 0 0 8 0 0 0 0 1 40 EV: 0
5 5 8 8 0 0 0 6 6 0 0 0 0 0 0 0 0 6 6 0 0 0 8 8 5 5 0 8 8 0 0 0 1 41 EV: 0
0 3 6 8 0 0 6 2 6 0 0 0 0 0 0 0 6 2 6 0 0 8 6 3 0 5 8 6 8 0 0 1 2 42 EV: 0
5 3 9 4 8 0 6 8 8 6 0 0 0 0 0 0 6 8 8 6 0 8 4 9 3 5 3 4 4 8 0 1 3 43 EV: 0
8 2 3 2 8 6 4 6 4 6 0 0 0 0 0 6 4 6 4 6 8 2 3 2 8 8 7 8 2 8 1 4 6 44 EV: 0
6 0 5 5 0 4 0 0 0 0 6 0 0 0 0 6 0 0 0 0 4 0 5 5 0 6 5 5 0 0 9 5 0 45 EV: 0
6 5 0 5 4 4 0 0 0 6 6 0 0 0 6 6 0 0 0 4 4 5 0 5 6 1 0 5 0 9 4 5 0 46 EV: 0
7 1 5 5 9 8 4 0 0 6 2 6 0 0 6 2 6 0 0 4 8 9 5 5 1 7 1 5 5 9 3 9 5 47 EV: 0
8 6 0 4 7 2 4 0 6 8 8 6 0 6 8 8 6 0 4 2 7 4 0 6 8 8 6 0 4 2 2 4 0 48 EV: 0
6 4 6 4 1 9 6 4 6 4 6 4 6 6 4 6 4 6 4 6 9 1 4 6 4 6 4 6 4 6 4 6 4 49 EV: 0
0 0 0 5 0 5 0 0 0 0 0 0 2 0 0 0 0 0 0 5 0 5 0 0 0 0 0 0 0 0 0 0 0 50 EV: 0
0 0 0 5 5 5 5 0 0 0 0 0 2 2 0 0 0 0 0 5 5 5 5 0 0 0 0 0 0 0 0 0 0 51 EV: 0
0 0 5 0 0 0 5 0 0 0 0 2 4 2 0 0 0 0 5 0 0 0 5 0 0 0 0 0 0 0 0 0 0 52 EV: 0
0 0 5 5 0 0 5 5 0 0 0 2 6 6 2 0 0 0 5 5 0 0 5 5 0 0 0 0 0 0 0 0 0 53 EV: 0
0 5 0 5 0 5 0 5 0 0 2 8 2 8 2 0 0 5 0 5 0 5 0 5 0 0 0 0 0 0 0 0 0 54 EV: 0
0 5 5 5 5 5 5 5 5 0 2 0 0 0 0 2 0 5 5 5 5 5 5 5 5 0 0 0 0 0 0 0 0 55 EV: 0
5 0 0 0 0 0 0 0 5 2 2 0 0 0 2 2 5 0 0 0 0 0 0 0 5 0 0 0 0 0 0 0 5 56 EV: 0
5 5 0 0 0 0 0 0 5 7 4 2 0 0 2 4 7 5 0 0 0 0 0 0 5 5 0 0 0 0 0 0 5 57 EV: 0
0 5 0 0 0 0 0 5 2 1 6 2 0 2 6 1 2 5 0 0 0 0 0 5 0 5 0 0 0 0 0 5 0 58 EV: 0
5 5 5 0 0 0 0 5 7 3 7 8 2 2 8 7 3 7 5 0 0 0 0 5 5 5 5 0 0 0 0 5 5 59 EV: 0
0 0 5 0 0 0 5 2 0 0 5 0 4 0 5 0 0 2 5 0 0 0 5 0 0 0 5 0 0 0 5 0 6 60 EV: 0
0 0 5 5 0 0 5 7 2 0 5 5 4 4 5 5 0 2 7 5 0 0 5 5 0 0 5 5 0 0 5 5 6 61 EV: 0
0 5 0 5 0 5 2 9 2 5 0 9 8 9 0 5 2 9 2 5 0 5 0 5 0 5 0 5 0 5 0 1 2 62 EV: 0
5 5 5 5 5 5 7 1 1 7 5 9 7 7 9 5 7 1 1 7 5 5 5 5 5 5 5 5 5 5 5 1 3 63 EV: 0
0 0 0 0 0 2 8 2 8 2 4 6 4 6 4 2 8 2 8 2 0 0 0 0 0 0 0 0 0 0 6 4 6 64 EV: nan
If you click the button above, you will see my program output. Each successive PDF is obtained by convolution Pn @ P1 = P(n+1). Note that the first time that a 1 appears in column 0 is in P25. It is impossible to lose 25 units before round 25 if you are only risking one unit on each round. I also calculate the EV of the PDF as another sanity check. The EV remains zero (relative to the starting bankroll) for all Pn.
In the second test below, I convolve P1 @ P1 = P2, then P2 @ P2 = P4, P4 @ P4 = P8,
Pn @ Pn = P(2n), etc. I get to P64 in just six convolution operations.
Round limit: 64 Convolve Pn with Pn
Prob::size: 2 count: 2 min: -1 max: 1
N: 1 V: -1
N: 1 V: 1
1 0 EV: 0
1 1 1 EV: 0
1 2 1 2 EV: 0
1 4 6 4 1 4 EV: 0
1 8 8 6 0 6 8 8 1 8 EV: 0
1 6 0 0 0 8 8 0 0 0 8 8 0 0 0 6 1 16 EV: 0
0 6 2 6 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 6 2 6 0 0 6 2 1 32 EV: 0
0 0 0 0 0 2 8 2 8 2 4 6 4 6 4 2 8 2 8 2 0 0 0 0 0 0 0 0 0 0 6 4 6 64 EV: nan
I am skipping past many PDFs, but if I actually needed P38, I could use P32 @ P4 @ P2 = P38 to get it quickly.
In the third test below, I am using a more complicated P1 with a count of 5 elements. This is meant to be an extremely simplified video poker PDF with a max payoff of 6:1. The P1 is asymmetrical, but the EV is zero. Again, it takes 25 rounds before there is a chance for the player to tap out. The normalization factor for P1 is 13, for P2 is 139, etc.
Round limit: 64 Convolve Pn with P1
Prob::size: 5 count: 5 min: -1 max: 6
N: 9 V: -1
N: 1 V: 0
N: 1 V: 1
N: 1 V: 2
N: 1 V: 6
1 0 EV: 0
9111 1 1 EV: 0
18903218222 1 2 EV: 0
930840497809637333 1 3 EV: 0
1624728892201600808266444 1 4 EV: 0
95555150551055560005000000005555 1 5 EV: 0
149404606046265412600010005050505054666 1 6 EV: 0
9760792181642295427141323755010005013403213777 7 EV: 0
1202644616488206328480805884828480044084044280468 8 EV: 0
99318489551942451117800953952669486226462880220660 9 EV: 0
105058505090500050503000525050600008005020000200002 10 EV: 0
9166028985692950540528385825209681078435370203242082 11 EV: 0
18403000262006444286642088421260540400280426328448089 12 EV: 0
935397346063862862286086008477971116002946409119402791 13 EV: 0
1674206418788494007028446660505624245614801414863818183 14 EV: 0
95005305500055585055900005005540550950007550035550050009 15 EV: 0
144402828000800238806424000400649406484082620280300080064 16 EV: 0
9715268982484604975700018442862215176885800880689753468526 17 EV: 0
12521256240868743038521800642852349838588206845456761232446 18 EV: 0
998680477227033126466301908549176240676178678511084027099203 19 EV: 0
1420706290223020584476863886422296881840522886445020500050006 20 EV: 0
93711558531813389578115673386463393153321756004373953378319046 21 EV: 0
387840648026287660902616403470085486823208207082788226980842526 22 EV: 0
9122772949662477311772191299015798326858938410535790409217621631 23 EV: 0
70200666722246264402604046048688464228888008464862482288146848821 24 EV: 0
779186617539284580662622088806802646800628280222404446865573848931 25 EV: 0
410341436325882468882520020624604624408266848206000866438589214185 26 EV: 0
444081250747906903487173624506842426240486004486466466914204836347 27 EV: 0
894886224882690605488840298624264966848428240844402829482546884666 28 EV: 0
373002456226137575900281915920657735606904486660604073557992228524 29 EV: 0
066781606709802666418981088744634365004600424124482725844647254409 30 EV: 0
653280535881578101558248949696532904748327267179287888118770489798 31 EV: 0
248600282202040220886222434820246260660806028824884684020582462608 32 EV: 0
444848482486840860844428959906038226286806040440226064689393642126 33 EV: 0
822487408286486688046207436103680880650824622220864224898767050426 34 EV: 0
450999790269888480866493884467362749195708058662284862574648231023 35 EV: 0
254204824624006489866948432629888126646484208226610269282124410643 36 EV: 0
331006218084640675135158379097507112282984220024933719705158111015 37 EV: 0
074524842908234169642464840427882549880823860703658800440262894263 38 EV: 0
594279435097110186164169222697355527954158515765867289472068111313 39 EV: 0
614666022702282001200846832442820966808682600244694488000946842209 40 EV: 0
973902213751020979192407597504815797646704228268155362019179680597 41 EV: 0
034320634147022143810041498986692121480642426345414727852521804765 42 EV: 0
838092384502189005863432496016386726566985421986088925472921547641 43 EV: 0
608840668180404025242884850848226720216686640168004046284566082828 44 EV: 0
428684449997804775518223933964251977397424015359484348201575822322 45 EV: 0
288488418305234127212225236348234324476163876661468604694445290648 46 EV: 0
460728134608216909673032436418562331708564057636520647777577637747 47 EV: 0
028280068622200884206466284686442224022620608482206008066260648064 48 EV: 0
666820062884006840244666484084208826220242082800880626644468620622 49 EV: 0
042409884822244466866400048640284404826486264468626020264602084802 50 EV: 0
436793332601222008288446262462408220404240224866284202826848682662 51 EV: 0
220000686488466065684840460082882224068684004840468420646804822668 52 EV: 0
428924002622000239312687826268844008246642244028682660682024864620 53 EV: 0
824445406120284783658706602889868622682604882042842226020420020028 54 EV: 0
970716715116665220602152614173774267660626620262608624264488080026 55 EV: 0
478088224102660260004684412840408480800881628422286486862022648268 56 EV: 0
119360877971840766888686597142676800804291132807624448648866064400 57 EV: 0
672383478721604082644345816789640264078145852342420603240604204666 58 EV: 0
260429878741746145485566224389780123374600034776034155538063200688 59 EV: 0
202246604040636265424900026881022068056049806568440248260024000089 60 EV: 0
224768864200597757941112860593512243951595385192462528260426604031 61 EV: 0
674283828747654064466821882326038443456881646089086623280940426141 62 EV: 0
425874543743665841492217733576595017017152100874570858971378481042 63 EV: 0
468664468262868064048804490206884842062668086884226224422084282862 64 EV: 0
In the fourth test below, you can see that the convolution Pn @ Pn = P(2n) works just as well for an asymmetric PDF.
Round limit: 64 Convolve Pn with Pn
Prob::size: 5 count: 5 min: -1 max: 6
N: 9 V: -1
N: 1 V: 0
N: 1 V: 1
N: 1 V: 2
N: 1 V: 6
1 0 EV: 0
9111 1 1 EV: 0
18903218222 1 2 EV: 0
1624728892201600808266444 1 4 EV: 0
1202644616488206328480805884828480044084044280468 8 EV: 0
144402828000800238806424000400649406484082620280300080064 16 EV: 0
248600282202040220886222434820246260660806028824884684020582462608 32 EV: 0
468664468262868064048804490206884842062668086884226224422084282862 64 EV: 0
This is just a demo program using 64-bit unnormalized integers. My actual convolution program uses 64-bit floating point values.
Let's get to MBJ's problem. If you have this convolution program, you can quickly iterate until the round where players start tapping out. Then, you remove elements from the PDF where the player has tapped out and save them in another bucket. This bucket accumulates the session-tap-out-probability (STOP). This is what most people call risk-of-ruin (RoR). If you want to be very accurate, you have to start convolving by Pn @ P1. Otherwise you will miss some players whose bankroll went negative but recovered to a positive value before you got to the next PDF.
In Test #1 above, one player tapped out on round 25, so STOP = 1 / 2^25. In a coin flip, nobody can tap out in round 26, but it would seem that 7 players would tap out in round 27. This is not right because I have not removed the player who tapped out in round 25.
In my video poker PDF program, I also remove probability from the PDF for players who have hit mutiple Royals and are thousands of units to the good. If you are only concerned about calculating STOP, then these lucky players don't affect the calculation. As a result my PDF size does not grow indefinitely as we go to millions of rounds of video poker.
I am including a stripped down version of the program so you can see how simple the convolution process is. If you want to port this to another language, I recommend that you start by using integer instead of floating point number to be sure that you get the right result.
typedef unsigned long long u_ll;
// a couplet of (n,v)
class cpl {
public:
u_ll m_n;
int m_v;
};
// the coin flip P1 has size = 2, and two couplets (1,-1) and (1, 1)
class Prob {
cpl * cplPtr;
int size; // allocated size for cplPtr
int min;
int max;
int count; // current count of cplPtr used
}
// the convolution algorthm stripped of error checking and diagnostics
int Prob::convolve(Prob & A, Prob & B, u_ll *& array)
{
max = A.max + B.max;
min = A.min + B.min;
int range = 1 + max - min;
array = new u_ll[range];
for (int i = 0; i < range; i++) {
array = 0;
}
int rA = A.max - A.min;
int rB = B.max - B.min;
int zB = B.cplPtr[0].m_v;
for (int iB = 0; iB < B.count; iB++) {
int zA = A.cplPtr[0].m_v;
for (int iA = 0; iA < A.count; iA++) {
u_ll nA = A.cplPtr[iA].m_n;
u_ll nB = B.cplPtr[iB].m_n;
int vA = A.cplPtr[iA].m_v;
int vB = B.cplPtr[iB].m_v;
int ind = vA - zA + vB - zB;
array[ind] += nA * nB;
}
}
int cnt = 0;
for (int i = 0; i < range; i++) {
u_ll n = array;
if (!n) continue;
cnt++;
}
setSize(cnt);
cnt = 0;
for (int i = 0; i < range; i++) {
u_ll n = array;
if (!n) continue;
cnt++;
add(n, i+min);
}
return range;
}
I just did timing tests of this code out to P4096. It takes 21 msec on one processor. The Pn @ Pn method is 20 times faster than Pn @ P1 after 4096 rounds. The comparison is even more dramatic for really long sessions (millions of rounds). For video poker, I routinely ran PDFs out to 4 million hands on 1998 vintage hardware. MBJ may not need this precision for his RoR calculator, but it would not be that computationally expensive. I have never used any online RoR calculator. I don't know what limitations they have for number of rounds. The complexity of the P1 PDF barely matters because the Pn PDF quickly grows in size. Therefore, my method will handle VP PDFs with the usual 9-15 pay lines quite easily.
Also, note that this integer version overflows 64-bit integers before P64 even with the simple coin-flip PDF. To do any serious work, I use a different version where the couplet has a 64-bit FP value.
Gambling is a math contest where the score is tracked in dollars. Try not to get a negative score.
February 28th, 2023 at 12:49:35 PM
permalink
It all seems very convoluted. LOL..I couldn't resist! But seriously, thanks! This is very interesting.Quote: MentalI tried to answer this question in MBJ's original thread. I am starting a new thread because I don't want my response to MBJ to get lost in a longer thread. My terse explanation in the original thread made sense to me but it was probably incomprehensible to people who have never worked with discrete convolutions.Quote: MichaelBluejaySUMMARY: How to calculate or simulate how much to bet per round for casino games given a starting bankroll, hours of play, rounds per hour, and risk of ruin (RoR)?
link to original post
I finally got around to working up an explanation that hopefully makes my comments about discrete convolution clearer. If MBJ still doesn't understand it or doesn't need something this accurate, perhaps someone else will find it interesting or helpful. This was the Wiki reference I cited as background:
https://en.wikipedia.org/wiki/Convolution_of_probability_distributions
The point of this reference is that if two variables are independent, then the convolution of the sum is just the product of the convolutions. We can play a fair coin-flip for one unit 9 times and get a probability distribution function (PDF9 or P9) for the result with respect to the starting bankroll. If we get another P7 for 7 games, then we can get the PDF16 by convolving P9 @ P7 = P16 (where I am using @ to represent the PDF convolution operator).
I think my example of the convolution method will be easier to understand with graphical output. I realized I could represent PDFs with ascii output if I used integers for the PDFs and just printed the last digit in the column representing the number of bet units. In these examples, I assume the bettor starts with 25 units. Column zero represents zero, so the bettor is tapped out.
In the first example, Convolution Test #1, I start with a population of 1 in column 26, P1 has N=1 at 0. I create the PDF1 which has two elements, N=1 at -1 (1,-1) and N=1 at +1 (1,1). Now, I convolve P1 @ P1 = P2. P2 has three elements (1,-2)(2,0)(1,2) where I am using a more compact (n,v) notation for the unnormalized PDF. If I had normalized P2, then 1/4th of bettors are at +2 and -2 units and 2/4ths are at 0 units. P3 needs to be normalized by a factor of 8, P4 by 16, etc. It take a lot of space to present floating point numbers, so I use the unnormalized number (modulo 10) in my output.
Round limit: 64 Convolve Pn with P1
Prob::size: 2 count: 2 min: -1 max: 1
N: 1 V: -1
N: 1 V: 1
1 0 EV: 0
1 1 1 EV: 0
1 2 1 2 EV: 0
1 3 3 1 3 EV: 0
1 4 6 4 1 4 EV: 0
1 5 0 0 5 1 5 EV: 0
1 6 5 0 5 6 1 6 EV: 0
1 7 1 5 5 1 7 1 7 EV: 0
1 8 8 6 0 6 8 8 1 8 EV: 0
1 9 6 4 6 6 4 6 9 1 9 EV: 0
1 0 5 0 0 2 0 0 5 0 1 10 EV: 0
1 1 5 5 0 2 2 0 5 5 1 1 11 EV: 0
1 2 6 0 5 2 4 2 5 0 6 2 1 12 EV: 0
1 3 8 6 5 7 6 6 7 5 6 8 3 1 13 EV: 0
1 4 1 4 1 2 3 2 3 2 1 4 1 4 1 14 EV: 0
1 5 5 5 5 3 5 5 5 5 3 5 5 5 5 1 15 EV: 0
1 6 0 0 0 8 8 0 0 0 8 8 0 0 0 6 1 16 EV: 0
1 7 6 0 0 8 6 8 0 0 8 6 8 0 0 6 7 1 17 EV: 0
1 8 3 6 0 8 4 4 8 0 8 4 4 8 0 6 3 8 1 18 EV: 0
1 9 1 9 6 8 2 8 2 8 8 2 8 2 8 6 9 1 9 1 19 EV: 0
1 0 0 0 5 4 0 0 0 0 6 0 0 0 0 4 5 0 0 0 1 20 EV: 0
1 1 0 0 5 9 4 0 0 0 6 6 0 0 0 4 9 5 0 0 1 1 21 EV: 0
1 2 1 0 5 4 3 4 0 0 6 2 6 0 0 4 3 4 5 0 1 2 1 22 EV: 0
1 3 3 1 5 9 7 7 4 0 6 8 8 6 0 4 7 7 9 5 1 3 3 1 23 EV: 0
1 4 6 4 6 4 6 4 1 4 6 4 6 4 6 4 1 4 6 4 6 4 6 4 1 24 EV: 0
1 5 0 0 0 0 0 0 5 5 0 0 0 0 0 0 5 5 0 0 0 0 0 0 5 1 25 EV: 0
6 5 0 0 0 0 0 5 0 5 0 0 0 0 0 5 0 5 0 0 0 0 0 5 6 1 26 EV: 0
7 1 5 0 0 0 0 5 5 5 5 0 0 0 0 5 5 5 5 0 0 0 0 5 1 7 1 27 EV: 0
8 6 5 0 0 0 5 0 0 0 5 0 0 0 5 0 0 0 5 0 0 0 5 6 8 8 1 28 EV: 0
6 4 1 5 0 0 5 5 0 0 5 5 0 0 5 5 0 0 5 5 0 0 5 1 4 6 9 1 29 EV: 0
0 5 6 5 0 5 0 5 0 5 0 5 0 5 0 5 0 5 0 5 0 5 6 5 0 5 0 1 30 EV: 0
5 5 1 1 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 1 1 5 5 5 1 1 31 EV: 0
0 6 2 6 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 6 2 6 0 0 6 2 1 32 EV: 0
0 6 8 8 6 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 6 8 8 6 0 6 8 3 1 33 EV: 0
6 4 6 4 6 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 6 4 6 4 6 6 4 1 4 1 34 EV: 0
2 0 0 0 0 6 0 0 0 0 0 0 0 0 0 0 0 0 0 0 6 0 0 0 0 2 0 5 5 5 1 35 EV: 0
2 0 0 0 6 6 0 0 0 0 0 0 0 0 0 0 0 0 0 6 6 0 0 0 2 2 5 0 0 6 1 36 EV: 0
4 2 0 0 6 2 6 0 0 0 0 0 0 0 0 0 0 0 0 6 2 6 0 0 2 4 7 5 0 6 7 1 37 EV: 0
6 2 0 6 8 8 6 0 0 0 0 0 0 0 0 0 0 0 6 8 8 6 0 2 6 1 2 5 6 3 8 1 38 EV: 0
7 8 2 6 4 6 4 6 0 0 0 0 0 0 0 0 0 0 6 4 6 4 6 2 8 7 3 7 1 9 1 9 1 39 EV: 0
5 0 8 0 0 0 0 6 0 0 0 0 0 0 0 0 0 6 0 0 0 0 8 0 5 0 0 8 0 0 0 0 1 40 EV: 0
5 5 8 8 0 0 0 6 6 0 0 0 0 0 0 0 0 6 6 0 0 0 8 8 5 5 0 8 8 0 0 0 1 41 EV: 0
0 3 6 8 0 0 6 2 6 0 0 0 0 0 0 0 6 2 6 0 0 8 6 3 0 5 8 6 8 0 0 1 2 42 EV: 0
5 3 9 4 8 0 6 8 8 6 0 0 0 0 0 0 6 8 8 6 0 8 4 9 3 5 3 4 4 8 0 1 3 43 EV: 0
8 2 3 2 8 6 4 6 4 6 0 0 0 0 0 6 4 6 4 6 8 2 3 2 8 8 7 8 2 8 1 4 6 44 EV: 0
6 0 5 5 0 4 0 0 0 0 6 0 0 0 0 6 0 0 0 0 4 0 5 5 0 6 5 5 0 0 9 5 0 45 EV: 0
6 5 0 5 4 4 0 0 0 6 6 0 0 0 6 6 0 0 0 4 4 5 0 5 6 1 0 5 0 9 4 5 0 46 EV: 0
7 1 5 5 9 8 4 0 0 6 2 6 0 0 6 2 6 0 0 4 8 9 5 5 1 7 1 5 5 9 3 9 5 47 EV: 0
8 6 0 4 7 2 4 0 6 8 8 6 0 6 8 8 6 0 4 2 7 4 0 6 8 8 6 0 4 2 2 4 0 48 EV: 0
6 4 6 4 1 9 6 4 6 4 6 4 6 6 4 6 4 6 4 6 9 1 4 6 4 6 4 6 4 6 4 6 4 49 EV: 0
0 0 0 5 0 5 0 0 0 0 0 0 2 0 0 0 0 0 0 5 0 5 0 0 0 0 0 0 0 0 0 0 0 50 EV: 0
0 0 0 5 5 5 5 0 0 0 0 0 2 2 0 0 0 0 0 5 5 5 5 0 0 0 0 0 0 0 0 0 0 51 EV: 0
0 0 5 0 0 0 5 0 0 0 0 2 4 2 0 0 0 0 5 0 0 0 5 0 0 0 0 0 0 0 0 0 0 52 EV: 0
0 0 5 5 0 0 5 5 0 0 0 2 6 6 2 0 0 0 5 5 0 0 5 5 0 0 0 0 0 0 0 0 0 53 EV: 0
0 5 0 5 0 5 0 5 0 0 2 8 2 8 2 0 0 5 0 5 0 5 0 5 0 0 0 0 0 0 0 0 0 54 EV: 0
0 5 5 5 5 5 5 5 5 0 2 0 0 0 0 2 0 5 5 5 5 5 5 5 5 0 0 0 0 0 0 0 0 55 EV: 0
5 0 0 0 0 0 0 0 5 2 2 0 0 0 2 2 5 0 0 0 0 0 0 0 5 0 0 0 0 0 0 0 5 56 EV: 0
5 5 0 0 0 0 0 0 5 7 4 2 0 0 2 4 7 5 0 0 0 0 0 0 5 5 0 0 0 0 0 0 5 57 EV: 0
0 5 0 0 0 0 0 5 2 1 6 2 0 2 6 1 2 5 0 0 0 0 0 5 0 5 0 0 0 0 0 5 0 58 EV: 0
5 5 5 0 0 0 0 5 7 3 7 8 2 2 8 7 3 7 5 0 0 0 0 5 5 5 5 0 0 0 0 5 5 59 EV: 0
0 0 5 0 0 0 5 2 0 0 5 0 4 0 5 0 0 2 5 0 0 0 5 0 0 0 5 0 0 0 5 0 6 60 EV: 0
0 0 5 5 0 0 5 7 2 0 5 5 4 4 5 5 0 2 7 5 0 0 5 5 0 0 5 5 0 0 5 5 6 61 EV: 0
0 5 0 5 0 5 2 9 2 5 0 9 8 9 0 5 2 9 2 5 0 5 0 5 0 5 0 5 0 5 0 1 2 62 EV: 0
5 5 5 5 5 5 7 1 1 7 5 9 7 7 9 5 7 1 1 7 5 5 5 5 5 5 5 5 5 5 5 1 3 63 EV: 0
0 0 0 0 0 2 8 2 8 2 4 6 4 6 4 2 8 2 8 2 0 0 0 0 0 0 0 0 0 0 6 4 6 64 EV: nan
If you click the button above, you will see my program output. Each successive PDF is obtained by convolution Pn @ P1 = P(n+1). Note that the first time that a 1 appears in column 0 is in P25. It is impossible to lose 25 units before round 25 if you are only risking one unit on each round. I also calculate the EV of the PDF as another sanity check. The EV remains zero (relative to the starting bankroll) for all Pn.
In the second test below, I convolve P1 @ P1 = P2, then P2 @ P2 = P4, P4 @ P4 = P8,
Pn @ Pn = P(2n), etc. I get to P64 in just six convolution operations.
Round limit: 64 Convolve Pn with Pn
Prob::size: 2 count: 2 min: -1 max: 1
N: 1 V: -1
N: 1 V: 1
1 0 EV: 0
1 1 1 EV: 0
1 2 1 2 EV: 0
1 4 6 4 1 4 EV: 0
1 8 8 6 0 6 8 8 1 8 EV: 0
1 6 0 0 0 8 8 0 0 0 8 8 0 0 0 6 1 16 EV: 0
0 6 2 6 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 6 2 6 0 0 6 2 1 32 EV: 0
0 0 0 0 0 2 8 2 8 2 4 6 4 6 4 2 8 2 8 2 0 0 0 0 0 0 0 0 0 0 6 4 6 64 EV: nan
I am skipping past many PDFs, but if I actually needed P38, I could use P32 @ P4 @ P2 = P38 to get it quickly.
In the third test below, I am using a more complicated P1 with a count of 5 elements. This is meant to be an extremely simplified video poker PDF with a max payoff of 6:1. The P1 is asymmetrical, but the EV is zero. Again, it takes 25 rounds before there is a chance for the player to tap out. The normalization factor for P1 is 13, for P2 is 139, etc.
Round limit: 64 Convolve Pn with P1
Prob::size: 5 count: 5 min: -1 max: 6
N: 9 V: -1
N: 1 V: 0
N: 1 V: 1
N: 1 V: 2
N: 1 V: 6
1 0 EV: 0
9111 1 1 EV: 0
18903218222 1 2 EV: 0
930840497809637333 1 3 EV: 0
1624728892201600808266444 1 4 EV: 0
95555150551055560005000000005555 1 5 EV: 0
149404606046265412600010005050505054666 1 6 EV: 0
9760792181642295427141323755010005013403213777 7 EV: 0
1202644616488206328480805884828480044084044280468 8 EV: 0
99318489551942451117800953952669486226462880220660 9 EV: 0
105058505090500050503000525050600008005020000200002 10 EV: 0
9166028985692950540528385825209681078435370203242082 11 EV: 0
18403000262006444286642088421260540400280426328448089 12 EV: 0
935397346063862862286086008477971116002946409119402791 13 EV: 0
1674206418788494007028446660505624245614801414863818183 14 EV: 0
95005305500055585055900005005540550950007550035550050009 15 EV: 0
144402828000800238806424000400649406484082620280300080064 16 EV: 0
9715268982484604975700018442862215176885800880689753468526 17 EV: 0
12521256240868743038521800642852349838588206845456761232446 18 EV: 0
998680477227033126466301908549176240676178678511084027099203 19 EV: 0
1420706290223020584476863886422296881840522886445020500050006 20 EV: 0
93711558531813389578115673386463393153321756004373953378319046 21 EV: 0
387840648026287660902616403470085486823208207082788226980842526 22 EV: 0
9122772949662477311772191299015798326858938410535790409217621631 23 EV: 0
70200666722246264402604046048688464228888008464862482288146848821 24 EV: 0
779186617539284580662622088806802646800628280222404446865573848931 25 EV: 0
410341436325882468882520020624604624408266848206000866438589214185 26 EV: 0
444081250747906903487173624506842426240486004486466466914204836347 27 EV: 0
894886224882690605488840298624264966848428240844402829482546884666 28 EV: 0
373002456226137575900281915920657735606904486660604073557992228524 29 EV: 0
066781606709802666418981088744634365004600424124482725844647254409 30 EV: 0
653280535881578101558248949696532904748327267179287888118770489798 31 EV: 0
248600282202040220886222434820246260660806028824884684020582462608 32 EV: 0
444848482486840860844428959906038226286806040440226064689393642126 33 EV: 0
822487408286486688046207436103680880650824622220864224898767050426 34 EV: 0
450999790269888480866493884467362749195708058662284862574648231023 35 EV: 0
254204824624006489866948432629888126646484208226610269282124410643 36 EV: 0
331006218084640675135158379097507112282984220024933719705158111015 37 EV: 0
074524842908234169642464840427882549880823860703658800440262894263 38 EV: 0
594279435097110186164169222697355527954158515765867289472068111313 39 EV: 0
614666022702282001200846832442820966808682600244694488000946842209 40 EV: 0
973902213751020979192407597504815797646704228268155362019179680597 41 EV: 0
034320634147022143810041498986692121480642426345414727852521804765 42 EV: 0
838092384502189005863432496016386726566985421986088925472921547641 43 EV: 0
608840668180404025242884850848226720216686640168004046284566082828 44 EV: 0
428684449997804775518223933964251977397424015359484348201575822322 45 EV: 0
288488418305234127212225236348234324476163876661468604694445290648 46 EV: 0
460728134608216909673032436418562331708564057636520647777577637747 47 EV: 0
028280068622200884206466284686442224022620608482206008066260648064 48 EV: 0
666820062884006840244666484084208826220242082800880626644468620622 49 EV: 0
042409884822244466866400048640284404826486264468626020264602084802 50 EV: 0
436793332601222008288446262462408220404240224866284202826848682662 51 EV: 0
220000686488466065684840460082882224068684004840468420646804822668 52 EV: 0
428924002622000239312687826268844008246642244028682660682024864620 53 EV: 0
824445406120284783658706602889868622682604882042842226020420020028 54 EV: 0
970716715116665220602152614173774267660626620262608624264488080026 55 EV: 0
478088224102660260004684412840408480800881628422286486862022648268 56 EV: 0
119360877971840766888686597142676800804291132807624448648866064400 57 EV: 0
672383478721604082644345816789640264078145852342420603240604204666 58 EV: 0
260429878741746145485566224389780123374600034776034155538063200688 59 EV: 0
202246604040636265424900026881022068056049806568440248260024000089 60 EV: 0
224768864200597757941112860593512243951595385192462528260426604031 61 EV: 0
674283828747654064466821882326038443456881646089086623280940426141 62 EV: 0
425874543743665841492217733576595017017152100874570858971378481042 63 EV: 0
468664468262868064048804490206884842062668086884226224422084282862 64 EV: 0
In the fourth test below, you can see that the convolution Pn @ Pn = P(2n) works just as well for an asymmetric PDF.
Round limit: 64 Convolve Pn with Pn
Prob::size: 5 count: 5 min: -1 max: 6
N: 9 V: -1
N: 1 V: 0
N: 1 V: 1
N: 1 V: 2
N: 1 V: 6
1 0 EV: 0
9111 1 1 EV: 0
18903218222 1 2 EV: 0
1624728892201600808266444 1 4 EV: 0
1202644616488206328480805884828480044084044280468 8 EV: 0
144402828000800238806424000400649406484082620280300080064 16 EV: 0
248600282202040220886222434820246260660806028824884684020582462608 32 EV: 0
468664468262868064048804490206884842062668086884226224422084282862 64 EV: 0
This is just a demo program using 64-bit unnormalized integers. My actual convolution program uses 64-bit floating point values.
Let's get to MBJ's problem. If you have this convolution program, you can quickly iterate until the round where players start tapping out. Then, you remove elements from the PDF where the player has tapped out and save them in another bucket. This bucket accumulates the session-tap-out-probability (STOP). This is what most people call risk-of-ruin (RoR). If you want to be very accurate, you have to start convolving by Pn @ P1. Otherwise you will miss some players whose bankroll went negative but recovered to a positive value before you got to the next PDF.
In Test #1 above, one player tapped out on round 25, so STOP = 1 / 2^25. In a coin flip, nobody can tap out in round 26, but it would seem that 7 players would tap out in round 27. This is not right because I have not removed the player who tapped out in round 25.
In my video poker PDF program, I also remove probability from the PDF for players who have hit mutiple Royals and are thousands of units to the good. If you are only concerned about calculating STOP, then these lucky players don't affect the calculation. As a result my PDF size does not grow indefinitely as we go to millions of rounds of video poker.
I am including a stripped down version of the program so you can see how simple the convolution process is. If you want to port this to another language, I recommend that you start by using integer instead of floating point number to be sure that you get the right result.
typedef unsigned long long u_ll;
// a couplet of (n,v)
class cpl {
public:
u_ll m_n;
int m_v;
};
// the coin flip P1 has size = 2, and two couplets (1,-1) and (1, 1)
class Prob {
cpl * cplPtr;
int size; // allocated size for cplPtr
int min;
int max;
int count; // current count of cplPtr used
}
// the convolution algorthm stripped of error checking and diagnostics
int Prob::convolve(Prob & A, Prob & B, u_ll *& array)
{
max = A.max + B.max;
min = A.min + B.min;
int range = 1 + max - min;
array = new u_ll[range];
for (int i = 0; i < range; i++) {
array = 0;
}
int rA = A.max - A.min;
int rB = B.max - B.min;
int zB = B.cplPtr[0].m_v;
for (int iB = 0; iB < B.count; iB++) {
int zA = A.cplPtr[0].m_v;
for (int iA = 0; iA < A.count; iA++) {
u_ll nA = A.cplPtr[iA].m_n;
u_ll nB = B.cplPtr[iB].m_n;
int vA = A.cplPtr[iA].m_v;
int vB = B.cplPtr[iB].m_v;
int ind = vA - zA + vB - zB;
array[ind] += nA * nB;
}
}
int cnt = 0;
for (int i = 0; i < range; i++) {
u_ll n = array;
if (!n) continue;
cnt++;
}
setSize(cnt);
cnt = 0;
for (int i = 0; i < range; i++) {
u_ll n = array;
if (!n) continue;
cnt++;
add(n, i+min);
}
return range;
}
I just did timing tests of this code out to P4096. It takes 21 msec on one processor. The Pn @ Pn method is 20 times faster than Pn @ P1 after 4096 rounds. The comparison is even more dramatic for really long sessions (millions of rounds). For video poker, I routinely ran PDFs out to 4 million hands on 1998 vintage hardware. MBJ may not need this precision for his RoR calculator, but it would not be that computationally expensive. I have never used any online RoR calculator. I don't know what limitations they have for number of rounds. The complexity of the P1 PDF barely matters because the Pn PDF quickly grows in size. Therefore, my method will handle VP PDFs with the usual 9-15 pay lines quite easily.
Also, note that this integer version overflows 64-bit integers before P64 even with the simple coin-flip PDF. To do any serious work, I use a different version where the couplet has a 64-bit FP value.
link to original post
February 28th, 2023 at 1:41:12 PM
permalink
I’m surprised that I’d never heard of mathematical convolution until now. I’d need to see a straightforward simple example of it being successfully applied in order to fully grasp it and possibly start using it.
I don’t really follow the above post
I don’t really follow the above post
It’s all about making that GTA
February 28th, 2023 at 3:00:26 PM
permalink
Quote: Ace2I’m surprised that I’d never heard of mathematical convolution until now. I’d need to see a straightforward simple example of it being successfully applied in order to fully grasp it and possibly start using it.
I don’t really follow the above post
link to original post
Discrete convolution is related to polynomial expansion which everyone has done at some level. The sequences "1 2 1" and "1 4 6 4 1" should ring a bell.
Here is a real simple example.
Fair roulette wheel betting on dozens.P1 = (2,-1)(1,+2) This means you lose 1 unit two times out of three and gain 2 units one time.
P0 -s (0,1) meaning all the population is at zero, that is, at the starting bankroll. To get the PDF after one spin, You multiply P1 by 2 and shift it by -1 (left by one unit). Then you multiply P1 by 1 and shift 2 (right). Add them up.
1 P0 EV: 0
2 1 P1 EV: 0
P0 is just the identity value. P0 @ Pn = Pn. Now lets do P1 @ P1
2 1
above P1 shifted right by 2
4 2
above P1 shifted left by 1 and multiplied by 2
4 4 1 P2 EV: 0
add the numbers in the column and you get P2 above.
Normalizing P2,
4/9ths of players will lose 2 units.
4/9ths of players will gain 1 units.
1/9ths of players will gain 4 units.
I hope you could get this same result doing the math in your head. P5 is harder to get right, and P64 takes a computer.
Here is the program output. Note that we are mod10, the '6' in P4 is really 16, etc.
Round limit: 4 Convolve Pn with P1
Prob::size: 2 count: 2 min: -1 max: 2
N: 2 V: -1
N: 1 V: 2
1 P0 EV: 0
2 1 P1 EV: 0
4 4 1 P2 EV: 0
8 2 6 1 P3 EV: 0
6 2 4 8 1 P4 EV: 0
Gambling is a math contest where the score is tracked in dollars. Try not to get a negative score.
February 28th, 2023 at 8:49:04 PM
permalink
Interesting thread and very nice illustration of how to approach the problem. Will go back and review long forgotten convolution theory. Here are a couple of sources that others may find useful:
1) The Algebra of Random Variables by M. D. Springer, 1979 Wiley. ISBN 0471014060. Prof. Dr. Springer mentored several doctoral students at Univ of Arkansas whose dissertations advanced convolution theory.
2) Probability Methods for Cost Uncertainty Analysis: A Systems Engineering Perspective by Paul R. Garvey, 1999, Marcel Dekker Inc,
I found 2) to a good starting point since it showed hands on examples of convolutions that were applied to engineering and business applications; 1) has a more theoretical treatment of convolutions. I used both in tandem often times with 2) allowing the light bulb to turn on when tackling sections of 1). The convolution dissertations that came out of Prof. Dr. Springer's students were challenging to read and centered on convolution theory using characteristic functions.
1) The Algebra of Random Variables by M. D. Springer, 1979 Wiley. ISBN 0471014060. Prof. Dr. Springer mentored several doctoral students at Univ of Arkansas whose dissertations advanced convolution theory.
2) Probability Methods for Cost Uncertainty Analysis: A Systems Engineering Perspective by Paul R. Garvey, 1999, Marcel Dekker Inc,
I found 2) to a good starting point since it showed hands on examples of convolutions that were applied to engineering and business applications; 1) has a more theoretical treatment of convolutions. I used both in tandem often times with 2) allowing the light bulb to turn on when tackling sections of 1). The convolution dissertations that came out of Prof. Dr. Springer's students were challenging to read and centered on convolution theory using characteristic functions.
I 'm gonna go get the papers, get the papers.
March 1st, 2023 at 3:01:10 AM
permalink
Quote: Jimmy2TimesInteresting thread and very nice illustration of how to approach the problem. Will go back and review long forgotten convolution theory. Here are a couple of sources that others may find useful:
1) The Algebra of Random Variables by M. D. Springer, 1979 Wiley. ISBN 0471014060. Prof. Dr. Springer mentored several doctoral students at Univ of Arkansas whose dissertations advanced convolution theory.
2) Probability Methods for Cost Uncertainty Analysis: A Systems Engineering Perspective by Paul R. Garvey, 1999, Marcel Dekker Inc,
I found 2) to a good starting point since it showed hands on examples of convolutions that were applied to engineering and business applications; 1) has a more theoretical treatment of convolutions. I used both in tandem often times with 2) allowing the light bulb to turn on when tackling sections of 1). The convolution dissertations that came out of Prof. Dr. Springer's students were challenging to read and centered on convolution theory using characteristic functions.
link to original post
Thanks. I have no formal training in convolution theory. I just figured it out in grad school when I had to come up with a program to do deconvolution on data sets.
If anyone wants to see the relationship to polynomial expansion, here is a Wiki reference:
https://en.wikipedia.org/wiki/Polynomial_expansion
The coefficients in their example For example, when expanding (x+y)^6 are the same as my P6 for a coin flip. This is not a coincidence. Since (x+y)^a * (x+y)^b = (x+y)^(a+b), it makes sense that Pa @ Pb = P(a+b). They are both commutative operations. If you have a gambling session of (a+b) rounds, it does not matter if you do a round first and b rounds second. The final PDF is the same (so long as you cannot tap out). The two sub-sessions can even be on a two different games with two different PDFs. Each session has an independent PDF, so they can be merged using convolution.
Gambling is a math contest where the score is tracked in dollars. Try not to get a negative score.
