[SOLVED] CS203B Assignment 2

1. Endsem allocation

You are allocated as the Tutor of CS203, with n students. Rajat has created 2 sets of Endsem papers to decrease cheating. He has asked you to help decide which paper should be given to whom. You scraped through the data on Hello, and found out who have been project partners in previous courses, as they will be friends now. Thus, you have found out m friendship connections among the students. You reported this to Rajat, and he said he is fine with any allocation that disrupts atleast half of the friendship connections. A friendship connection is disrupted if the students get different sets of papers.

• You are really busy, and just randomly allocated each student to set 1 or set 2. Show that theexpected value of disrupted friendship connections is.
• Getting expected value is not enough, you need to find a proper allocation. But you cannot goover all the 2ⁿ allocations as n ≈ 150. Using the construction for pairwise independence given in class, show that you can find an allocation with at least half of the friendship connections disrupted in poly(n)-time.

2. Estimating the number of tickets

You are given a bag full of N tickets numbered 1,…,N(N is unknown to you). You can take out tickets one at a time, note their label, and put them back in the bag. Your task is to estimate N. We will do this in the same way as we estimated π in lecture:

• Assume you drew out k What will be the expected value of the mean of these tickets ? Calculate N in terms of this mean, call this N˜.
• Chernoff bound can be extended to work on the case when the Random Variables take valuesother than {0,1}. This is known as Hoeffding’s inequality. Use it to find a lower bound on the probability that the error in N, using the above calculation, will be less than δN(δ < 1/2). (in terms of N,δ,k)
• Assume k,N are odd. In calculation of part (a), instead of using the value of mean, we use the median of the labels of tickets drawn. Prove a lower bound of 1 on the probability that the error in N using the median will be less than δN(δ < 1/2). (in terms of N,δ,k)

1

• Start with a random hidden value of N in range 10⁴ − 10⁶. Write a function that gives k values from [N] when queried with equal probability. Use these values to calculate N˜ as in part (a) and (c), and plot them with respect to increasing k ≤ 1000. Repeat this estimation for a total of 3 different N, and put the plots in the main answer file. Submit the code you used to generate these plots, along with a readme on how to execute the code, zipped together with the main answer file into a single .zip file.

3. (15+15 marks) Markov Chain

Consider a homogeneous regular Markov chain with state space S of size |S|, and transition matrix M. Suppose that M is symmetric and entry-wise positive.

• Show that all the eigenvalues of M are bounded by 1 and that the uniform distribution is the unique stationary probability distribution for M.
• Starting from the stationary distribution, express the probability of returning to the same stateas the state at t = 0 after n ∈ N steps in terms of the eigenvalues of M. Compute the limit of the above probability as n → ∞.

You might find the second part to be easier than the first. Feel free to assume the first part and finish the second part (even when you can’t prove the first part).

4. (Optional) DNF Counting

Given a DNF formula F of n variables, how can we estimate the number of satisfying assignments without considering all cases? A natural approach is to randomly sample m assignments uniformly from the set of all possible assignments. Let X be the number of satisfying assignments among the m samples.

• Derive an unbiased estimate for the total number of satisfying assignments in terms of X,m,n.
• Construct one DNF formula each for number of variables n for n = 6,8,10,12 having n clauses with each clause composed of subsets of n − 4 variables.
• Simulate the above algorithm on the constructed DNF formulas with m = 4n. Compare the estimate from the algorithm against the actual number satisfying assignments for each of the constructed formula. Plot the estimate and the number of satisfying assignments on the y-axis vs n on the x-axis..
• Explain qualitatively why the above scheme requires a large number of samples to produce accurateestimates.

2