随机算法 (Spring 2014)/Problem Set 2
(Due to D.R. Karger and R. Motwani.)
- Let be two disjoint subsets of a universe such that . Suppose we select a random set by independently sampling each element of with probability . We say that the random sample is good if the following two conditions hold: and . Show that for , the probability that is good is larger than some positive constant.
- Suppose now that the random set is chosen by sampling the elements of with only pairwise independence. Show that for a suitable choice of the value of , the probability that is good is larger than some positive constant.
- Generalize the LazySelect algorithm for the -selection problem: Given as input an array of distinct numbers and an integer , find the th smallest number in the array.
- Use the Chernoff bounds instead of Chebyshev's inequality in the analysis of the LazySelect Algorithm and try to use as few random samples as possible.
A boolean code is a mapping . Each is called a message and is called a codeword. The code rate of a code is . A boolean code is a linear code if it is a linear transformation, i.e. there is a matrix such that for any , where the additions and multiplications are defined over the finite field of order two, .
The distance between two codeword and , denoted by , is defined as the Hamming distance between them. Formally, . The distance of a code is the minimum distance between any two codewords. Formally, .
Usually we want to make both the code rate and the code distance as large as possible, because a larger rate means that the amount of actual message per transmitted bit is high, and a larger distance allows for more error correction and detection.
- Use the probabilistic method to prove that there exists a boolean code of code rate and distance . Try to optimize the constant in .
- Prove a similar result for linear boolean codes.
Let be independent geometrically distributed random variables each having expectation 2 (each of the is an independent experiment counting the number of tosses of an unbiased coin up to and including the first HEADS). Let and be a positive real constant. Derive the best upper bound you can on .