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

## Contents

## Problem 1

(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.

## Problem 2

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

## 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 .