# Calculation and Proof for The Influence of Variables on Boolean Functions

*Brian Li*

*2020-05-13*

*MAT388 Boolean Function Mathematics*

## # 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

#### # Proof

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

#### # Proof

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

#### # Justification

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,

#### # Justification

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:

To measure the probaility that there exists

After simplifying, we obtain

Therefore the total influence

#### # Case 2: Even dimension

When

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.