Question: I need help with task 3 please! I have attached a picture. Thank you so much. Task 3 - Random strings [12 pts] Consider n-bit
I need help with task 3 please! I have attached a picture. Thank you so much.

Task 3 - Random strings [12 pts] Consider n-bit binary strings {0, 1)" and the following notations and functions w.r.t. them. - For every string s, s[i] for ie [n] denotes the i'th bit of s. - The hamming weight of a string s, denoted by HW(s), is the number of I's in s, that is, HW(s) = Ii s[i]. - The xor of two strings s] @s2 = s is the bit-wise xor of $1, $2, that is, for every i e [n], s = $1s2[;]. - The xor of k strings s = $1 0$2 0. . . Ost = (((s] (@s2) @s;) . .. ) (st. Equivalently, s[i] = 1 iff an odd number of s1 . . . s* are l's. Consider a random experiment where n strings X1, ..., Xi, ... . Xn are sampled uniformly and indepen dently from {0, 1}". Let Zij = XOX; for i, je [n]. a) [5 pts] Prove that Z1,2 = X1 @ X, and Z23 = X2 @ X's are independent. Recall that two random variables A. B are independent if for every a in the range of A and every b in the range of B, it holds that P (A = a, B = b) = P(A = a) P(B = b). b) [3 pts] Let H = Sisisign HW(Zi;). Compute the expectation of H. c) [4 pts] Prove the following: P( H - E(H )| >n) <
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
