(Typical sets) Let X, X2,..., Xn be i.i.d. Bernoulli(p) random variables. Let p(x), x = 0,...
Fantastic news! We've Found the answer you've been seeking!
Question:
Transcribed Image Text:
(Typical sets) Let X₁, X2,..., Xn be i.i.d. Bernoulli(p) random variables. Let p(x), x = 0, 1 be the pmf of X. Consider the typical set, An (€) := { x† : | - = log₂,(P(17†)) — H₂(p)| ≤e}. n (a) Show that for any fixed € > 0 and large enough n, P((X₁, X2, ..., Xn) € An (€)) ≥ (1 − €). (b) Let h₂(p) = -plog₂ p- (1-p) log2 (1-p). Show that for any (x1,...,xn) € An (€), 2-nh2(p)-ne ≤ P((X₁, ..., Xn) = (x₁,...,xn)) ≤ 2-nh₂(p)+ne Thus, all typical set sequences have approximately the same probability of 2-nh2(p). (c) Show that the number of typical sequences An(e)| satisfies the following inequality, (1 - €)2nh2(p)-ne ≤ |An(€)| ≤ 2nh2(p)+ne Thus about 2nh2(p) typical sequences are there and they require nh₂ (p) bits for representation. (Hint: use the Union bound.) (Typical sets) Let X₁, X2,..., Xn be i.i.d. Bernoulli(p) random variables. Let p(x), x = 0, 1 be the pmf of X. Consider the typical set, An (€) := { x† : | - = log₂,(P(17†)) — H₂(p)| ≤e}. n (a) Show that for any fixed € > 0 and large enough n, P((X₁, X2, ..., Xn) € An (€)) ≥ (1 − €). (b) Let h₂(p) = -plog₂ p- (1-p) log2 (1-p). Show that for any (x1,...,xn) € An (€), 2-nh2(p)-ne ≤ P((X₁, ..., Xn) = (x₁,...,xn)) ≤ 2-nh₂(p)+ne Thus, all typical set sequences have approximately the same probability of 2-nh2(p). (c) Show that the number of typical sequences An(e)| satisfies the following inequality, (1 - €)2nh2(p)-ne ≤ |An(€)| ≤ 2nh2(p)+ne Thus about 2nh2(p) typical sequences are there and they require nh₂ (p) bits for representation. (Hint: use the Union bound.)
Expert Answer:
Related Book For
Posted Date:
Students also viewed these electrical engineering questions
-
Show that for any continuous odd function f defined on the interval [a, a], we have f(x) dx = 0.
-
Show that for any continuous even function f defined on the interval [a, a], we have jaa f (x) dx =
-
Show that for any electromagnetic potentials (ɸ,A) there are many possible choices of gauge-transformed potentials such that the Lorentz condition (D.11) is satisfied. af =+ t A = Vf,...
-
Assume that a security is selling at INR 217 and American call and American put options are available on the stock with 3 months maturity and an exercise price of INR 210. The call is selling at INR...
-
Within payroll reporting compliance what information should be reported and how often? What information should be posted for employees?
-
Important ratios of a firm for the year 2015 are given below: The firm expects an increase of 50% in sales in the ensuing year. Estimate the working capital requirement of the firm for the ensuing...
-
Badger Corporation is subject to the book minimum tax. The following information pertains to Badger for Years 1 and 2: a. What is Badgers book minimum tax for Year 1? b. What is Badgers book minimum...
-
Pas and Sal Corporations' balance sheets at December 31, 2010, are summarized as follows (in thousands): Pas acquired 80 percent of the voting stock of Sal on January 2, 2011, at a cost of $320,000....
-
Program for Calculate Compound Interest when principal, rate and number of periods are given.
-
Bryant Corporation was incorporated on December 1, 2009, and began operations one week later. Before closing the books for the fiscal year ended November 30, 2010, Bryants controller prepared the...
-
General purpose money is used for most transactions in our society. How is the act of purchasing an object with money different from trading or gift-giving in terms of the social and personal...
-
The IRS is interested in knowing whether people who have an accountant prepare their tax returns have fewer errors than people who prepare their own returns. A random sample of 500 people who had...
-
If the professor wants to raise the standard for passing the test to nine or more correct answers, what is the probability of a Type I error? Use the following information to answer question. A...
-
Assume that we know that for the period 19262010 the yield component for common stocks was 3.99 percent and that the cumulative wealth index was $2,420.46. The cumulative wealth index value for the...
-
A questionnaire was sent to 500 of a dry cleaners customers to solicit their opinions about service received. Twenty-three customers were found to be unhappy with the service. On this evidence, can...
-
You are working for a VCR manufacturer. There are three shifts in the plant: morning shift, evening shift, and midnight shift. The manager suspects that the midnight shifts productivity is lower than...
-
Find all the first order partial derivatives for the following function. (2) f(x, y) = In
-
How do network effects help Facebook fend off smaller social-networking rivals? Could an online retailer doing half as much business compete on an equal footing with Amazon in terms of costs? Explain.
-
Establish the Lagrange Identity, that for any numbers a1, a2,..., an and b1,b2,..., bn, Use the identity to show that the correlation coefficient is equal to 1 if and only if all of the sample points...
-
Show that if (0) is an unbiased level acceptance region of a test of H0: = 0 versus H1: 0 and C(x) is the 1 - confidence set formed by inverting the acceptance regions, then C(x) is an unbiased...
-
Efron (1982) analyzes data on law school admission, with the object being to examine the correlation between the LSAT (Law School Admission Test) score and the first-year GPA (grade point average)....
-
1. Describe the bases of power held by Dr. Jamie Thompson. Describe the bases of power held by Dr. Elizabeth Clarke. 2. What activities and people have contributed to Jaime Thompsons power? What...
-
What is the current in the wire in Figure Q22.1? 1.0 VR + 1.0-1.0V + FIGURE Q22.1
-
Electroconvulsive therapy is a last-line treatment for certain mental disorders. In this treatment, an electric current is passed directly through the brain, inducing seizures. The total charge that...
Study smarter with the SolutionInn App