javascriptalgorithmloopsbonferroni

Avoid multiple loops in JS implementation of Bonferroni inequality


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


Solution

  • 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