### 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(4)

### View Full Document

## 14

## 0

## Popular in Course

## Popular in Department

This 63 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 14 views.

## Similar to Course at UMass

## Popular in Subject

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

### 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 15 amp 16 Martingales Andrew McGregor Last Comp ed Apm 2 2009 Two Exam ples Martingale Definitions Azuma Hoeffding Inequality Outline Two Exam ples Example Application Ballot Counting gt Suppose two candidates A and B run for an election gt A gets 3 votes and B gets b lt 3 votes gt If the votes are counted in random order what is probability that A is always ahead during the voting Example Application Gambling gt Suppose a gambler places bets on a sequence of fair games bets can increasedecrease based on history and he can stop at any time gt Let Xt be amount he wins at step 1 could be negative gt Let Z Zidt gt Can he win money if he comes up with a clever strategy about when to quit 1X be total winning at end of t th step Outline Martingale Definitions Martingales Definition Given two rv39s X7 Y 1PX xiY is the rv taking value EDX xiY y with prob 1PY y ConsequentlyEXiY is rv taking value XXX X xiY y with prob JPY y Martingales Definition Given two rv39s X7 Y lP X le is the rv taking value EDX le y with prob lPY y ConsequentlyEXlY is rv taking value ZXXlP X le y with prob JPY y Definition A sequence of rv39s Z07217 is a martingale with respect to sequence X07X17 if for all n 2 0 gt Z is a function of X07X17 7Xn gt E lan lt oo E lZn1lX07 7an Zn Zo7 Zl is a martingale if it39s a martingale with respect to itself Martingales Definition Given two rv39s X7 Y lP X le is the rv taking value EDX le y with prob lPY y ConsequentlyEXlY is rv taking value ZXXlP X le y with prob JPY y Definition A sequence of rv39s Z07217 is a martingale with respect to sequence X07X17 if for all n 2 0 gt Z is a function of X07X17 7Xn gt E lan lt 00 gt E Zr1l07 7r Zn Zo7 Zl is a martingale if it39s a martingale with respect to itself Eg In the gambling problem IEZlur1lX17 7Xil Zi ElXi1l Z Simple Lemmas Lemma Em EHEW ZH Lemma E X Y IE X fY iff is invertible Lemma IE XX Y X Deciding when to stop ahead of time Suppose before he starts the gambler decides he39ll quit after the n th game What39s the gambler39s expected winning Deciding when to stop ahead of time Suppose before he starts the gambler decides he39ll quit after the n th game What39s the gambler39s expected winning Lemma I1 Z07217 72 is a martingale With respect to X07 X17 Xn then E Zn E Zo Deciding when to stop ahead of time Suppose before he starts the gambler decides he39ll quit after the n th game What39s the gambler39s expected winning Lemma I1 Z07217 72 is a martingale With respect to X07 X17 Xn then E Zn E Zol Proof gt By the martingale definition Z E Z1lX07 7X Deciding when to stop ahead of time Suppose before he starts the gambler decides he39ll quit after the n th game What39s the gambler39s expected winning Lemma I1 Z07217 72 is a martingale With respect to X07 X17 Xn then E Zn E 20 Proof gt By the martingale definition Z E Z1lX07 7X gt Take expectation E Z E E 21le X E 21 D Deciding when to stop ahead of time Suppose before he starts the gambler decides he39ll quit after the n th game What39s the gambler39s expected winning Lemma I1 Z07217 72 is a martingale With respect to X07 X17 Xn then E Zn E Zol Proof gt By the martingale definition Z E Z1lX07 7X gt Take expectation E Z E E 21le X E Zi1 gt Repeating argument gives result D Deciding when to stop based on evolving sequence Definition Stopping Time A non negative integer valued random variable T is a stopping time for sequence Zn n 2 0 if the event T n depends only on the value of the random variables Z07217 7Zn Deciding when to stop based on evolving sequence Definition Stopping Time A non negative integer valued random variable T is a stopping time for sequence Zn n 2 0 if the event T n depends only on the value of the random variables Z07217 7Zn Theorem Martingale Stopping Theorem If Zo7 217 is a martingale With respect to X07X27 and if T is a stopping time for X07X27 then E Zr E Zol Whenever one of the following holds gt Z are bounded ie for constant c lZl S c for all i gt T is bounded gt E T lt 00 and there exists constant c such that ElZ1 7 Z ll07 7 lt C Ballot Example 14 gt Two candidates A and B run for an election with n voters gt A gets 3 votes and B gets b lt 3 votes gt If the votes are counted in a random order what is the probability that A is always ahead during the voting Ballot Example 24 gt Let 5k votes by which A leads after k votes counted gt Hence A has k l Sk2 votes and B has k7 Sk2 votes after k votes have been counted Ballot Example 24 gt Let 5k votes by which A leads after k votes counted gt Hence A has k l Sk2 votes and B has k7 Sk2 votes after k votes have been counted gt Note that 5k 5H1 i1 and k1 5k12 k1 m 1 wan2 k1 l 5k 5k1 1l5k1l 1P lsk 5k1 1l5k1l Ballot Example 34 gt Define martingale Xk 5nkn 7 k for O S k g n 71 Ballot Example 34 gt Define martingale Xk 5nkn 7 k for O S k g n 71 EXle0 Xk1 Ballot Example 34 gt Define martingale Xk 5nkn 7 k for O S k g n 71 EXle0 Xk1 snik IE 5quot75n nikl kll Ballot Example 34 gt Define martingale Xk 5nkn 7 k for O S k g n 71 EXle0 Xk1 7 sn7k E niklsn77sn7k1 1 l 5n7k 5n7k1 1l5n7k1sn7k1 1 n 7 k 1 sn7k sn7k1 llsn7k1l sn7k1 1 Ballot Example 34 gt Define martingale Xk 5nkn 7 k for O S k g n 71 EXle0 Xk1 E sn7k n 7 klsnv 7sn7k1 1 n 7 k l 5n7k 5n7k1 1l5n7k1sn7k1 1 1 sn7k sn7k1 llsn7k1l sn7k1 1 7 1 n7 k 17 Snk12 n7klt n7k1 Snikllll 7 k 1 5n 2 Wsn7kl 1 Ballot Example 34 gt Define martingale Xk 5nkn 7 k for O S k g n 71 EXle0 Xk1 7 E snik n 7 klsnv 7snik1 l n 7 k l snik 5n7k1 1l5n7k1snik1 1 1 snik 5n7k1 1l5n7k1l 5n7k1 1 7 1 n7 k17 snk12 niklt nik1 Snikllll n7 k1nik12 7 ni k1 5n7k1 1 snik1 m m Ballot Example 34 gt Define martingale Xk 5nkn 7 k for O S k g n 71 EXle0 Xk1 sn7k IE 5 5 ln 7 kl kll l n 7 k l 5n7k 5n7k1 1l5n7k1sn7k1 1 1 sn7k sn7k1 llsn7k1l sn7k1 1 7 1 n7 k17 snk12 n7klt n7k1 Snikllll n7 k1sn7k12 7 ni k1 sn7k1 1 sn7k1 m m gt Clearly that Ele1l n lt oo Ballot Example 44 gt Let Tminn71UkXk0 Ballot Example 44 gt Let Tminn71UkXk0 gt T is bounded stopping time Martingale Stopping Thm gives ESn7aib n iab E XT E X0 Ballot Example 44 gt Let Tminn71UkXk0 gt T is bounded stopping time Martingale Stopping Thm gives EX71EX01Elns l gt If A always leads then T n 71 and X7 1 1 Ballot Example 44 gt Let Tminn71UkXk0 gt T is bounded stopping time Martingale Stopping Thm gives En 37 b E E XTl X0 n 3 b gt If A always leads then T n 71 and X7 1 1 gt If A doesn39t always lead then T k lt n 71 and X7 O Ballot Example 44 gt Let T minn71UkXk0 gt T is bounded stopping time Martingale Stopping Thm gives En iaib n ab 1E XT E X0 gt If A always leads then T n 71 and X7 1 1 gt If A doesn39t always lead then T k lt n 71 and X7 O gt Hence XT O or X7 1 and aib ab 1E X7 111D A always leads0lP A doesn39t always lead Wald s Equation Theorem Let X17X27 be non negative independent identically distributed random variables With distribution X Let T be a stopping time for this sequence If T and X have bounded expectation then T 2x i1 IE ETEX Wald s Equation Theorem Let X17X27 be non negative independent identically distributed random variables With distribution X Let T be a stopping time for this sequence If T and X have bounded expectation then T 2x i1 E ETEX Proof For i 2 1 let 2 31109 7EX Wald s Equation Theorem Let X17X27 be non negative independent identically distributed random variables With distribution X Let T be a stopping time for this sequence If T and X have bounded expectation then T 2x i1 E ETEX Proof For i 2 1 let 2 31109 7EX gt Z1722 is martingale wrt X17X27 and EZ1 O Wald s Equation Theorem Let X17X27 be non negative independent identically distributed random variables With distribution X Let T be a stopping time for this sequence If T and X have bounded expectation then T 2x i1 E ETEX Proof For i 2 1 let 2 31109 7EX gt Z1722 is martingale wrt X17X27 and EZ1 O gt E T lt 00 and EHZHl 7 ZHX1 X 2EX hence Em Em 0 Wald s Equation Theorem Let X17X27 be non negative independent identically distributed random variables With distribution X Let T be a stopping time for this sequence If T and X have bounded expectation then T E ZX ETEX i1 Proof For i 2 1 let 2 31109 7EX gt Z1722 is martingale wrt X17X27 and EZ1 O gt E T lt 00 and ElZ1 7 ZillX1 X 2EX hence EizTi Eizli 0 gt Results follows since EZT IE XL1 7E TEX Application of Wald s Equation 12 gt Suppose n servers communicate using shared channel gt At each step each server sends a message with prob ln gt Send is successful if only one message is sent gt What39s expected time until all servers have sent 2 1 message Application of Wald s Equation 22 gt Let N be packets sent successfully until each server has sent at least one packet IEN nHn Application of Wald s Equation 22 gt Let N be packets sent successfully until each server has sent at least one packet EN nHn gt Let t be time of i th successful send Application of Wald s Equation 22 gt Let N be packets sent successfully until each server has sent at least one packet EN nHn gt Let t be time of i th successful send gt Let r t 7 171 l one message sent 7 1 Er 1lP one message sent 1p Application of Wald s Equation 22 gt Let N be packets sent successfully until each server has sent at least one packet EN nHn gt Let t be time of i th successful send gt Let r t 7 171 l one message sent 7 1 Er 1lP one message sent 1p gt Then T r is time at which all servers have sent 1 message Em E ElNlEM nHnp I39dV Outline Azuma Hoeffding Inequality Azuma Hoeffding Inequality Theorem Azuma Hoeffding Inequality Let X07 Xn be a martingale With le iXkAl g ck Then for all t 2 O and any gt 0 IPHXt 7 Xol 2 S 2e A2Zzi1ck2 Azuma Hoeffding Inequality Theorem Azuma Hoeffding Inequality Let X07 Xn be a martingale With le iXkAl g ck Then for all t 2 O and any gt 0 IPHXt 7 Xol 2 S 2e A2Zzi1ck2 Proof gt Let YX7X1 g c and EYilX07X17 7Xi71 E XilX07X17 7Xi71 Xi71 0 Azuma Hoeffding Inequality Theorem Azuma Hoeffding Inequality Let X07 Xn be a martingale With le iXkAl g ck Then for all t 2 O and any gt 0 IPHXt 7 Xol 2 2e A2Zzi1ck2 Proof gt Let YX7X1 g c and EYilX07X17 7Xi71 E XilX07X17 7Xi71 Xi71 0 gt By convexity of eu yl 7L L DLC DZC anlt1 Ceiaq1Ceaqiele 0467 2c m 2 2 2 e Azuma Hoeffding Inequality Theorem Azuma Hoeffding Inequality Let X07 Xn be a martingale With le 7Xk21l ck Then for all t 2 O and any gt 0 IPHXt 7 Xol 2 2e A2Zzi1ck2 Proof gt Let YX7X1 g c and EYilX07X17 7Xi71 E XilX07X17 7Xi71 Xi71 0 gt By convexity of eu yl 17L 1 L ac DZC anlt CeiuzC F Ceaqie 9 l 046 2 i 2 2 2 e l gt Putting above two lines together lt emf2 l A E eaKlX07X17H397XIil Proof Continued gt Applying the previous bound repeatedly S eZEtD C22 H iet IE 9010940 IE Proof Continued gt Applying the previous bound repeatedly S eZEtD C22 H iet IE 9010940 IE gt By Markov inequality E eaXt7Xo 1P Xt 7 X0 2 1P eMXt X 2 em 3 em Proof Continued gt Applying the previous bound repeatedly S eZEtD C22 H iet IE 9010940 IE gt By Markov inequality E eaXt7Xo 1P Xt 7 X0 2 1P eMXt X 2 em 3 em gt Combing above two lines and choosing Oz Zkem cg ED Xt 7 X0 2 A S eZngCVZ D A S e Agingm Ci Proof Continued gt Applying the previous bound repeatedly S eZEtacl22 H iet IE 9010940 IE gt By Markov inequality E 04Xt7Xo PDQ 7X0 2 A ED eDtXt XO 2 804A S gt Combing above two lines and choosing Oz Zkem cg ED Xt 7 X0 2 A S eZetD C22 DH S e Agingm C gt Bound for lP X0 7 Xt 2 follows similarly Application to Pattern Matching gt Let X X17 7Xn be sequence of characters drawn independently and uniformly from a size 5 alphabet X Application to Pattern Matching gt Let X X17 7Xn be sequence of characters drawn independently and uniformly from a size 5 alphabet X gt Let B b17 bk be a fixed set of characters from X Application to Pattern Matching gt Let X X17 7Xn be sequence of characters drawn independently and uniformly from a size 5 alphabet X gt Let B b17 bk be a fixed set of characters from X gt Let F be number of occurrences of the fixed string B Application to Pattern Matching gt Let X X17 7Xn be sequence of characters drawn independently and uniformly from a size 5 alphabet X gt Let B b17 bk be a fixed set of characters from X gt Let F be number of occurrences of the fixed string B gt By linearity of expectation EF n 7 k11sk Application to Pattern Matching gt Let X X17 7Xn be sequence of characters drawn independently and uniformly from a size 5 alphabet X Let B b17 bk be a fixed set of characters from X Let F be number of occurrences of the fixed string B By linearity of expectation E F n 7 k 11sk Define the following martingale VVVV Z1llEF7 ZiEFlX177Xi forlgign Application to Pattern Matching gt Let X X17 7Xn be sequence of characters drawn independently and uniformly from a size 5 alphabet X Let B b17 bk be a fixed set of characters from X Let F be number of occurrences of the fixed string B By linearity of expectation E F n 7 k 11sk Define the following martingale VVVV Z1llEF7 ZiEFlX177Xi forlgign V Because the i1 th character occurs in at most k matches lZi17 Zil lEFlX17Xi17EFlX177Xi l g k Application to Pattern Matching b VVVV V V Let X X17 7Xn be sequence of characters drawn independently and uniformly from a size 5 alphabet X Let B b1L7 Let F be number of occurrences of the fixed string B By linearity of expectation E F n 7 k 11sk Define the following martingale 7bk be a fixed set of characters from X Z0 IlEI 7 Z EFlX1X for 1 i n Because the i1 th character occurs in at most k matches lZ1 7 Zil lEFlX17X17EFlX177X l g k Note that Z F By applying Azuma39s inequality puzn 7 zoi 2 ma aW Azuma Hoeffding Inequality Generalization Theorem Azuma Hoeffding Inequality Let X07 7Xr be a martingale With Bkgxk inlgBk i dk for some constants dk and for some random variables Bk that may be a function oon7 7Xk1 Then for all t 2 O and any gt 0 P ixt 7X0i 2 A armZia d3 Applying Azuma Hoeffding Inequality gt For a function f R HR with IiEifX1X27 7Xni lt 00 for random variables X17 Xn define the martingale Zo E 1X17 X27 7Xn Zk E 1X17X27 7XniX17 7in Applying Azuma Hoeffding Inequality gt For a function f R HR with IiEifX1X27 7Xni lt 00 for random variables X17 Xn define the martingale Zo E 1X17 X27 7Xn Zk E 1X17X27 7XniX17 7in gt Suppose f R a R satisfies the Lipschitz condition with bound 6 ie for any i X17 7Xn7y ifx177xnifx177X17yi7xi17xni c Applying Azuma Hoeffding Inequality gt For a function f R HR with IiEifX1X27 7Xni lt 00 for random variables X17 Xn define the martingale Zo E 1X17 X27 7Xn Zk E 1X17X27 7XniX17 7in gt Suppose f R a R satisfies the Lipschitz condition with bound 6 ie for any i X17 7Xn7y ifx17 7Xn 7 fx17 7X17yX17 Xni c gt fX39s are independent it can be shown that Bkgxk inl S Bk C where Bk infEfX17 7XniX17 7Xk1Xk y 7EfX1XniX1Xk1 Applying Azuma Hoeffding Inequality gt For a function f R HR with IiEifX1X27 7Xni lt 00 for random variables X17 Xn define the martingale Zo E 1X17 X27 7Xn Zk E 1X17X27 7XniX17 7in gt Suppose f R a R satisfies the Lipschitz condition with bound 6 ie for any i X17 7Xn7y ifx17 7Xn 7 fx17 7X17yX17 Xni c gt fX39s are independent it can be shown that Bkgxk inl S Bk C where Bk ianiEfX177XriX177Xk1Xlt y 7EfX1XniX17Xk71 gt Hence by Azuma PHXt iXoi Z 2e 2A2Zi cg

### 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

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "When you're taking detailed notes and trying to help everyone else out in the class, it really helps you learn and understand the material...plus I made $280 on my first study guide!"

#### "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.