o(1/2^k) doesn’t vary with n—are you saying that it doesn’t matter how big the input array is, the only determinant is the number of unknown bits, and the number of known bits is irrelevant? That would be quite interesting if so (though I have some question about how likely the function is to be truly random from an even distribution of such functions).
One can enumerate all such 3-bit functions (8 different inputs, each input can return 0 or 1, so 256 functions (one per output-bit-pattern of the 8 possible inputs). But this doesn’t seem to follow your formula—if you have 3 unknown bits, that should be 1⁄8 of a bit about the output, 2 for 1⁄4, and 1 unknown for 1⁄2 a bit about the output. But in fact, the distribution of functions includes both 0 and 1 output for every input pattern, so you actually have no predictive power for the output if you have ANY unknown bits.
o(1/2^k) doesn’t vary with n—are you saying that it doesn’t matter how big the input array is, the only determinant is the number of unknown bits, and the number of known bits is irrelevant?
Yes, that’s correct.
But in fact, the distribution of functions includes both 0 and 1 output for every input pattern, so you actually have no predictive power for the output if you have ANY unknown bits.
The claim is for almost all functions when the number of inputs is large. (Actually what we need is for 2^(# of unknown bits) to be large in order for the law of large numbers to kick in.) Even in the case of 3 unknown bits, we have 256 possible functions, and only 18 of those have less than 1⁄4 1′s or more than 3⁄4 1′s among their output bits.
o(1/2^k) doesn’t vary with n—are you saying that it doesn’t matter how big the input array is, the only determinant is the number of unknown bits, and the number of known bits is irrelevant? That would be quite interesting if so (though I have some question about how likely the function is to be truly random from an even distribution of such functions).
One can enumerate all such 3-bit functions (8 different inputs, each input can return 0 or 1, so 256 functions (one per output-bit-pattern of the 8 possible inputs). But this doesn’t seem to follow your formula—if you have 3 unknown bits, that should be 1⁄8 of a bit about the output, 2 for 1⁄4, and 1 unknown for 1⁄2 a bit about the output. But in fact, the distribution of functions includes both 0 and 1 output for every input pattern, so you actually have no predictive power for the output if you have ANY unknown bits.
Yes, that’s correct.
The claim is for almost all functions when the number of inputs is large. (Actually what we need is for 2^(# of unknown bits) to be large in order for the law of large numbers to kick in.) Even in the case of 3 unknown bits, we have 256 possible functions, and only 18 of those have less than 1⁄4 1′s or more than 3⁄4 1′s among their output bits.