Let be a matrix, with entries chosen independently at random. Every entry is chosen to be 0 or 1, each with probability . Find the expected value of (as a function of ), where is the transpose of .
Solution
The expected value equals Write the determinant of as the sum over permutations of of the product then the expected value of the determinant is the sum over of the expected value of this product, which we denote by . Note that if we partition into orbits for the action of , then partition the factors of the product accordingly, then no entry of appears in more than one of these factors; consequently, these factors are independent random variables. This means that we can compute as the product of the expected values of the individual factors. It is obvious that any orbit of size 1 gives rise to the zero product, and hence the expected value of the corresponding factor is zero. For an orbit of size , the corresponding factor contains distinct matrix entries, so again we may compute the expected value of the factor as the product of the expected values of the individual terms . However, the distribution of this term is symmetric about 0, so its expected value is 0. We conclude that unless acts with orbits of size 2. To compute in this case, assume without loss of generality that the orbits of are ; note that . Then is the expected value of , which is times the -th power of the expected value of . Since takes the values with probabilities , its square takes the values with probabilities ; we conclude that The permutations of this form correspond to unordered partitions of into sets of size 2, so there are such permutations. Putting this all together yields the claimed result.