2024年5月7日

CS代写｜CSCI 1550 / 2540 Homework 3

Problem 3 (20 points)

Let f(X1, X2, . . . , Xn) satisfy the Lipschitz condition so x1,…,xn and yi,

values

We set and

Z0 = E(f(X1,…,Xn))
Zi = E(f(X1,…,Xn) | X1,…,Xi).

that,
|f (x1 , . . . , xi−1 , xi , xi+1 , . . . , xn ) − f (x1 , . . . , xi−1 , yi , xi+1 , . . . , xn )| ≤ c.

Give an example to show that, if the Xi are not independent, then it is possible that |Zi − Zi−1| > c for some i.

Problem 4 (20 points)

Consider a bin with N > 1 balls. The balls are either black or white. Let X0 = Nm < 1 be the fraction of black balls in the bin at time 0. Let Xi be the fraction of black balls at time i. At step i ≥ 1 one ball, chosen uniformly at random, is replace with a new ball. With probability Xi the new ball is black, otherwise it is white. All random choices are independent.

Consider the stopping time τ := infi{Xi ∈ {0, 1}}. That is, the process stops when all balls have the same color.

(a) Show that X1, X2, . . . is a martingale with respect to itself. (b) Show that E[τ] < ∞.

Hint: Show that at any step there is probability ≥ ( 1 )N/2 to terminate in the next

N/2 steps. Conclude that E[τ] ≤ (2N)N/2 + N/2. (c) Calculate P(Xτ = 1)

2N

Problem 5 (20 points)

Consider the range space ([0, 1], R), where R is the collection of unions of two closed intervals in [0, 1]. I.e.

R={[x,y]∪[v,w]|[x,y], [v,w]⊆[0,1]}. Assume a distribution D that is uniform on [0, 1].

  1. What is the VC-dimension of ([0, 1], R)?
  2. Construct an ε-net for ([0, 1], R).
  3. Construct an ε-sample for ([0, 1], R). For convenience, you may assume that ε = n1 for a positive integer n.
  4. Compare the asymptotic sizes of your constructions in (2) and (3) to the bounds for ran- dom sample sizes proven using the VC- dimension. Your constructions should require no more elements than these bounds (up to constant factors).