be more than one such guess by the pigeonhole principle.) Assuming that these algorithm runs are independent, the probability that more than n/2 of the guesses is correct is equal to the probability that the sum of independent Bernoulli random variables that are 1 with probability p is more than n/2. This can be shown to be at least via the multiplicative Chernoff bound (Corollary 13.3 in Sinclair's class notes, ).: Matrix Chernoff bound Rudolf Ahlswede and Andreas Winter introduced a Chernoff bound for matrix-valued random variables. The following version of the inequality can be found in the work of Tropp. Let be independent matrix valued random variables such that and . Let us denote by the operator norm of the matrix . If holds almost surely for all , then for every Notice that in order to conclude that the deviation from 0 is bounded by with high probability, we need to choose a number of samples proportional to the logarithm of . In general, unfortunately, a dependence on is inevitable: take for example a diagonal random sign matrix of dimension . The operator norm of the sum of t independent samples is precisely the maximum deviation among d independent random walks of length t. In order to achieve a fixed bound on the maximum deviation with constant probability, it is easy to see that t should grow logarithmically with d in this scenario. The following theorem can be obtained by assuming M has low rank, in order to avoid the dependency on the dimensions. Theorem without the dependency on the dimensions Let and M be a random symmetric real matrix with and almost surely. Assume that each element on the support of M has at most rank r. Set If holds almost surely, then where are i.i.d. copies of M. Sampling variant The following variant of Chernoff's bound can be used to bound the probability that a majority in a population will become a minority in a sample, or vice versa. Suppose there is a general population A and a sub-population B ⊆ A. Mark the relative size of the sub-population (|B|/|A|) by r. Suppose we pick an integer k and a random sample S ⊂ A of size k. Mark the relative size of the sub-population in the sample (|B∩S|/|S|) by rS. Then, for every fraction d ∈ [0,1]: In particular, if B is a majority in