### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# Class Note for CMPSCI 711 at UMass(2)

### View Full Document

## 17

## 0

## Popular in Course

## Popular in Department

This 53 page Class Notes was uploaded by an elite notetaker on Friday February 6, 2015. The Class Notes belongs to a course at University of Massachusetts taught by a professor in Fall. Since its upload, it has received 17 views.

## Similar to Course at UMass

## Popular in Subject

## Reviews for Class Note for CMPSCI 711 at UMass(2)

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 02/06/15

CMPSCI 711 Really Advanced Algorithms Lecture 17 amp 18 Entropy Randomness and Information Andrew McGregor Last Compned mm 9 2009 Definitions Entropy and Binomial Coefficients Extracting Random Bits Pairwise Independent Functions Outline Definitions Entropy Definition Given a discrete random variable X the entropy of X is HX 7ZPXXIoglPXx Given two discrete random variables X7 Y the conditional entropy ofX given Y is HXlY ZylPYyHXlYy Entropy Definition Given a discrete random variable X the entropy of X is HX izmx x oglPX x X Given two discrete random variables X7 Y the conditional entropy ofX given Y is HXlY ZleY y HXlY y Lemma For function g HgXlX 0 HXlgX O iffg invertible Entropy Definition Given a discrete random variable X the entropy of X is HX izmx x oglPX x X Given two discrete random variables X7 Y the conditional entropy ofX given Y is HXlY ZleY y HXlY y Lemma For function g HgXlX 0 HXlgX O iffg invertible Lemma Ile7 Xn are discrete random variables HX1Xn Z HXiX17X1 i6n IfX1 Xn are independent then HX17 7X Zieln HX Mutual Information Definition Given discrete random variables X Y the mutual information is x Y HX 7 HXlY HY 7 HYlX Given discrete random variables X Y Z the conditional mutual information is IX YlZ 2M2 z IX YlZ z Mutual Information Definition Given discrete random variables X Y the mutual information is x Y HX 7 HXlY HY 7 HYlX Given discrete random variables X Y Z the conditional mutual information is IX YlZ 2M2 z IX YlZ 2 Lemma IfX1 Xn Y are discrete random variables IX1Xn Y Z IX YlX1X1 i6n IfX and Y are independent IX Y 0 Outline Entropy and Binomial Coefficients Entropy and Binomial Coefficients Lemma r nH r n 2 lt n lt 2nHrn n 1 7 7 Where HX 7X Iogx 7 17 X Iog1 7 X Entropy and Binomial Coefficients Lemma n1 r Where HX 7X Iogx 7 17 X Iog1 7 X Proof gt Let q rn nHr n 2 S n 2WW Entropy and Binomial Coefficients Lemma n1 r Where HX 7X Iogx 7 17 X Iog1 7 X Proof gt Let q rn gt RHS nHr n 2 S n 2WW Entropy and Binomial Coefficients Lemma nH r n 2 lt n lt 2nHrn n1 r 7 Where HX 7X Iogx 7 17 X Iog1 7 X Proof gt Let q rn gt RHS 7 n n k 7 n7k n n 7 n7 n 7 n 7nHq 1 7 1 gt q 1 q 7 2 H ltkgtq q 7 W a W gt Claim qnnqq l 7 q quot 2 qk1 7 q for 0 g k g n 1 Entropy and Binomial Coefficients Lemma nH r n 2 lt n lt 2nHrn n1 r 7 Where HX 7X Iogx 7 17 X Iog1 7 X Proof gt Let q rn gt RHS 7 n n k 7 n7k n n 7 n7 n 7 n 7nHq 1 7 1 gt q 1 q 7 2 H ltkgtq q 7 W a W 03 cin1 7qquot1 W q 2Zqk17 q for 0 g k g n gt LHS lg n 1X5 qqn1 7 qn7qn n 1qnn2nHq 1 Proof of Claim Claim 5nqq 1 q quot ZZqk1 q k for 0 S k S n Proof of Claim Claim qnannu 7n7qn Z qkl 7 q k forO S k S n Proof gt Consider difference of terms qk1 qnek 7 k1gtqk117 0ka Proof of Claim Claim 5nqq 1 q quot ZZqk1 q k for 0 S k S n Proof gt Consider difference of terms qk1 qnek 7 k1gtqk117 0ka ltZgtqk1iq k lt1Zampgt gt This is non negative when k 2 qn71 q Proof of Claim Claim 5nqq 1 q quot 2 Zqk1 q k for 0 S k S n Proof gt Consider difference of terms qk1 qnek 7 k1gtqk117 0ka ltZgtqk1iq k lt1Zampgt gt This is non negative when k 2 qn71 q gt Terms increasing up to k qn and decreasing afterwards Outline Extracting Random Bits Extracting Random Bits Definition An extraction function Ext takes the value of a random variable X and outputs a sequence of bits y such that if P yi k 7 0 PiExtX YiiYi k 2 Extracting Random Bits Definition An extraction function Ext takes the value of a random variable X and outputs a sequence of bits y such that if PHyi k 7 0 PiExtX YiiYi k 2 Theorem Consider a coin With bias p gt 12 For any constant 6 gt O and n sufficiently large gt There exists an extraction function that takes n independent coin flips and outputs an average of at least 1 7 6nHp unbiased and independent random bits gt The average number of unbiased and independent bits output by any extraction function on an input sequence ofn independent flips is at most nHp Extracting bits from uniform distributions 12 Lemma Suppose X is uniformly distributed in 07 7 m 7 1 Then there is an extraction function forX that outputs on average at least log mi 7 1 unbiased and independent bits Extracting bits from uniform distributions 12 Lemma Suppose X is uniformly distributed in 07 7 m 7 1 Then there is an extraction function forX that outputs on average at least log mi 7 1 unbiased and independent bits Proof gt Let Oz log mi and define the extraction function recursively Extracting bits from uniform distributions 12 Lemma Suppose X is uniformly distributed in 07 7 m 7 1 Then there is an extraction function forX that outputs on average at least log mi 7 1 unbiased and independent bits Proof gt Let Oz log mi and define the extraction function recursively gt If X g 20 71 output the 1 bit representation of X Extracting bits from uniform distributions 12 Lemma Suppose X is uniformly distributed in 07 7 m 7 1 Then there is an extraction function forX that outputs on average at least log mi 7 1 unbiased and independent bits Proof gt Let Oz log mi and define the extraction function recursively gt If X g 20 71 output the 1 bit representation of X gt IfX 2 20 use the extraction function on X 7 20 since this is uniform on 07 7 m7 20 71 Extracting bits from uniform distributions 12 Lemma Suppose X is uniformly distributed in 07 7 m 7 1 Then there is an extraction function forX that outputs on average at least log mi 7 1 unbiased and independent bits Proof gt Let Oz log mi and define the extraction function recursively gt If X g 20 71 output the 1 bit representation of X gt IfX 2 20 use the extraction function on X 7 20 since this is uniform on 07 7 m7 20 71 gt For each k we get uniform distribution over k bit sequences Extracting bits from uniform distributions 12 Lemma Suppose X is uniformly distributed in 07 7 m 7 1 Then there is an extraction function forX that outputs on average at least log mi 7 1 unbiased and independent bits Proof gt Let Oz log mi and define the extraction function recursively gt If X g 20 71 output the 1 bit representation of X gt IfX 2 20 use the extraction function on X 7 20 since this is uniform on 07 7 m7 20 71 gt For each k we get uniform distribution over k bit sequences gt Remains to show that we expect to output log mi 71 unbiased and independent bits Extracting bits from uniform distributions 22 gt Let Y be the number of bits output Extracting bits from uniform distributions 22 gt Let Y be the number of bits output gt By induction on m 20 7 2 EY i0 m m 0 i042 m Ebits from07 7 m7 20 71 3 M077 7 2m 71 m m72 i Extracting bits from uniform distributions 22 gt Let Y be the number of bits output gt By induction on m EY am2 Ebitsfrom0m72 71 2 WM llogm72 l1 gt Some algebra gives this is at least 04 71 completing induction Extracting Bits from Biased Coin Upper Bound 12 Theorem Consider coin With bias p gt 12 For any constant 6 gt O and n sufficiently large there exists a function that takes n independent coin flips and outputs an average of at least 17 6nHp independent and unbiased bits Extracting Bits from Biased Coin Upper Bound 12 Theorem Consider coin With bias p gt 12 For any constant 6 gt O and n sufficiently large there exists a function that takes n independent coin flips and outputs an average of at least 17 6nHp independent and unbiased bits Proof gt Let Z be number of heads seen Extracting Bits from Biased Coin Upper Bound 12 Theorem Consider coin With bias p gt 12 For any constant 6 gt O and n sufficiently large there exists a function that takes n independent coin flips and outputs an average of at least 17 6nHp independent and unbiased bits Proof gt Let Z be number of heads seen gt Conditioned on Z k each of sequence sequences is equally likely Can expect to extract llog 71 bits Extracting Bits from Biased Coin Upper Bound 12 Theorem Consider coin With bias p gt 12 For any constant 6 gt O and n sufficiently large there exists a function that takes n independent coin flips and outputs an average of at least 17 6nHp independent and unbiased bits Proof gt Let Z be number of heads seen gt Conditioned on Z k each of sequence sequences is equally likely Can expect to extract llog 71 bits gt Let B be total number of bits extracted EB iMZ kEBlZ k 2 iMZ mliog Djil k0 k0 D Extracting Bits from Biased Coin Upper Bound 22 gt Consider only k such that n2 np 7 e g k np e w 2 W5 W k W M 1 k i P 5i Extracting Bits from Biased Coin Upper Bound 22 gt Consider only k such that n2 np 7 e g k np l e w Z quot5 W k log Di 1 k l P 5l gt Relating binomial coefficients to entropy quotHP6 llog 71 log 7 2 Extracting Bits from Biased Coin Upper Bound 22 gt Consider only k such that n2 np 7 e g k np l e w Z quot5 W k log Di 1 k l P 5l gt Relating binomial coefficients to entropy quotHP6 llog 71 log 7 2 gt Appealing to ChernofF bound lnpel 2 Z 1PZk172e 53P k7inp7ei Extracting Bits from Biased Coin Upper Bound 22 gt Consider only k such that n2 np 7 e g k np l e w Z quot5 W k log Di 1 k l P 5l gt Relating binomial coefficients to entropy quotHP6 llog 71 log 7 2 gt Appealing to ChernofF bound lnP6l 2 M2 k 2 17 2e neg3P kl P 5l gt Putting it together E B 7 Hpe7Iogn172172equot 23P 2 176nHp where the last inequality is for sufficiently large n Extracting Bits from Biased Coin Tosses Lower Bound Theorem Consider a coin With bias p gt 12 The average number of bits output by any extraction function on an input sequence of n independent flips is at most nHp Extracting Bits from Biased Coin Tosses Lower Bound Theorem Consider a coin With bias p gt 12 The average number of bits output by any extraction function on an input sequence of n independent flips is at most nHp Proof gt Consider extraction function Ext Extracting Bits from Biased Coin Tosses Lower Bound Theorem Consider a coin With bias p gt 12 The average number of bits output by any extraction function on an input sequence of n independent flips is at most nHp Proof gt Consider extraction function Ext gt Ifx occurs with probability q then iEXtXi og1q since qgi EX Xi g 1 Extracting Bits from Biased Coin Tosses Lower Bound Theorem Consider a coin With bias p gt 12 The average number of bits output by any extraction function on an input sequence of n independent flips is at most nHp Proof gt Consider extraction function Ext gt Ifx occurs with probability q then iEXtXi og1q since quEX Xi g 1 gt Let B be number of bits extracted by Ext EB ZPXxiExtxi ZPXXiOgm D Outline Pairwise Independent Functions Pairwise Independent Functions gt Let n bea primeand ab R 07177n71 Pairwise Independent Functions gt Letn bea primeand ab R 07177n71 gt Consider Z R07 Rn71 where R 3 b mod n Pairwise Independent Functions gt Let n bea primeand ab R 07177n71 gt Consider Z R07 Rn71 where R 3 b mod n gt Entropy of each R Pairwise Independent Functions gt Let n bea primeand ab R 07177n71 gt Consider Z R07 Rn71 where R 3 b mod n gt Entropy of each R HR log n Pairwise Independent Functions V Let n bea primeand ab R 07177n71 Consider Z R07 Rn71 where R 3 b mod n Entropy of each R HR log n Entropy of Z VVV Pairwise Independent Functions V Let n bea primeand ab R 07177n71 Consider Z R07 Rn71 where R 3 b mod n Entropy of each R HR log n Entropy of Z HZ 2 Iogn VVV Pairwise Independent Functions V Let n bea primeand ab R 07177n71 Consider Z R07 Rn71 where R ai b mod n Entropy of each R HR log n Entropy of Z HZ 2 Iogn VVV Lemma For discrete random variable X and function g HgX HX With equality iffg is invertible Pairwise Independent Functions gt Let n bea primeand ab R 07177n71 gt Consider Z R07 Rn71 where R ai b mod n gt Entropy of each R HR log n gt Entropy of Z HZ 2ogn Lemma For discrete random variable X and function g HgX HX With equality iffg is invertible Proof gt HX7gX HX HgXiX HX Pairwise Independent Functions gt Let n bea primeand ab R 07177n71 gt Consider Z R07 Rn71 where R ai b mod n gt Entropy of each R HR log n gt Entropy of Z HZ 2ogn Lemma For discrete random variable X and function g HgX HX With equality iffg is invertible Proof HX7gX HX HgXiX HX HX7gX HgX HXigX Z HgX Pairwise Independent Functions gt Let n bea primeand ab R 07177n71 gt Consider Z R07 Rn1 where R ai b mod n gt Entropy of each R HR log n gt Entropy of Z HZ 2ogn Lemma For discrete random variable X and function g HgX HX With equality iffg is invertible Proof HX7gX HX HgXiX HX HX7gX HgX HXigX Z HgX gt Z fa7 b where f is invertible Hence HZ H37b H3 Hb 2logn

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "I used the money I made selling my notes & study guides to pay for spring break in Olympia, Washington...which was Sweet!"

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.