1. Random sets
Suppose we are given a set of size S, and generate two subsets A and B by including each element of S in A with independent probability p and in B with independent probability q.
- What is the probability that A⊆B?
- What are the expected sizes of A, B, A∩B, and A∪B?
For A⊆B to hold, it must be the case x∈A ⇒ x∈B for all x∈S. Let's compute the probability that this condition fails for some fixed x: we need x∈A but x∉B. Since these events are independent, they occur with probability p(1-q). So the probability that the condition holds for x is (1-p(1-q)), and the probability that it holds for all x is (1-p(1-q))n.
Linearity of expectation is our friend here; given a target set T, we let Xx be the indicator variable for the event that x∈T. Then E[|T|] = ∑x∈S E[Xx] = ∑x∈S Pr[x∈T] = n Pr[x∈T] if the probability is the same for all x. Thus we have:
- For A, Pr[x∈A] = p ⇒ E[|A|] = pn.
- For B, Pr[x∈B] = q ⇒ E[|B|] = qn.
- For A∩B, Pr[x∈A∩B] = pq ⇒ E[|A∩B|] = pqn.
- For A∪B, Pr[x∈A∪B] = 1-(1-p)(1-q) = p+q-pq ⇒ E[|A∪B|] = n(p+q-pq).
- Let T(n) = 1 + T(n-X), where X = 0 with probability p and ⌈n/2⌉ with probability q = 1-p. Give the best upper bound you can on E[T(n)].
Let T(n) = n2 + T(n-X), where X is a uniformly distributed integer-valued random variable in the range 1..n. Give the best upper bound you can on E[T(n)].
- Let T(n) = 1 + T(n-X), where the distribution of X depends on n and E[X] = μ(n), where μ satisfies the conditions of the Karp-Upfal-Wigderson bound. Give an example of a family of processes for which the K-U-W bound on E[T(n)] for some n is an arbitrarily large multiple of the actual value of E[T(n)].
- We can try doing this either with KUW or by attacking it directly.
- KUW bound
EX = q⌈n/2⌉, a non-decreasing function in n, so E[T(n)] ≤ ≤ = (2/q) H(⌈n/2⌉) ≤ (2/q) ln n.
- Direct bound
- Here we observe that at each value we reach, we wait an expect (1/q) rounds before dropping to the next value. It takes ⌈lg n⌉+1 drops to get to 0, so the total expected time is exactly (1/q)(⌈lg n⌉ + 1). The constants here are slightly better than the KUW bound, but otherwise both are asymptotically Θ((1/q) log n).
Here we guess that an2 works for some constant a, since this is what we'd expect if we were solving the recurrence with X = n/2. So let's check the guess against the actual recurrence. For n = 0, we get T(n) = 0 = an2. For larger n, assume that E[T(m)] ≤ am2 for m<n and check E[T(n)] = E[n2+T(n-X)] = ≤ = n2 + (a/n)(n3/3) = (1+a/3)n2 ≤ an2 provided (1+a/3)≤a. This holds when a≥3/2, so we get E[T(n)] ≤ (3/2)n2.
Let's just look at a process with three states, corresponding to n=2, 1, 0. From n=2, suppose we drop to 0 with probability 1; from n=1, we drop to 0 with probability p and otherwise stay put. Now we have E[X1] = p and E[X2] = 2, so we can let μ(n) = p for 0≤n≤1 and 2 for 1<n≤2. The KUW bound on E[T(2)] is then 1/p+1/2. But the actual value of E[T(2)] is 1, so by letting p→0 we can make the KUW bound arbitrarily worse than the real value.
3. Random hitting sets
In the hitting set problem, one is given a collection of subsets A1,A2...Ak of a set S of n elements, and the goal is to find as small a set B as possible such that Ai∩B≠∅ for all i.
Suppose that |Ai| = m for all i, and that we choose B by including each element of S with independent probability c/m. As a function of n, k, and m, how large does c need to be so that you can show there is at least a constant probability that B∩Ai≠∅ for all i?
You may find it helpful to use the fact that 1+x ≤ ex for all x.
We'll start by computing Pr[B∩Ai=∅] for any specific Ai. This is just the probability that none of the m elements of Ai are chosen, or (1-c/m)m ≤ exp(-c/m)m = exp(-c). Applying the union bound gives a bound on the probability than any Ai is missed of k(1-c/m)m ≤ ke-c. Letting ke-c = ε and solving for c gives c = ln(k/ε).