Bounded Differences Inequality (aka Azuma-Hoeffding Inequality)

Key Takeaways

in this video we'll look at a powerful tool in the probabilistic method known as bounded differences inequality which also goes by the name auma hofing inequality this inequality tells us that if we have a function of independent random variables and such that this function doesn't change very much if we just change one of the inputs of the function then the output of this function given the random input is fairly concentrated around its mean let's look at this actual statement of this theorem we have X1 random variable taking values in the set or in the probability space Omega 1 and so on so so X1 X2 to xn so these are independent random variables and it's very important that they're independent we have a function f which takes as input and coordinates and outputs a real number and the hypothesis of this theorem is that this function f satisfies the following property that if we look at two different outputs of f on inputs X and Y such that X and Y differ on exactly one coordinate right so by only changing a single coordinate of f the assumption is that the value of f changes by no more than one right so F in some sense is fairly smooth to the fluctuations in the input if you change only one input coordinate then the output of f does not change too much does not change by more than one okay what is the conclusion of the theorem it says that the random variable obtained by evaluating F on these independent random input coordinates right so we call this output Z this random variable Z satisfies the following concentration inequality for every non- negative real Lambda the probability that Z is exceeds its expectation by at least Lambda is at most this quantity here which goes down rapidly as Lambda is gets large and also we also have a lower tail concentration bound which says that the probability that Z is significantly below its expectation by more than Lambda at least Lambda is this probability is upper bounded by the same quantity which again decays extremely quickly when Lambda is large okay so this is the statement of the bound the differences inequality again the intuition here is that given independent inputs to a function which satisfies this property that it does not change by more than one upon changing any single coordinate the output random variable is very concentrated around the mean in the rest of this video I want to present three applications of this inequality the first application is meant to illustrate a very simple example of a function where we can apply the theorem and this function is simply the function taking Boolean input so n Boolean inputs outputs a real number obtained by simply adding up the input numbers another words this is a sum of N different coin tosses each coin toss resulting in zero or one and you can check that this function has the property that we require in this theorem namely that if you flip just one of the input coordinates the output changes by well in this case exactly one but certainly no more than one now we can apply theuma hting inequality or the Bounder differences inequality to this function and that gets us a tail bound on the binomial distribution this case you know that the expectation of Z is exactly n /2 and it tells you that the deviation cannot exceed very much Beyond something on the Square on the order of the square root of uh the square root of n this bound is also known as the turnoff bound and in fact the proof of the bound differences in equality is very Sim similar to the proof of the turnoff bound which you can view in a different video let me now go on to the next example the next example concerned a problem called the coupon collector problem the setup is that we have independent random numbers S1 through SN and they're each chosen uniformly from the numbers 1 through n so these numbers are uniformly and independently chosen so you can imagine a setup as having and different coupons and each time you draw a random coupon see what it is return it to the box and draw it again and these S1 through SN are it's a list of coupons that you draw from this box and the random variable that we're interested in Z is the number of missing coupons the number of coupons that you have not seen through this process okay in other words this is the number of elements of one through n that are not among the elements S1 through SN okay so this is a number of missing coupons it is a random variable because S1 through SN are random we wish to understand how Z is concentrated around its mean and for that we can apply the bounded differences in equality note that this function given viewing this quantity as a function from S1 through SN as inputs to the output number this function satisfies the required hypothesis namely if you change one of the SI you do not change the number of missing coupons by more than one number of coupons missing coupons might not change at all but it cannot change by more than one so this means that we can apply the bound differences inequality to deduce the conclusion that the probability that Z deviates from its expectation by more than Lambda is at most two because here we're using upper and lower bounds simultaneously time 2 to the minus E 2 Lambda 2 / n and the expectation is something that we can calculate pretty easily using linearity expectations of these n different numbers these n different coupons each single coupon is missing with probability one minus 1 / n to the N right because in this does this is the probability that a specific coupon coupon I is missing which is the event that coupon I is not drawn in each of the N different random draws and this quantity is very close to n/ e okay so this is an application of the bounded differences inequality to a function which is not linear like before right so the first example is a much simpler example because the function f is simply a sum of its inputs and here there's a more complicated function our last example involves an even subtler function and here the result is a classic theorem in probabilistic combinatorics due to Shamir and Spencer from the 80s the theorem concerns the chromatic number of a random graph so let Z be the chromatic number of the random graph GNP okay so GMP is the airish r random graph obtained by taking n vertices and putting an edge between every pair of vertices with probability P so throw a probability P coin for each possible Edge independently and construct a random graph this way and then Z is the chromatic number of of this random graph right so it is the minimum number of colors required to color all the vertices so that no two adjacent vertices receive the same color this is some random variable and this random variable is pretty complicated it's pretty hard to analyze but nevertheless using the bound the differences inequality let us deduce the following concentration bound showing that Z typically is not too far away from its expectation and specifically we have the bound saying that Z deviates from expectation by more than this quantity here and this event has probability at most 2 * eus 2 Lambda s okay let's prove this theorem the interesting part of this proof is how to set up the function f so that we can apply the bounded differences inequality so right now Z is some quantity which seems kind of complicated and it's based on Something That Is Random so how can we phrase it in terms of independent random variables in a way so that we can apply the bound differences inequality well one way to do it and um it's a natural first attempt is to view Z as a function with n choose two inputs one input for each possible edge of the random graph that is a valid choice in the sense that it satisfies the bounded differences condition but it will not give the correct bound because it will turn out to have way too many variables in this function we'll take a look at a different method that will be able to provide us with the desired bound and there's some neat idea here on how to Cluster the random variables together so we will represent our graph on N vertices labeled 1 through n and this graph which has some edges and we'll need to represent these edges um will represent them as an element of the following product set Omega 1 * Omega 2 so these are cartisian products * Omega 3 so on to Omega n minus one and how we're going to encode the graph using the element of of this product set is as follows Omega 1 will be the set0 comma 1 and this set will record the which either zero or one which one gets chosen or record whether there's an edge between the first vertex and the second vertex okay so if we choose zero then there's no Edge between one and two if we choose one then there is an edge between one and two Omega 2 is the product set of 01 with itself and this two bits encodes whether there's an edge between one and three and also whether there's an edge between two and three that information is encoded in the element of Omega 2 that we choose and Omega 3 is now 0a 1 raised to the 3 power and here these three bits record whether the three edges from 1 two and three to the fourth vertex are included or not included in this graph and so on okay so every graph on N labelled vertices can be represented as an element of this product set and vice versa basically we are clustering the edges together according to the end point of its uh the right end point of its Edge according to this vertex order of the vertices okay so why is this useful well if we have two graphs G and G Prime that differ on edges around only one vertex okay um so if G and G Prime differ on edges around only one vertex then the chromatic number so Kai of G minus Kai of G Prime this in absolute value is at most one so if you have two graphs and one can be obtained from the other by modifying edges around a single vertex then their chromatic numbers cannot be differ cannot differ by more than one and the reason is that well we could have just chosen a new color for the vertex that is involved so we would not need to use more than one color change to go from one graph to another okay so this is a important fact that turns out to be incredibly useful and it's useful because if we have a graph represented as an element of this product set then having another graph that's obtained by just changing one coordinate results in a graph where the only changes to the graph itself are edges around a single vertex and therefore the function F that sends an element of this to an element of the r basically the chromatic number of the graph satisfies the bounded differences hypothesis and by applying the theorem we can then deduce the concentration bound here so that finishes the proof of this theorem on the concentration of a chromatic number of a random graph all right so in this video we saw the statement of the bound differences inequality which is a important versatile tool that is used all over probabilistic combinatorics it says that the concentration of a function of independent inputs or this as long as the function has the property that it doesn't change very much if you only change a single coordinate then the output as a random variable is highly concentrated around its mean and we saw three different examples applying this Bounder differences in equality