Resolution dependence of the maximal information coefficient for noiseless relationship

Reshef et al. (Science 334:1518–1523, 2011) introduce the maximal information coefficient, or MIC, which captures a wide range of relationships between pairs of variables. We derive a useful property which can be employed either to substantially reduce the computer time to determine MIC, or to obtain a series of MIC values for different resolutions. Through studying the dependence of the MIC scores on the maximal resolution, employed to partition the data, we show that relationships of different natures can be discerned more clearly. We also provide an iterative greedy algorithm, as an alternative to the ApproxMaxMI proposed by Reshef et al., to determine the value of MIC through iterative optimization, which can be conducted parallelly.