Calculation and Proof for The Influence of Variables on Boolean Functions
# Calculation and Proof for The Influence of Variables on Boolean Functions
During last week's post, we investigated different Boolean functions and approximated their total influence using Python scripts. Today we will be confirming these results by calculating the influence of these functions using a mathematical approach.
My approach is to separate potentially influential bits, divide them into different cases and calculate each event's probability then add them up. I am certain that there should be other ways to calculate the total influence but for me this is the most intuitive approach.
# Boolean Functions Example 1: Randomly Generate
A random Boolean functions utilize a computer program to generate a random output for each inputs. To see an example, please refer to the previous post.
Theorem 1: If
We will calculate the influence of an individual bit first. Since all outputs are random, once we flip the bit, the chances of us getting a different output would be
Thus individual influence would be
which is equivalent to
Since each individual event is independent,
And we obtain the individual influence
Now since each bit in a random Boolean function have the same influence on our outcome, their individual influence are equal. Thus, we can express the total influence for a random Boolean function as
# Boolean Functions Example 2: Is everything equal to one?
This is a function where the output will be 0 unless all input bits are 1, the previous post provided examples as well.
Theorem 2: If
Example 2 is a bit more complicated so let us divide the calculation into cases:
- We have "0" in the ith bit and "1" everywhere else. If we flipped the "0", the output turns from 0 to 1 since all input becomes 1.
- We have 1 for every bit of the input, and we flip any ith bit, the output turns from 1 to 0.
Thus individual influence would be
Due to properties of individual events we have
Thus we obtain the individual influence
Now since each bit in this Boolean function have the same influence on our outcome, their individual influence are equal. Thus, we can express the total influence for such functions as
# Boolean Functions Example 3: Even or Odd?
Now we will investigate the Boolean function that add up all entries in mod 2. Essentially this is equivalent to identifying whether the sum is even or odd. Two examples are written in the [previous post]
Theorem 3: If
This Boolean function is a bit special due to the fact that no matter which bit we changed, it will affect the output regardless. The reason is that by changing one bit, the sum of our input either increase or decrease by 1. Therefore, an even sum will be odd and an odd sum will be even. Thus the output will turn from 1 to 0 or 0 to 1.
By this argument, the probability of the outcome being affected by a flipped bit is 100%. Therefore, we can conclude that
# Boolean Functions Example 4: Are the majority of the inputs one?
For this example, if majority of the input is 1, the output would be 1. Otherwise the output would be 0, including the case where the number of 1s and 0s are equal. Examples are shown in the previous post:
Theorem 4: If
We can use Stirling's approximation to simplify our result. That is, we use the approximation
Thus we obtain when n is odd,
We would like to divide the calculation into two cases based on the Boolean function's dimension's parity (even or odd). Nevertheless, before that we would like to clarify some notations that will come up below:
# Case 1: Odd dimension
When n is odd, we have two cases where the outcome could be affected:
Due to properties of independent event:
It is interesting to note that case 1 and case 2 are symmetric with equal properties. Moreover, besides the ith digit that is flipped, the rest of the input has an even length and equal number of 0 and 1, thus:
To measure the probaility that there exists
After simplifying, we obtain
Therefore the total influence
# Case 2: Even dimension
Due to properties of independent event,
Notice that in case 1, after isolating the flipped bits "0", we have one more "1" than "0". In case 2, after isolating the flipped bits(1), we have one more "1" than "0". Again, these two cases are symmetric. In both of these cases,
Since the flipped bit is chosen at this point, all other "1" exists in the string with length
Hence the total influence
Notice that if we plug in two consecutives
Now we have calculated and confirmed the accuracy of our plot from the last post. One interesting property of influence is that there is no particular formula to apply during calculation. My approach is solely based on dividing and conquering cases then apply fundamental probability theories. Boolean functions have been widely used in fields like computer science, cryptography and logic. We will definitely discuss more on this topic in some future posts.