I was trying to implement the "Bonferroni inequality" which models the probability of the union of many independent events for a data science use case on GCP BigQuery using a Javascript UDF. However I'm quite unfamiliar with JS and have no clue of the good practices.
The formula to apply is the following:
P(U Ai) = SUM(P(Ai)) - SUM(P(Ai)*P(Aj)) + SUM(P(Ai)*P(Aj)*P(Ak) - ... i != j != k
My input for this function is an array of the single event probabilities:
[P(A1), P(A2), P(A3), ...]
I instinctively made "for loops" in rows to get the result however, it hurts to see a code this ugly so was wondering if any of you had an idea on how to achieve it in a more elegant and optimized way?
Here is the function I wrote for a level 4 Bonferroni inequality :
function unionBoundProbability(probList){
var intersection2 = 0;
var intersection3 = 0;
var intersection4 = 0;
var i = 0;
var j = 0;
var k = 0;
var l = 0;
var sum = 0;
var product = 1;
var sum = probList.reduce((a, b) => a + b, 0);
for(i = 0; i < probList.length; i++){
product *= probList[i];
for(j = i+1; j < probList.length; j++){
intersection2 += probList[i]*probList[j];
for(k = j+1; k < probList.length; k++){
intersection3 += probList[i]*probList[j]*probList[k];
for(l = k+1; l < probList.length; l++){
intersection4 += probList[i]*probList[j]*probList[k]*probList[l];
}
}
}
}
switch (probList.length) {
case 0:
return 0;
break;
case 1:
return probList[0];
break;
case 2:
return sum - product;
break;
case 3:
return sum - intersection2 + product;
break
case 4:
return sum - intersection2 + intersection3 - product;
case 5 :
return sum - intersection2 + intersection3 - intersection4 + product;
default:
return Math.max((sum - intersection2 + intersection3 - intersection4), Math.max.apply(Math, probList));
}
}
What I am trying to do is to calculate an approximation of the probability of the union of all the probabilities passed as the input.
If I have less than 5 probabilities, then the switch statement applies the exact formula. Otherwise, the default case applies the Bonferroni approximation, (As I'm modeling the chance of a signal to be received, if the estimation is less than the probability with the best antenna then I keep the best antenna).
Thank you for your help
This example follows the below equation from https://www.probabilitycourse.com/chapter6/6_2_1_union_bound_and_exten.php
P(⋃(i=1 => n)Ai)=∑(i=1 => n) P(Ai) − ∑(i<j) P(Ai ∩ Aj) + ∑(i<j<k) P(Ai ∩ Aj ∩ Ak) − ... +(−1)^n−1 P(⋂(i=1 => n) Ai)
I don't know the reason why you included factorials in the example you gave, but I didn't include factorials as they are not there in the above equation.
// Recursive function to update sums of each level
function updateSums(sums, probList, maxLevel, currentLevel = 1, currentProduct = 1, lastIndex = -1) {
// Example case: maxLevel = 4, curentLevel = 3, path = { 1: 0, 2: 1 }, currentProduct = probList[0] * probList[1]
// Loops through all entries except 0 and 1 and adds the products to sums[2], for each entry also calculates level 4 sums
for (let i = lastIndex + 1; i < probList.length; i++) {
const nextProduct = currentProduct * probList[i];
sums[currentLevel - 1] += nextProduct;
if (currentLevel < maxLevel) {
// get the next level product sums for current product
updateSums(sums, probList, maxLevel, currentLevel + 1, nextProduct, i);
}
}
}
// Main function
function inequality(probList) {
probList = probList.sort((a, b) => b - a).slice(0, 4);
// Calculate maxLevel
const maxLevel = probList.length;
if (!maxLevel) return 0;
// create am array of sums, each entry represents 1 level
const sums = (new Array(maxLevel)).fill(0);
updateSums(sums, probList, maxLevel);
return sums.reduce((a, c, i) => {
return a + ((i % 2) ? -1 : 1) * c;
}, 0);
}
console.log(inequality(probList));
PS: This is written in ES6