Predicting epistasis from mathematical models

Classically, epistasis is either computed exactly by Walsh coefficients or estimated by sampling. Exact computation is usually of theoretical interest since the computation typically grows exponentially with the number of bits in the domain. Given an evaluation function, epistasis also can be estimated by sampling. However this approach gives us little insight into the origin of the epistasis and is prone to sampling error. This paper presents theorems establishing the bounds of epistasis for problems that can be stated as mathematical expressions. This leads to substantial computational savings for bounding the difficulty of a problem. Furthermore, working with these theorems in a mathematical context, one can gain insight into the mathematical origins of epistasis and how a problem's epistasis might be reduced. We present several new measures for epistasis and give empirical evidence and examples to demonstrate the application of the theorems. In particular, we show that some functions display "parity" such that by picking a well-defined representation, all Walsh coefficients of either odd or even index become zero, thereby reducing the nonlinearity of the function.