(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,...
-
For a certain company, the cost function for producing x items is C(x)=30x+100 and the revenue function for selling x items is R(x)=0.5(x70)^2+2,450 . The maximum capacity of the company is 100...
-
What is escheatment and what are state laws and regulations on abandoned or unclaimed payroll funds?
-
From the following annual statements of Pioneer Ltd., calculate the following ratios: (a) Gross Profit Ratio; (b) Current Ratio; (c) Liquid Ratio; and Debt Equity Ratio. I. II. III. IV. V. VIII....
-
Yellow Corporation is subject to the book minimum tax. For the current year, its financial statement net income is \($2.5\) billion, and its taxable income is \($2.0\) billion. Net income reflects...
-
During the summer of 2002, the financial press reported that Citigroup was being investigated for allegations that it had arranged transactions for Enron so as to intentionally misrepresent the...
-
A wheel of 100 cm diameter, 1000 N weight is resting against a block of 25 cm height. Find minimum force P at angle 45 with horizontal when the wheel is just on the point of climbing the block. P...
-
Goldie and Kurt want advice from your financial advising firm. They have provided the following information. They graduated from university four years ago and they have good jobs, but neither of them...
-
What is the regionalization / localization strategy? How does it differ from globalization?
-
Refer to question 41 to find the power of a 10 % level test when the true population mean mileage is 36 miles per gallon. Question 41 An automobile manufacturer claims that a new car gets an average...
-
You are working for a consumer rights organization. You are interested in knowing whether the milk contained in 16-oz (1-pint) bottles really weighs 16 oz. You do not want to accuse the packer of...
-
The head accountant in a large corporation conducted a survey last year to study the proportion of incorrect invoices. Of the 2,000 invoices sampled, 25 were incorrect. To lower the proportion, he...
-
Management Discussion and Analysis Check out an online annual report of a selected financial institution and review the Management Discussion and Analysis (MD&A) section or Operating Review. 1....
-
Related party disclosures The following diagram shows the corporate structure of Alpha Corporation and three other companies. Alpha exercises control over both Betas and Deltas policy decisions since...
-
Acme Inc. just paid an annual dividend of 0.89. You expect Acme to make a big push into the Internet-of-Things (IoT) space during the next five years. As a result, you expect Acme/s dividend growth...
-
What is removed during each of the three stages of wastewater treatment: primary, secondary, and tertiary? During which state would you expect items to be recovered that were accidentally flushed,...
-
(a) For the situation of Example 1.2.20, enumerate the ordered samples that make up the unordered samples {4,4,12,12} and {2,9,9,12}. (b) Enumerate the ordered samples that make up the unordered...
-
As in Example 1.3.6, consider telegraph signals "dot" and "dash" sent in the proportion 3:4, where erratic transmissions cause a dot to become a dash with probability 1/4 and a dash to become a dot...
-
One very striking abuse of a levels is to choose them after seeing the data and to choose them in such a way as to force rejection (or acceptance) of a null hypothesis. To see what the true Type I...
-
You are told that a person has walked 750 m. What can you safely say about the persons final position relative to the starting point?
-
Can the displacement of a persons trip be zero, yet the distance involved in the trip is nonzero? How about the reverse situation? Explain.
-
An object traveling at a constant velocity vo experiences a constant acceleration in the same direction for a period of time t. Then an acceleration of equal magnitude is experienced in the opposite...
Study smarter with the SolutionInn App