随机算法 (Spring 2014)/Problem Set 2

From EtoneWiki
Jump to: navigation, search

Problem 1

(Due to D.R. Karger and R. Motwani.)

  1. 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.
  2. 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.

Problem 2

  1. 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.
  2. 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.

Problem 3

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.

Problem 4

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 .