2/3 Disordered systems and random graphs
CC Attribution - NonCommercial - NoDerivatives 4.0 International:
You are free to use, copy, distribute and transmit the work or content in unchanged form for any legal and non-commercial purpose as long as the work is attributed to the author in the manner specified by the author or licensor.
Coja-Oghlan, Amin
Besides being a classical research topic at the junction of combinatorics and probability with applications in several other disciplies, random graphs and their phase transitions have been attracting the interest of the statistical physics community. From a statistical physics viewpoint, random graphs can be viewed as disordered systems, real-world examples of which include glasses and spin glasses. Physicists have thus brought to bear techniques centered around the notion of "replica symmetry breaking", thereby putting forward a multitude of predictions. In this course we will learn about the present state of the art with respect to rigorising these predictions, and about the new mathematical tools developed over the recent years. Additionally, we will look at applications, particularly in the area of Bayesian inference.
 Okay, so what I'm going to do today is I'm going to talk you more precisely, more or less talk you back to back through the physics intuition and the mathematical corroboration of the two-set result. So what we are going to look at is a random two-set formula like we talked about in the previous lecture. So we have n Boolean variables and clauses that look like this, propositional clauses that look like this. And so we are looking at a random two-set formula with a also dn on two number of clauses. So the average number of clauses in which a variable appears is just d. And what we would like to determine is the number of satisfying assignment that such a formula typically has to be more precise because that number scales exponentially. We would like to compute the limit as n goes to infinity of 1 on n, knock off number of satisfying assignments. And we saw last time that unfortunately something as simple as first and the second moment calculation go to the trick. So we need to dig a bit deeper. And this is where the physics intuition comes in. And in particular, the favorite toy of our very good friends from physics called belief propagation. We already saw that we can turn this random two-set problem into a graph. On the one side, we have the propositional Boolean variables. And on the other side, we have the clauses which are constraints that bind variables. And the colors of the edges between them indicate whether a variable appears in the clause positively or negatively. And we already spoke a little bit about the structure of this resulting random graph, namely, locally, this random graph resembles a Gordon Watson tree. And in particular, this graph doesn't contain a whole lot of short cycles. Locally it is tree-like. And the degrees are bounded. Obviously the degrees of the clauses are always precisely two. And the number of neighbors of a specific variable is approximately more so d. Now we already also spoke about the Boltzmann distribution, which unsurprisingly is the protagonist of this problem from the physics perspective. And that's just the uniform distribution on the set of satisfying assignments. And I'm going to write this built sigma for a sample from this Boltzmann distribution. Because a built sigma is just a uniformly random satisfying assignment of our formula. Now the main challenge in this problem is to actually get a handle on the Boltzmann distribution. And in particular, to understand the marginals of Boltzmann distribution, that is the probability that under a randomly chosen satisfying assignment, a specific variable is set to the value true. And the device that physicists came up with in order to get a grip on the Boltzmann distribution and its marginals is a message passing process called belief propagation. The messages in this case are associated with the edges of the graph. And more precisely for any pair of adjacent variables and clauses for any edge of the factor graph, there's two messages traveling across that edge. One message goes in the direction from the variable to the clause. And the other message is going to go in the reverse direction from the clause to the value. What's the combinatorial meaning of the message from a variable to a clause? Well, the combinatorial meaning is that this is going to be the marginal of that variable in the absence of this particular clause. So what would this variable do if I were to remove this clause from the formula? So the message is simply the probability that this variable here is set to plus one or to minus one if I remove this clause here from the graph. So in particular, it's a probability distribution on plus minus one on the two Boolean values. How about the message in the reverse direction from a clause to a variable? The idea is similar, but this time the message from A to X, from for example, A1 to X1, is simply going to be the marginal of this variable if I remove all the other clauses apart from A where X appears in. So in this specific case, the message from A1 to X1 would be the marginal of X1 if I remove A2. So in other words, this is effectively the influence of A1 on X1 if I forget everybody else. So this is essentially what A1 would like X to do if there was nobody else interfering. And the nice thing about these messages by comparison to plain old marginals is that we can actually write a system of self-consistent equations for them. So we can actually relate these messages to one another through a reasonably conceivable system of equations. And these are the so-called belief propagation equations. These equations essentially express our intuition that in this problem there's no long-range correlations. So the gist of it is no long-range correlations. There's short-range correlations only. And the short-range correlations can be expressed because of this particular structure that we introduced for the messages. And to be more precise, what these equations express is the following. So suppose I look at a variable X like this one here, and I want to calculate the message that X sends to some clause A that sits up here. Then I can hope that there's no correlations between these different influences that come to X from down below from these three branches down here. Why can I hope that? Well, I can hope that because my formula is locally tree-like. So it is very unlikely that these different branches down here will meet within a short period of time other than through X itself. So if I were to remove X from the graph, then there would be a large distance between these different clauses here and these different variables. So the only way they interact is presumably, unless there's long-range interactions, through this variable right up here. And so this notion, this idea of independence of these different branches is precisely what we can express in terms of messages. And this intuition, if you work it out a little bit, tells you that the message that X sends to A has a product structure. So it's essentially the product of the influences on X that result from these different branches down below. To be precise, because we want our messages to be probability distributions on plus or minus one, we have to do a normalization. And I didn't write the normalization. It's hidden in this proportional symbol here. And so like I said, these self-consistent equations that link the messages to each other essentially express the independence of these different branches. That's for the messages from X, from this variable up here to some other clause that's maybe somewhere up there. And we can write even simpler equations, even simpler recurrence relations for the clauses because each clause only has a single child. So for the clauses, it turns out that we can actually write the message in this particular simple form. Again, there's a normalization missing. And what this expresses is simply the probability that this variable here is going to satisfy the clause if I set the variable up here to some particular value sigma. So I don't expect you to fully grasp these equations in an instant. You can read up on them later if you care about it. But like I said, the gist of it is no long-range correlations means I can write down a recurrence relation that expresses short-range correlations. And so actually, coming back to the previous slide again, actually, if my formula would be completely acyclic, if there weren't any cycles in the graph at all, then a simple inductive argument tells you that these equations are actually 100% spot on. They are 100% accurate. And in fact, if you do a bit of induction, you find that on an acyclic formula, on an acyclic graph, you can even write a formula for the partition function purely in terms of these messages. And this formula for the partition function is something called the beta-free entropy in physics language. And so this formula is, like I said, 100% accurate if your formula happens to be acyclic. The graph doesn't contain any cycles at all. And again, I don't expect you to grasp this completely right here on the spot, but just bear with me. And this is something that you can work out essentially as an exercise if there's no cycles. Now like I said, locally, our formula is acyclic. Locally, it looks like a tree. There's few short cycles. And so we might hope that in the absence of long-range correlations, maybe we are in luck, and the same formula for the partition function like on a tree still applies in this scenario here. And this is what physicists would call the replicastometric answers. Now one drawback of this formula here is that, unfortunately, it speaks about the specific messages that visit along the edges of a specific two-sub formula. And so it seems that in order to calculate this monster here, you would actually have to first generate your formula and then maybe try and find the fixed point or the solution to these equations somehow and plug that into this slightly awe-inspiring formula here. And so obviously, that's not what we want. What we would like is we would like to be able to write a function that comes just in terms of the model parameters, in this case, just in terms of the average number of clauses that a variable appears in. And so our good friends from physics have a trick up their sleeves for this too. It is something called density evolution. And the big idea is to grossly simplify the belief propagation equations along the following lines. So suppose I forget about the identities of the edges of my graph. I don't care anymore which variable precisely is connected to which particular clause and so on and so forth. But what I do is I just take the messages, the belief propagation messages on my graph and I put them into one big back. And so mathematically, this back is of course called an empirical distribution. So pi phi is just the empirical distribution of all the messages from variables to clauses that actually travel along my random formula. Now given that locally the structure of the graph resembles a Gordon Watson tree, I can try and actually write down a fixed point equation not for individual messages one by one, but kind of statistically in distribution for all of this, I mean for this entire empirical distribution in one sweep. And so the intuition behind this would be that well, if I forget about the identities of the variables and clauses, then maybe I can do the following. A variable in my formula has Poisson d children. So I just generate a Poisson d variable. To be more precise, I generate two Poisson d on two variables, one representing the plus children, the children where my variable appears as a positive literal, and one representing the remaining minus children. And then I label under the hypothesis that these messages that come in from down here below, well, any old messages that travel along the edges of my factor graph, that is, I'm going to presume that these messages that come in from below are actually independent samples from this empirical distribution. So I'm going to presume that actually in some sense, what matters is only the structure of the graph, only the geometry, how the geometry is distributed and not so much precisely which variable talks to which particular clause. And so this is again something where this construction of messages comes in handy because the message from X to A only essentially cares about the structure that lies on the other side of X that doesn't involve A. So maybe because of this particular message construction, this is a sensible thing to write down. And so what I'm writing down is, well, the message up here is essentially what I get if I generate these Poisson variables and stick in samples from my empirical distribution down below here. And this means that I'm arriving at this simplified belief propagation version. That's something called the density evolution equation in physics. So this is kind of like the belief propagation equation with the numerator and the normalizing term. But this time instead of meticulously tracing the incoming messages, I just take independent samples from this empirical distribution up here. And what this equation expresses is essentially the self-consistency of belief propagation, namely that the distribution of the message that I get out when I perform this operation is precisely pi phi, is precisely the empirical distribution of messages that I stick in. So you may find this a bit adventurous. And in fact, that's how many of us felt when we first saw this. But if you, I mean, it will grow on you. It's not as outlandish as it might at first seem. And so the big plus of this is that we get one equation, I mean, one fixed point equation, admittedly a more complicated fixed point equation because now the objects that we are talking about in this equation are random variables. But we get one single equation whose only parameter is a number, namely d. And so while you're in this mindset, you can also write along similar lines a simplified version of the beta free entropy in terms of this empirical distribution and along similar lines like similar reasoning, you see that this complicated free line formula with the various different logarithms and sums and products and so on and so forth actually simplifies in terms of this empirical distribution and boils down to this one line formula here. But these mu i's are independent samples from the probability distribution and again these d plus and d minus are independent plus or d on two variables. And so this finally leads to the so-called replicasometric solution or mathematically speaking replicasometric prediction for the number of satisfying assignments first derived by Monasson and Zekina in 96. And so this prediction holds that there's precisely one probability distribution, there's precisely one distribution on the unit interval that satisfies this stochastic fixed point equation that satisfies this equation that if you draw independent samples mu i from pi d you will get a random and apply this formula you will get something out that is distributed as pi d. And the prediction is that log Z is actually in the limit as n goes to infinity given by the beta free entropy that you get if you plug independent samples from this fixed point distribution into the beta free entropy. So I mean again let me emphasize that this is quite a bit more complicated than what we would get from the plane first moment calculation. And so the big plus of this more elaborate prediction is that it takes into account precisely the short range effects that take place on this random two-sub formula and it labors under the assumption that there's no long range effects going. And what we are going to do next is we are going to turn this prediction into a rigorous theorem. So we are going to prove in fact that this stochastic fixed point equation has a unique solution and that if you draw a bunch of independent samples from this distribution, from this fixed point distribution you get the number of satisfying assignments out. Now we prove that, let me show you what the result looks like. On the right hand side here you see on the x-axis D which ranges between 0 and 2, remember that the satisfiability threshold occurs at D equals 2. So there's no satisfying assignments left once D is greater than 2. The red line that you see here is this function B of D from the previous slide. So the red line is precisely the beta free entropy applied to our wondrous unique fixed point distribution. This blue dotted line here is the formula that you would get from the first moment. You can see that the blue line and the red line are reasonably close together but remember this is on an exponential scale, on a logarithmic scale. So a small difference here actually translates into an exponential factor between the first moment and the actual number of satisfying assignments. And something that you can maybe not quite as easily see in this plot is that the blue dotted line and the red line are never identical for any positive D. So the first moment is always for any specific D an overestimate of the actual number of solutions. So another thing to observe is that like I said the satisfiability threshold occurs at D equals 2. At D equals 2 our beta free entropy still has a positive value. So write the moment before your formula becomes unsatisfiable, it still has an exponential number of satisfying assignments. So it falls right off a cliff at the satisfiability threshold. On the left here what you see is the CDF of this fixed point distribution that comes out of this equation here for various values of D. For D equals 1.2 up to 1.9 and what you can see is that this fixed point distribution is something that is rather non-trivial. So this is not something that this is not presumably the thing you would first guess. And the reason is that this probability distribution here captures precisely the possible or the statistics of the short range correlations in your random two-sub formula up to any finite correlation length. And so we obtained this result using a computer calculation using a numerical calculation. And it turns out that actually this equation here, this fixed point equation converges rapidly so you can get very good estimates using relatively little computational resources. Anyway, so this much about the physics prediction, let's now see how we can prove such a thing, how we can turn this prediction into a theory. And the proof strategy has four items. The first item is something that is called the contraction method. And this is a trick that we are going to use in order to prove that this density evolution equation possesses a unique solution, that there's a unique way of solving this distributional equation. The second stop is going to be spatial mixing. So we are going to actually prove that in this random two-sub problem, there's no long range correlations. And this part of the proof is the core of the matter. This is where the meat is and where we will have to work the most. The next step is a coupling argument known as the Eisenman-Sim star scheme. And here we are going to combine the results of the first two steps in order to prove that the beta-free, the beta formula, the beta-free entropy actually correctly gives the expectation of log z phi. Now in this problem because we are looking at zero temperature at hard constraints that all simultaneously have to be satisfied, we are going to have to follow this up by another argument known as the interpolation method that will allow us to prove concentration of log z. So I think it's a good idea to maybe take a break at this point before we launch into the proof, before we actually begin with the contraction method. So why don't we take five minutes off? That sounds good. So if you have any questions feel free to ask them in the chat and I think we'll restart at 2 p.m. Do you have access to the chat, I mean? Yeah, I'm working on it. Okay, I can just read it out. Would you briefly say the meaning of the expectation of a random probability measure in the last two lines of the two slides ago? This slide right here. So the expectation right here at the bottom in the beta-free entropy formula. Right. Okay, so what this means is, so this means the expectation over everything. So this probability distribution pi d here is actually not a random probability measure, but it's a fixed probability measure, namely the unique probability measure so that if you draw a sample from this measure, which is mu zero, that sample is distributed precisely like the number that you would obtain if you were to draw independent samples mu i, multiply them up to an independent Poisson d over 2 variable d plus and then normalize accordingly. Now this expectation, oops, this expectation down here is the expectation over everything. So you generate an infinite sequence of independent samples from this distribution. So these mu i's are an infinite family of samples from pi d and d plus and d minus are again independent samples from the Poisson d over 2 distribution. So you just plug in the numbers that you get and you average over everything. Any other questions? Yeah, it's looking good. I think you can go to the proof. I'm looking a little dark, but I can try to maybe switch. I'm writing up matters a little. So did I manage to completely lose everybody? I think it's good you had just had the one question. Good. I'm happy to rumble on if you want me to. Okay, so we will try to now carry out this program. Yeah, so that's, in principle, I should say a few words about how this strategy compares to some prior work, not all of which deals with the two sub-proc. But let me just, let's just cut to the chase. I mean, the main difference really is that here we are talking about hard constraints, so you want to count assignments that satisfy every single clause simultaneously. And so that's basically the main difference between this and, for example, work on the easing model on random graphs. So, like I said, the first step on the agenda is going to be the contraction method. So we want to show that there that this stochastic fixed point equation here. So, so just out of curiosity, it would be interesting to see how many of you have dealt with stochastic fixed point equations before. I don't know if there's a way of indicating that in the chat, but I will be curious about this. So if you if you know them from some other context, maybe drop a line in the chat. Anyway, so we want to show that this stochastic fixed point equation where these new eyes are independent random variables and also the D plus and D minus random variables that this stochastic fixed point equation possesses a unique solution. And so one thing that is a bit unpleasant about this equation, I mean, even though it's one of the more amenable specimens that you will encounter in the context of the cavity method, one thing that is a bit unpleasant about it is that we have this complicated sum product structure here in the denominator. And so one trick that is often useful to get rid of this kind of nasty denominators is to look at log likelihood ratios. So this means that instead of studying the new eyes themselves the messages themselves which are numbers between zero and one. And what we are going to do is we are going to look at these log likelihood ratios log new I on one minus mu I, and that's a positive or negative real number. And by going to new I on one minus mu I be immediately get rid of this denominator and we are left with a product of quotients. And so upon taking the log this product turns into a sum. And so a fixed point equation from the previous slide turns into a sudden into any equation about sums of independent random variables, namely that the random variable eta zero is distributed precisely as a sum of a personal number of independent summons and has two Rademacher variables si and si prime, and then okay admittedly this log and 10 which are an acquired taste, but at least we have some of independent things so that's maybe something that we can work with and this equation now is precisely equivalent up to this transformation to the equation that we had on the previous slide. Now what we are going to do is we are going to look at this equation here this fixed point problem here. And we are going to use some tools from analysis. In order to solve this fixed point equation. And in particular what we are going to do is we are going to turn the space of probability measures into a complete metric space so that we can apply the fixed point theorems about metric spaces that we know and love. And it turns out the right space to look in this example is the wastes steins space. And the wastes steins steins space w two of us defined as the space of all probability measures on the real line with a finite second moment. The metric on the space is this wastes stein metric delta two of row and row prime. And this metric is defined as follows. So you first take a coupling of these two probability measures so you take one random variable X that is distributed as row and another random variable X prime that is distributed as well prime. And now these two random variables need not be independent instead they are they live on is on the same probability space. And you try to align them as best as you can. So as to minimize the resulting distance. And the minimum possible L two distance that you can accomplish in such a way is the wastes stein distance of these two probability measures. It's a simple exercise to show that this turns the W two space into a complete separable space. And on the space therefore we have our favorite better fixed point theory, which says the following if you have a contraction from this complete metric space into itself. That is a map that that decreases distances so if you take if you put two probability distributions row and row prime in and apply your map. Then the resulting distance is going to be smaller than the distance that you had previously that you started from. If you have such a map that is a contraction, then this map possesses a unique fixed point. So that's going to be our tool in order to show that there's a unique solution to this stochastic fixed point equation. And we will apply this map to our recurrent to our fixed point equation for log likelihood ratios. And what we are going to show to show is that this map that takes a probability distribution row and maps it to the distribution of this beautiful random variable down here actually is a contraction on the W two space. So effectively, the uniqueness of the solution to this density evolution equation follows from the Anak fixed point theory. The proof of this fact the proof of this contraction fact is given on this slide. I'm not going to talk you through it. It's it's not rocket science. It's just, as you can see, one, two, three, four, five steps. Six, okay, six steps. And none of them is difficult about the most sophisticated tool that you use is the coaching Schwarz inequality. And at the end of this calculation, you're convinced that your map is a contraction so long as D is less than two. And in fact, it is. So in fact, we are assuming that D is less than two, because for the greater than two, there's no satisfying. Okay, so using the butter fixed point theory and this was a science space. We are now sure that there's only one single solution to our density evolution fixed point equation to this simplified version of belief propagation on the random form. Let's move on to step two step two is that we are going to show spatial mixing. We are going to show that there's no long range correlations in our formula. And as an application of this, we will prove this proposition displayed here. If you take any D less than two. And you look at the empirical distribution of your Boltzmann marginals on your random formula. So you look at the, so you take all the Boltzmann marginals and you put them into one big bag. And so that gives you a probability distribution, a discrete probability distribution with support up to end points. And we will prove that this distribution here converges in the limit as n goes to infinity to the unique solution of your density evolution equation. So this pi D is the unique solution to the stochastic fixed point equation that we just derived using the Banach fixed point theory. And what we prove is that as you make n bigger and bigger as you take the number of variables in your formula to infinity, the empirical distribution of the Boltzmann marginals actually converges to this magical fixed point distribution. Okay, like I said, the main step is going to be spatial mixing. The main step is going to be to prove that if I take two variables in my formula that are far apart from each other, then their joint distribution factorizes. The true value here doesn't tell me a whole lot about the true value over here. And in order to prove the spatial mixing property, it turns out that fortunately, we can exclusively work on tree formulas on two set formulas that don't contain any cycles. Specifically, we can exclusively work on the two set formulas that are described by this gold Watson tree that captures the local structure of my random formula. So we are going to look at a gold Watson tree that starts at a root variable x zero. Every variable in this tree spawns a porcelain D number of clauses as offspring. For each clause we choose with probability one half, whether the variable appears positively or negatively in that clause. And with every clause spawns obviously a single variable as its child, which again spawns for some D clauses and so on. And what we are going to do is we are going to look at this gold Watson tree and truncated after L after two L steps for some large number L. And we are going to investigate how the true value of the root correlates with the true values at the boundary of the tree at the variables at level to L. And yeah, so what we are going to show is a very strong spatial mixing property known as the Gibbs uniqueness property. So here is your tree, here is your tree expanded up to level to L and now the Gibbs uniqueness property provides the following. Suppose I put in any consistent boundary condition on this tree. So I write down specific true values, blue representing true I think and red representing false. Any collection of true values for the leaves or for the boundary of this tree that can be extended to a satisfying assignment of the entire tree. So there must be a way of actually satisfying all the clauses in such a way that the boundary variables get these particular true values. So suppose I take any, any reasonable any conceivable boundary condition and I plug it in down here. And now I asked myself, given this boundary condition. What is the distribution of the true value of the root. So subject to this boundary condition. Draw a random satisfying assignment of the tree. And inspect the distribution of the true value assigned to the root. So that's some distribution on the true values plus one minus one true and false. And now I would like you to compare this distribution that you get for particular boundary condition with the free boundary distribution with the distribution that you would get. If you wouldn't plug in any boundary condition at all if you leave the boundary free you just take a uniformly random uniformly random satisfying assignment of this entire tree formula and inspect the distribution of the true value of Excel. And what this gives you need this property says is that these two numbers these two marginals are close to each other and actually the distance goes to zero as I make the tree taller and taller. So for in the limit of large L in the limit of limit of large trees. You cannot influence the value of the route by plugging in any boundary condition that you like. You cannot nudge the root out of place with any possible boundary condition. It's simply not possible. Now observe that this is a property that purely speaks about trees, but because the local structure of my random to start formula is described precisely by this tree. This property directly translates to the random to start formula. It directly implies that if I take a variable x zero in my to start formula and carve out a large depth neighborhood around this formula I draw a circle of radius to L around this variable and now ask, what is the impact. If I write down specific true values on that on on level to L of this circle that that has a diminishing influence on x zero itself. And like I said this is simply because the local structure of the formula is described precisely by this tree here. And right so what we are going to show is that in fact in the random to start problem this gives you need this property always holds. So the strong spatial mixing property here is always satisfied. Now, the proof of this is really the core of the matter, and it's not a trivial argument so maybe your first step at this might be that you write down the recurrence that given the boundary condition actually gives you the root marginal. And in fact you can do that in fact you can write this down meticulously. And what you end up writing down this way is precisely belief propagation. So let's start and maybe try take derivatives. So if I change the boundary values, how much this that actually influenced the root. You could try and trace this by using calculus. And we tried that for quite a while but it doesn't work very well. So you simply hit the ball and you turns out you hit the ball at equals one more deepers to like we want to accomplish. And you can try as you could simply try and take a union bound over all the possible boundary conditions. But unfortunately there's quite a few of them. Maybe in a god Watson tree like this normally the boundary dominates everything. So the number of possible boundary conditions is rather enormous so that doesn't work either. What we did instead is or what you can try instead is maybe you can try and recurs and try and try and take recourse to a combinatorial construction. And I thought that in this problem you can actually construct an extremal boundary condition so you can construct a boundary condition that will maximize the probability for example that that the root gets set to plus one. How do you do that. Well, it turns out to be more complicated than in many other problems like for example the using model or the hardcore model. So in this case is you actually have to look at the tree itself in order to come up with this extremal boundary condition. Here's how it works. Suppose I want to nudge the root variable as much as possible towards plus one. So I want to maximize the probability that the root is assigned to plus one. How do I do that. Well, I first look at all the clauses where the root appears positively all the clauses where the root appears with a plus sign. And now these clauses have another child and I'm going to go to that other child. And I'm going to try and nudge it away from the value that will satisfy this clause as much as I can. So in order to nudge the root, I have to nudge its children. I have to tell them, try as much as you can to steer clear of the value that will satisfy this clause because if this clause is unsatisfied by the child, it will ask the root, can you please satisfy me. And that will encourage the root to take the value plus one. On the other hand, I can look at the minus one children of the root. And I don't want the root dragged into the minus one direction by this clause here. So I'm going to look at the child of that clause and I'm going to try and tell this child, well, you know what, whatever you can do to satisfy this clause, do it. Try and satisfy this clause as much as you can. So I'm going to try and nudge this guy here in the plus one direction, simply so that it tries to satisfy this clause and simply so that this clause doesn't drag plus one in the wrong direction, leads plus one up here, the straight. And so you can you can now iterate this process, you can now recurse the same process on these child variables. We have some particular direction in mind that we want to nudge them. So we are going to pass to their children at in turn and try and nudge them in some particular direction and so on, until we reach the boundary of the tree. And you can prove by an induction that this will actually work and this process will actually give you the boundary condition that maximizes the probability of plus one at the root. So now in the second step what we would like to do is we would like to take this particular boundary condition that be meticulously constructed in this top down fashion, and now calculate, given this extremal boundary condition, the probability that actually the root is going to be plus one. Now at first glance, this seems rather challenging because in the process of constructing the boundary condition, we actually had to expose the entire tree we actually had to walk down the tree top to bottom look at every sign in the tree all the children and all the clauses and so on, in order to reach the extremal boundary condition so it seems that at this point we are actually stuck. There's no randomness left that could aid us pass this boundary condition back up no. There's no stochastic process anymore but we are just facing a deterministic problem so at first glance this seems rather hopeless, but at second glance it turns out that actually it isn't. Actually, you can fold the top down process and the bottom up process into a single recursion into a single message passing equation. So we can solve these two problems in one sweep. And you can express these two two processes that go hand in hand by a modified version of the density evolution equation that encoded leaf propagation. And so, again, formulating this equation in log likelihood ratios we end up with this equation here. So, this again is stochastic fixed point equation and it again has the same form that we saw previously, namely that you have the sum of independent random variables. And the only difference between the previous equation that we had in this one here is that here we have the same sign as I occurring twice. So previously this was an independent random sign. Now these two signs are identical. And if you work for maybe half an hour or so you will see that this actually corresponds precisely to this construction of the extremal boundary condition. So all we have to do in other words is we have to show that this fixed point equation here has a unique solution. And that this unique solution is identical to the solution that we got from the plane density evolution equation that this one here was an independent sign independent of this other guy over here. And turns out that this is actually correct. And you can use the contraction method again just like we did before a slightly modified version of the same calculation is going to show you that this guy also has a unique fixed point and actually for symmetry reasons it turns out that you can easily check that pi d the solution of the old density evolution equation also is the unique solution to this fixed point equation here. So the consequence of this is that this nudging here, even though it gives you the extremal probability, it maximizes the probability that the root is going to be plus one. Still doesn't move you away from the distribution that you had previously so as a conclusion, we can derive the fact that this problem here in fact has the Gibbs uniqueness property. So if you make your tree taller and taller, there's no way to construct a boundary condition that will match the root marginal away from the free boundary condition. Okay, so one coronary one immediate application of this fact is this asymptotic independent statement here. So what is this saying, this is saying that if you take any K specific variables in your random formula, for example, the first K variables. Or more generally some you choose K variables in your formula at random and this is for any fixed K for example K is 500. And you look at the joint probability that these variables these Boolean variables are assigned specific values. Then this probability here is approximately equal to the product of the individual marginal probability so the true values assigned to a bunch of far away variables in your propositional formula is essentially a product distribution. How do we how do we see that well we take a large number L we draw a large radius L around each of our variables. If you choose either the first K variables in our formula or otherwise K random variables. It's unlikely that they have distance, less than L that there's a pair wise distance less than L. So, we can draw these circles around x one up to x K. We can actually not just fix the value of, let's say x one and x two, but we can, in order to study x three but we can actually fix the entire depth L boundary here. And it's not going to influence x three. So that's a stronger statement than saying I'm going to fix x one and x two specific values and look at the impact on x three. In fact, something stronger is true, even if I fix this entire ball of radius L. It's not going to influence x three. So this is an immediate consequence of the Gibbs uniqueness property. Okay, so now let's move on to the next item to wants to prove of the main theory, namely the Eisenman Sim star coupling argument. So here's, here's the core of the matter. What we are going to do is we are going to look at the change in that the change in the number of satisfying assignments. If we move from a formula with n variables and random formula with n variables to a random formula with n plus one variables. So how does the number of satisfying assignments change. If I make my system a bit bigger, if I add one more variable, and of course it's adjacent clauses to my random formula, how much is my number of satisfying assignments going to change. And what we are going to prove is that this change is given precisely by the beta free entropy precisely by this crazy expectation of log of some product and so on and so forth. And in fact, in the course of this we are going to see very precisely the combinatorial meaning of this beta free entropy formula. Now, one or two words about this. I put this maximum of partition function and one here to avoid that by accident, the small minority of unsatisfiable formulas formulas without any satisfying assignments, drag this expectation to minus infinity. So just to be sure just to be on the same side I put this maximum of one and set here. And another thing is how this is actually related to the original partition function to the log of set. Well, it's the following trick. And this is actually what I would probably call the Eisenmann Simstar trick or Eisenmann Simstar scheme if you like. So as an immediate implication of this proposition here we can derive a corollary that says that as n goes to infinity one on an expectation long set I mean never mind this max between one and set here that's just a technicality. So the limit as n goes to infinity one on an expectation long set is equal to beta free entropy. How do we see that. Now what we simply do is we write this out here this expectation. We write out as a telescoping some so we just write this expectation here as a difference of changes as we go from a system of size M to a system of size and plus one. Now these individual summons here according to our proposition or converge to be D or converge to the beta free entropy. So if I average them, the result is going to converge to the beta free entropy as well. So that's how I'm getting the corollary out of this proposition. So once we understand the change of our free energy upon increasing the system size by one, we can actually calculate expectation long set. Okay, so how does this Eisenmann Simstar scheme work. How do we pull off this. How do we prove the proposition up here. Well, we use a coupling argument. And so more precisely we are going to use this two way coupling. Starting from a formula phi n prime, a random two set formula phi n prime that contains almost as many clauses as the random formula of size M. And it contains m prime clauses. So that's by bounded amount less by something like D over to less than the real formula on n variables. So starting from this formula phi n prime here in the middle, we are going to construct phi n on the one side and phi n plus one, the random formula with n plus one variables on the other side. And to be precise, we are going to obtain phi m by simply adding in the missing course or D over to random clauses. So we will supplement. So we are going to add the new clauses to turn fire and prime into fire and on the other side, what we are going to do is we are going to add one variable X n plus one and poison D adjacent clauses that link this new variable with the bulk of the random formula with prime. So that's going to be our coupling on the one side we add the bounded number of random clauses. And on the other side, we add one variable and again, the small number of random clauses. And so we are going to meticulously calculate the change in partition function upon going along this arrow and upon going upon going along that arrow. And then we will take the difference. And if you take the difference between these two quantities, of course, the partition function of the guy in the middle is going to cancel. So we end up with the quantity that we aim to compute. So how do we, how do we do this calculation? What does this computation work? Well, the beautiful thing now is that all we have to do is you only have to control local changes to our random formula. We don't have to look at a very big change. We only add, for example, following this error, we only add a small number of clauses, not a lot of clauses. What we have to do is we have to check out what happens if we add Poisson D over two clauses, how the partition function changes. And if you remember the definition of these partition functions, this actually means that we have to compute the Boltzmann probability. So that's what these brackets are supposed to indicate. So the Boltzmann probability that a random satisfying assignment of phi and prime of this guy up here also happens to satisfy the two new clauses, or the Poisson D over two new clauses. So this is going to tell you how much the partition function changes because all of the satisfying assignments are going to survive that happen to satisfy the additional clauses. So how do we do this calculation here? Well, now we use our spatial mixing property because these clauses that we are adding in here are random. It is very unlikely that the variables that they connect are close together. With overwhelming probability, these two variables that this clause here connects to are going to be far apart. So we can apply our spatial mixing result. And we can say, well, presumably the true values assigned to these two variables are actually stochastically independent or nearly stochastically independent because we already proved thanks to Gibbs uniqueness that there's no long range correlations in our model. So we can write the probability that this particular clause here will be satisfied as well, one minus the probability that both these variables fail to satisfy it. And because of independence, we can write this probability here as a product of probabilities, namely the probability that the first variable fails to satisfy it times the probability that the second variable fails to satisfy. And because the number of clauses that we are adding is so small, the clauses that we are adding are not going to interfere with each other. So this product here simply comes out of the logarithm and turns into a d over two. So we end up with this expression d over two expectation log one minus mu one times mu two. If you remember the formula for the beta free entropy from a few slides back. So it's not so easy to go back with my mouse. So if you. So if you so this is precisely this expression back here. So the formula combinatorial calculation explains this expression here in front. And therefore, using this Eisenman-Sintz-Stahl scheme coupling argument together with the absence of long range correlations, we actually get not just this expression but also a combinatorial understanding of where this expression comes from. We are almost done with the proof of this two sub theorem. There's one ingredient missing. Namely, the missing ingredient is that up to this point I only computed the expectation of log Z of phi. What I still have to show to you is that this convergence here also holds in probability that, in fact, log Z phi concentrates about its expectation. And that I'm going to do tomorrow using the interpolation method. It's not going to take long. It's going to take probably less than 10 minutes to finish this. And after that, I'm going to show you an application of a belief propagation and this cavity method technology to a statistical inference problem, namely to the group testing problem of finding a small number of infected individuals in a large population. So thanks for today. Thanks for your attention and I'm going to stick around to answer any questions. We'll give everyone the possibility to unmute themselves. Now you should have the, you can unmute yourself and we'll give a round of applause for Amin. And now we'll do the usual turning off all the recordings and this way you can stand and now you can feel free to unmute yourself.
 Okay, so what I'm going to do today is I'm going to talk you more precisely, more or  less talk you back to back through the physics intuition and the mathematical corroboration  of the two-set result.  So what we are going to look at is a random two-set formula like we talked about in the  previous lecture.  So we have n Boolean variables and clauses that look like this, propositional clauses  that look like this.  And so we are looking at a random two-set formula with a also dn on two number of clauses.  So the average number of clauses in which a variable appears is just d.  And what we would like to determine is the number of satisfying assignment that such  a formula typically has to be more precise because that number scales exponentially.  We would like to compute the limit as n goes to infinity of 1 on n, knock off number of  satisfying assignments.  And we saw last time that unfortunately something as simple as first and the second moment calculation  go to the trick.  So we need to dig a bit deeper.  And this is where the physics intuition comes in.  And in particular, the favorite toy of our very good friends from physics called belief  propagation.  We already saw that we can turn this random two-set problem into a graph.  On the one side, we have the propositional Boolean variables.  And on the other side, we have the clauses which are constraints that bind variables.  And the colors of the edges between them indicate whether a variable appears in the clause positively  or negatively.  And we already spoke a little bit about the structure of this resulting random graph,  namely, locally, this random graph resembles a Gordon Watson tree.  And in particular, this graph doesn't contain a whole lot of short cycles.  Locally it is tree-like.  And the degrees are bounded.  Obviously the degrees of the clauses are always precisely two.  And the number of neighbors of a specific variable is approximately more so d.  Now we already also spoke about the Boltzmann distribution, which unsurprisingly is the  protagonist of this problem from the physics perspective.  And that's just the uniform distribution on the set of satisfying assignments.  And I'm going to write this built sigma for a sample from this Boltzmann distribution.  Because a built sigma is just a uniformly random satisfying assignment of our formula.  Now the main challenge in this problem is to actually get a handle on the Boltzmann distribution.  And in particular, to understand the marginals of Boltzmann distribution, that is the probability  that under a randomly chosen satisfying assignment, a specific variable is set to the value true.  And the device that physicists came up with in order to get a grip on the Boltzmann distribution  and its marginals is a message passing process called belief propagation.  The messages in this case are associated with the edges of the graph.  And more precisely for any pair of adjacent variables and clauses for any edge of the  factor graph, there's two messages traveling across that edge.  One message goes in the direction from the variable to the clause.  And the other message is going to go in the reverse direction from the clause to the value.  What's the combinatorial meaning of the message from a variable to a clause?  Well, the combinatorial meaning is that this is going to be the marginal of that variable  in the absence of this particular clause.  So what would this variable do if I were to remove this clause from the formula?  So the message is simply the probability that this variable here is set to plus one  or to minus one if I remove this clause here from the graph.  So in particular, it's a probability distribution on plus minus one on the two Boolean values.  How about the message in the reverse direction from a clause to a variable?  The idea is similar, but this time the message from A to X, from for example, A1 to X1, is  simply going to be the marginal of this variable if I remove all the other clauses apart from  A where X appears in.  So in this specific case, the message from A1 to X1 would be the marginal of X1 if I  remove A2.  So in other words, this is effectively the influence of A1 on X1 if I forget everybody  else.  So this is essentially what A1 would like X to do if there was nobody else interfering.  And the nice thing about these messages by comparison to plain old marginals is that  we can actually write a system of self-consistent equations for them.  So we can actually relate these messages to one another through a reasonably conceivable  system of equations.  And these are the so-called belief propagation equations.  These equations essentially express our intuition that in this problem there's no long-range  correlations.  So the gist of it is no long-range correlations.  There's short-range correlations only.  And the short-range correlations can be expressed because of this particular structure that  we introduced for the messages.  And to be more precise, what these equations express is the following.  So suppose I look at a variable X like this one here, and I want to calculate the message  that X sends to some clause A that sits up here.  Then I can hope that there's no correlations between these different influences that come  to X from down below from these three branches down here.  Why can I hope that?  Well, I can hope that because my formula is locally tree-like.  So it is very unlikely that these different branches down here will meet within a short  period of time other than through X itself.  So if I were to remove X from the graph, then there would be a large distance between these  different clauses here and these different variables.  So the only way they interact is presumably, unless there's long-range interactions, through  this variable right up here.  And so this notion, this idea of independence of these different branches is precisely what  we can express in terms of messages.  And this intuition, if you work it out a little bit, tells you that the message that  X sends to A has a product structure.  So it's essentially the product of the influences on X that result from these different branches  down below.  To be precise, because we want our messages to be probability distributions on plus or  minus one, we have to do a normalization.  And I didn't write the normalization.  It's hidden in this proportional symbol here.  And so like I said, these self-consistent equations that link the messages to each other  essentially express the independence of these different branches.  That's for the messages from X, from this variable up here to some other clause that's  maybe somewhere up there.  And we can write even simpler equations, even simpler recurrence relations for the clauses  because each clause only has a single child.  So for the clauses, it turns out that we can actually write the message in this particular  simple form.  Again, there's a normalization missing.  And what this expresses is simply the probability that this variable here is going to satisfy  the clause if I set the variable up here to some particular value sigma.  So I don't expect you to fully grasp these equations in an instant.  You can read up on them later if you care about it.  But like I said, the gist of it is no long-range correlations means I can write down a recurrence  relation that expresses short-range correlations.  And so actually, coming back to the previous slide again, actually, if my formula would  be completely acyclic, if there weren't any cycles in the graph at all, then a simple  inductive argument tells you that these equations are actually 100% spot on.  They are 100% accurate.  And in fact, if you do a bit of induction, you find that on an acyclic formula, on an  acyclic graph, you can even write a formula for the partition function purely in terms  of these messages.  And this formula for the partition function is something called the beta-free entropy  in physics language.  And so this formula is, like I said, 100% accurate if your formula happens to be acyclic.  The graph doesn't contain any cycles at all.  And again, I don't expect you to grasp this completely right here on the spot, but just  bear with me.  And this is something that you can work out essentially as an exercise if there's no cycles.  Now like I said, locally, our formula is acyclic.  Locally, it looks like a tree.  There's few short cycles.  And so we might hope that in the absence of long-range correlations, maybe we are in luck,  and the same formula for the partition function like on a tree still applies in this scenario  here.  And this is what physicists would call the replicastometric answers.  Now one drawback of this formula here is that, unfortunately, it speaks about the specific  messages that visit along the edges of a specific two-sub formula.  And so it seems that in order to calculate this monster here, you would actually have  to first generate your formula and then maybe try and find the fixed point or the solution  to these equations somehow and plug that into this slightly awe-inspiring formula here.  And so obviously, that's not what we want.  What we would like is we would like to be able to write a function that comes just in  terms of the model parameters, in this case, just in terms of the average number of clauses  that a variable appears in.  And so our good friends from physics have a trick up their sleeves for this too.  It is something called density evolution.  And the big idea is to grossly simplify the belief propagation equations along the following  lines.  So suppose I forget about the identities of the edges of my graph.  I don't care anymore which variable precisely is connected to which particular clause and  so on and so forth.  But what I do is I just take the messages, the belief propagation messages on my graph  and I put them into one big back.  And so mathematically, this back is of course called an empirical distribution.  So pi phi is just the empirical distribution of all the messages from variables to clauses  that actually travel along my random formula.  Now given that locally the structure of the graph resembles a Gordon Watson tree, I can  try and actually write down a fixed point equation not for individual messages one by  one, but kind of statistically in distribution for all of this, I mean for this entire empirical  distribution in one sweep.  And so the intuition behind this would be that well, if I forget about the identities  of the variables and clauses, then maybe I can do the following.  A variable in my formula has Poisson d children.  So I just generate a Poisson d variable.  To be more precise, I generate two Poisson d on two variables, one representing the plus  children, the children where my variable appears as a positive literal, and one representing  the remaining minus children.  And then I label under the hypothesis that these messages that come in from down here  below, well, any old messages that travel along the edges of my factor graph, that is,  I'm going to presume that these messages that come in from below are actually independent  samples from this empirical distribution.  So I'm going to presume that actually in some sense, what matters is only the structure  of the graph, only the geometry, how the geometry is distributed and not so much precisely  which variable talks to which particular clause.  And so this is again something where this construction of messages comes in handy because  the message from X to A only essentially cares about the structure that lies on the other  side of X that doesn't involve A.  So maybe because of this particular message construction, this is a sensible thing to write  down.  And so what I'm writing down is, well, the message up here is essentially what I get  if I generate these Poisson variables and stick in samples from my empirical distribution  down below here.  And this means that I'm arriving at this simplified belief propagation version.  That's something called the density evolution equation in physics.  So this is kind of like the belief propagation equation with the numerator and the normalizing  term.  But this time instead of meticulously tracing the incoming messages, I just take independent  samples from this empirical distribution up here.  And what this equation expresses is essentially the self-consistency of belief propagation,  namely that the distribution of the message that I get out when I perform this operation  is precisely pi phi, is precisely the empirical distribution of messages that I stick in.  So you may find this a bit adventurous.  And in fact, that's how many of us felt when we first saw this.  But if you, I mean, it will grow on you.  It's not as outlandish as it might at first seem.  And so the big plus of this is that we get one equation, I mean, one fixed point equation,  admittedly a more complicated fixed point equation because now the objects that we are  talking about in this equation are random variables.  But we get one single equation whose only parameter is a number, namely d.  And so while you're in this mindset, you can also write along similar lines a simplified  version of the beta free entropy in terms of this empirical distribution and along similar  lines like similar reasoning, you see that this complicated free line formula with the  various different logarithms and sums and products and so on and so forth actually simplifies  in terms of this empirical distribution and boils down to this one line formula here.  But these mu i's are independent samples from the probability distribution and again these  d plus and d minus are independent plus or d on two variables.  And so this finally leads to the so-called replicasometric solution or mathematically  speaking replicasometric prediction for the number of satisfying assignments first derived  by Monasson and Zekina in 96.  And so this prediction holds that there's precisely one probability distribution, there's  precisely one distribution on the unit interval that satisfies this stochastic fixed point  equation that satisfies this equation that if you draw independent samples mu i from  pi d you will get a random and apply this formula you will get something out that is  distributed as pi d.  And the prediction is that log Z is actually in the limit as n goes to infinity given by  the beta free entropy that you get if you plug independent samples from this fixed point  distribution into the beta free entropy.  So I mean again let me emphasize that this is quite a bit more complicated than what  we would get from the plane first moment calculation.  And so the big plus of this more elaborate prediction is that it takes into account precisely  the short range effects that take place on this random two-sub formula and it labors  under the assumption that there's no long range effects going.  And what we are going to do next is we are going to turn this prediction into a rigorous  theorem.  So we are going to prove in fact that this stochastic fixed point equation has a unique  solution and that if you draw a bunch of independent samples from this distribution, from this fixed  point distribution you get the number of satisfying assignments out.  Now we prove that, let me show you what the result looks like.  On the right hand side here you see on the x-axis D which ranges between 0 and 2, remember  that the satisfiability threshold occurs at D equals 2.  So there's no satisfying assignments left once D is greater than 2.  The red line that you see here is this function B of D from the previous slide.  So the red line is precisely the beta free entropy applied to our wondrous unique fixed  point distribution.  This blue dotted line here is the formula that you would get from the first moment.  You can see that the blue line and the red line are reasonably close together but remember  this is on an exponential scale, on a logarithmic scale.  So a small difference here actually translates into an exponential factor between the first  moment and the actual number of satisfying assignments.  And something that you can maybe not quite as easily see in this plot is that the blue  dotted line and the red line are never identical for any positive D.  So the first moment is always for any specific D an overestimate of the actual number of  solutions.  So another thing to observe is that like I said the satisfiability threshold occurs at  D equals 2.  At D equals 2 our beta free entropy still has a positive value.  So write the moment before your formula becomes unsatisfiable, it still has an exponential number  of satisfying assignments.  So it falls right off a cliff at the satisfiability threshold.  On the left here what you see is the CDF of this fixed point distribution that comes out  of this equation here for various values of D.  For D equals 1.2 up to 1.9 and what you can see is that this fixed point distribution  is something that is rather non-trivial.  So this is not something that this is not presumably the thing you would first guess.  And the reason is that this probability distribution here captures precisely the possible or the  statistics of the short range correlations in your random two-sub formula up to any finite  correlation length.  And so we obtained this result using a computer calculation using a numerical calculation.  And it turns out that actually this equation here, this fixed point equation converges  rapidly so you can get very good estimates using relatively little computational resources.  Anyway, so this much about the physics prediction, let's now see how we can prove such a thing,  how we can turn this prediction into a theory.  And the proof strategy has four items.  The first item is something that is called the contraction method.  And this is a trick that we are going to use in order to prove that this density evolution  equation possesses a unique solution, that there's a unique way of solving this distributional  equation.  The second stop is going to be spatial mixing.  So we are going to actually prove that in this random two-sub problem, there's no long  range correlations.  And this part of the proof is the core of the matter.  This is where the meat is and where we will have to work the most.  The next step is a coupling argument known as the Eisenman-Sim star scheme.  And here we are going to combine the results of the first two steps in order to prove that  the beta-free, the beta formula, the beta-free entropy actually correctly gives the expectation  of log z phi.  Now in this problem because we are looking at zero temperature at hard constraints that  all simultaneously have to be satisfied, we are going to have to follow this up by another  argument known as the interpolation method that will allow us to prove concentration  of log z.  So I think it's a good idea to maybe take a break at this point before we launch into  the proof, before we actually begin with the contraction method.  So why don't we take five minutes off?  That sounds good.  So if you have any questions feel free to ask them in the chat and I think we'll restart  at 2 p.m.  Do you have access to the chat, I mean?  Yeah, I'm working on it.  Okay, I can just read it out.  Would you briefly say the meaning of the expectation of a random probability measure in the last  two lines of the two slides ago?  This slide right here.  So the expectation right here at the bottom in the beta-free entropy formula.  Right.  Okay, so what this means is, so this means the expectation over everything.  So this probability distribution pi d here is actually not a random probability measure,  but it's a fixed probability measure, namely the unique probability measure so that if  you draw a sample from this measure, which is mu zero, that sample is distributed precisely  like the number that you would obtain if you were to draw independent samples mu i, multiply  them up to an independent Poisson d over 2 variable d plus and then normalize accordingly.  Now this expectation, oops, this expectation down here is the expectation over everything.  So you generate an infinite sequence of independent samples from this distribution.  So these mu i's are an infinite family of samples from pi d and d plus and d minus are  again independent samples from the Poisson d over 2 distribution.  So you just plug in the numbers that you get and you average over everything.  Any other questions?  Yeah, it's looking good.  I think you can go to the proof.  I'm looking a little dark, but I can try to maybe switch.  I'm writing up matters a little.  So did I manage to completely lose everybody?  I think it's good you had just had the one question.  Good.  I'm happy to rumble on if you want me to.  Okay, so we will try to now carry out this program.  Yeah, so that's, in principle, I should say a few words about how this strategy compares to some prior work, not all of which deals with the two sub-proc.  But let me just, let's just cut to the chase. I mean, the main difference really is that here we are talking about hard constraints, so you want to count assignments that satisfy every single clause simultaneously.  And so that's basically the main difference between this and, for example, work on the easing model on random graphs.  So, like I said, the first step on the agenda is going to be the contraction method. So we want to show that there that this stochastic fixed point equation here.  So, so just out of curiosity, it would be interesting to see how many of you have dealt with stochastic fixed point equations before. I don't know if there's a way of indicating that in the chat, but I will be curious about this.  So if you if you know them from some other context, maybe drop a line in the chat.  Anyway, so we want to show that this stochastic fixed point equation where these new eyes are independent random variables and also the D plus and D minus random variables that this stochastic fixed point equation possesses a unique solution.  And so one thing that is a bit unpleasant about this equation, I mean, even though it's one of the more amenable specimens that you will encounter in the context of the cavity method, one thing that is a bit unpleasant about it is that we have this complicated sum product structure here in the denominator.  And so one trick that is often useful to get rid of this kind of nasty denominators is to look at log likelihood ratios.  So this means that instead of studying the new eyes themselves the messages themselves which are numbers between zero and one.  And what we are going to do is we are going to look at these log likelihood ratios log new I on one minus mu I, and that's a positive or negative real number.  And by going to new I on one minus mu I be immediately get rid of this denominator and we are left with a product of quotients. And so upon taking the log this product turns into a sum.  And so a fixed point equation from the previous slide turns into a sudden into any equation about sums of independent random variables, namely that the random variable eta zero is distributed precisely as a sum of a personal number of independent summons  and has two Rademacher variables si and si prime, and then okay admittedly this log and 10 which are an acquired taste, but at least we have some of independent things so that's maybe something that we can work with and this equation now is precisely equivalent up to this transformation to the equation that we had on the previous slide.  Now what we are going to do is we are going to look at this equation here this fixed point problem here.  And we are going to use some tools from analysis.  In order to solve this fixed point equation. And in particular what we are going to do is we are going to turn the space of probability measures into a complete metric space so that we can apply the fixed point theorems about metric spaces that we know and love.  And it turns out the right space to look in this example is the wastes steins space. And the wastes steins steins space w two of us defined as the space of all probability measures on the real line with a finite second moment.  The metric on the space is this wastes stein metric delta two of row and row prime. And this metric is defined as follows.  So you first take a coupling of these two probability measures so you take one random variable X that is distributed as row and another random variable X prime that is distributed as well prime.  And now these two random variables need not be independent instead they are they live on is on the same probability space. And you try to align them as best as you can. So as to minimize the resulting distance.  And the minimum possible L two distance that you can accomplish in such a way is the wastes stein distance of these two probability measures.  It's a simple exercise to show that this turns the W two space into a complete separable space.  And on the space therefore we have our favorite better fixed point theory, which says the following if you have a contraction from this complete metric space into itself.  That is a map that that decreases distances so if you take if you put two probability distributions row and row prime in and apply your map.  Then the resulting distance is going to be smaller than the distance that you had previously that you started from.  If you have such a map that is a contraction, then this map possesses a unique fixed point.  So that's going to be our tool in order to show that there's a unique solution to this stochastic fixed point equation.  And we will apply this map to our recurrent to our fixed point equation for log likelihood ratios.  And what we are going to show to show is that this map that takes a probability distribution row and maps it to the distribution of this beautiful random variable down here actually is a contraction on the W two space.  So effectively, the uniqueness of the solution to this density evolution equation follows from the Anak fixed point theory.  The proof of this fact the proof of this contraction fact is given on this slide. I'm not going to talk you through it.  It's it's not rocket science.  It's just, as you can see, one, two, three, four, five steps.  Six, okay, six steps.  And none of them is difficult about the most sophisticated tool that you use is the coaching Schwarz inequality.  And at the end of this calculation, you're convinced that your map is a contraction so long as D is less than two.  And in fact, it is.  So in fact, we are assuming that D is less than two, because for the greater than two, there's no satisfying.  Okay, so using the butter fixed point theory and this was a science space. We are now sure that there's only one single solution to our density evolution fixed point equation to this simplified version of belief propagation on the random form.  Let's move on to step two step two is that we are going to show spatial mixing. We are going to show that there's no long range correlations in our formula.  And as an application of this, we will prove this proposition displayed here. If you take any D less than two.  And you look at the empirical distribution of your Boltzmann marginals on your random formula.  So you look at the, so you take all the Boltzmann marginals and you put them into one big bag.  And so that gives you a probability distribution, a discrete probability distribution with support up to end points.  And we will prove that this distribution here converges in the limit as n goes to infinity to the unique solution of your density evolution equation.  So this pi D is the unique solution to the stochastic fixed point equation that we just derived using the Banach fixed point theory.  And what we prove is that as you make n bigger and bigger as you take the number of variables in your formula to infinity, the empirical distribution of the Boltzmann marginals actually converges to this magical fixed point distribution.  Okay, like I said, the main step is going to be spatial mixing. The main step is going to be to prove that if I take two variables in my formula that are far apart from each other, then their joint distribution factorizes.  The true value here doesn't tell me a whole lot about the true value over here.  And in order to prove the spatial mixing property, it turns out that fortunately, we can exclusively work on tree formulas on two set formulas that don't contain any cycles.  Specifically, we can exclusively work on the two set formulas that are described by this gold Watson tree that captures the local structure of my random formula.  So we are going to look at a gold Watson tree that starts at a root variable x zero.  Every variable in this tree spawns a porcelain D number of clauses as offspring.  For each clause we choose with probability one half, whether the variable appears positively or negatively in that clause.  And with every clause spawns obviously a single variable as its child, which again spawns for some D clauses and so on.  And what we are going to do is we are going to look at this gold Watson tree and truncated after L after two L steps for some large number L.  And we are going to investigate how the true value of the root correlates with the true values at the boundary of the tree at the variables at level to L.  And yeah, so what we are going to show is a very strong spatial mixing property known as the Gibbs uniqueness property.  So here is your tree, here is your tree expanded up to level to L and now the Gibbs uniqueness property provides the following.  Suppose I put in any consistent boundary condition on this tree.  So I write down specific true values, blue representing true I think and red representing false.  Any collection of true values for the leaves or for the boundary of this tree that can be extended to a satisfying assignment of the entire tree.  So there must be a way of actually satisfying all the clauses in such a way that the boundary variables get these particular true values.  So suppose I take any, any reasonable any conceivable boundary condition and I plug it in down here.  And now I asked myself, given this boundary condition.  What is the distribution of the true value of the root.  So subject to this boundary condition.  Draw a random satisfying assignment of the tree.  And inspect the distribution of the true value assigned to the root.  So that's some distribution on the true values plus one minus one true and false.  And now I would like you to compare this distribution that you get for particular boundary condition with the free boundary distribution with the distribution that you would get.  If you wouldn't plug in any boundary condition at all if you leave the boundary free you just take a uniformly random uniformly random satisfying assignment of this entire tree formula and inspect the distribution of the true value of Excel.  And what this gives you need this property says is that these two numbers these two marginals are close to each other and actually the distance goes to zero as I make the tree taller and taller.  So for in the limit of large L in the limit of limit of large trees.  You cannot influence the value of the route by plugging in any boundary condition that you like.  You cannot nudge the root out of place with any possible boundary condition.  It's simply not possible.  Now observe that this is a property that purely speaks about trees, but because the local structure of my random to start formula is described precisely by this tree.  This property directly translates to the random to start formula.  It directly implies that if I take a variable x zero in my to start formula and carve out a large depth neighborhood around this formula I draw a circle of radius to L around this variable and now ask, what is the impact.  If I write down specific true values on that on on level to L of this circle that that has a diminishing influence on x zero itself.  And like I said this is simply because the local structure of the formula is described precisely by this tree here.  And right so what we are going to show is that in fact in the random to start problem this gives you need this property always holds.  So the strong spatial mixing property here is always satisfied.  Now, the proof of this is really the core of the matter, and it's not a trivial argument so maybe your first step at this might be that you write down the recurrence that given the boundary condition actually gives you the root marginal.  And in fact you can do that in fact you can write this down meticulously.  And what you end up writing down this way is precisely belief propagation.  So let's start and maybe try take derivatives. So if I change the boundary values, how much this that actually influenced the root. You could try and trace this by using calculus.  And we tried that for quite a while but it doesn't work very well.  So you simply hit the ball and you turns out you hit the ball at equals one more deepers to like we want to accomplish.  And you can try as you could simply try and take a union bound over all the possible boundary conditions. But unfortunately there's quite a few of them.  Maybe in a god Watson tree like this normally the boundary dominates everything.  So the number of possible boundary conditions is rather enormous so that doesn't work either.  What we did instead is or what you can try instead is maybe you can try and recurs and try and try and take recourse to a combinatorial construction.  And I thought that in this problem you can actually construct an extremal boundary condition so you can construct a boundary condition that will maximize the probability for example that that the root gets set to plus one.  How do you do that. Well, it turns out to be more complicated than in many other problems like for example the using model or the hardcore model.  So in this case is you actually have to look at the tree itself in order to come up with this extremal boundary condition. Here's how it works.  Suppose I want to nudge the root variable as much as possible towards plus one. So I want to maximize the probability that the root is assigned to plus one. How do I do that.  Well, I first look at all the clauses where the root appears positively all the clauses where the root appears with a plus sign.  And now these clauses have another child and I'm going to go to that other child.  And I'm going to try and nudge it away from the value that will satisfy this clause as much as I can.  So in order to nudge the root, I have to nudge its children. I have to tell them, try as much as you can to steer clear of the value that will satisfy this clause because if this clause is unsatisfied by the child,  it will ask the root, can you please satisfy me. And that will encourage the root to take the value plus one.  On the other hand, I can look at the minus one children of the root.  And I don't want the root dragged into the minus one direction by this clause here.  So I'm going to look at the child of that clause and I'm going to try and tell this child, well, you know what, whatever you can do to satisfy this clause, do it.  Try and satisfy this clause as much as you can. So I'm going to try and nudge this guy here in the plus one direction, simply so that it tries to satisfy this clause and simply so that this clause doesn't drag plus one in the wrong direction,  leads plus one up here, the straight.  And so you can you can now iterate this process, you can now recurse the same process on these child variables. We have some particular direction in mind that we want to nudge them.  So we are going to pass to their children at in turn and try and nudge them in some particular direction and so on, until we reach the boundary of the tree. And you can prove by an induction that this will actually work and this process will actually give you the boundary condition that maximizes the probability of plus one at the root.  So now in the second step what we would like to do is we would like to take this particular boundary condition that be meticulously constructed in this top down fashion, and now calculate, given this extremal boundary condition, the probability that actually the root is going to be plus one.  Now at first glance, this seems rather challenging because in the process of constructing the boundary condition, we actually had to expose the entire tree we actually had to walk down the tree top to bottom look at every sign in the tree all the children and all the clauses and so on,  in order to reach the extremal boundary condition so it seems that at this point we are actually stuck.  There's no randomness left that could aid us pass this boundary condition back up no.  There's no stochastic process anymore but we are just facing a deterministic problem so at first glance this seems rather hopeless, but at second glance it turns out that actually it isn't.  Actually, you can fold the top down process and the bottom up process into a single recursion into a single message passing equation.  So we can solve these two problems in one sweep. And you can express these two two processes that go hand in hand by a modified version of the density evolution equation that encoded leaf propagation.  And so, again, formulating this equation in log likelihood ratios we end up with this equation here. So, this again is stochastic fixed point equation and it again has the same form that we saw previously, namely that you have the sum of independent random variables.  And the only difference between the previous equation that we had in this one here is that here we have the same sign as I occurring twice. So previously this was an independent random sign.  Now these two signs are identical. And if you work for maybe half an hour or so you will see that this actually corresponds precisely to this construction of the extremal boundary condition.  So all we have to do in other words is we have to show that this fixed point equation here has a unique solution.  And that this unique solution is identical to the solution that we got from the plane density evolution equation that this one here was an independent sign independent of this other guy over here.  And turns out that this is actually correct. And you can use the contraction method again just like we did before a slightly modified version of the same calculation is going to show you that this guy also has a unique fixed point and actually for symmetry reasons it turns out that you can easily check that  pi d the solution of the old density evolution equation also is the unique solution to this fixed point equation here.  So the consequence of this is that this nudging here, even though it gives you the extremal probability, it maximizes the probability that the root is going to be plus one.  Still doesn't move you away from the distribution that you had previously so as a conclusion, we can derive the fact that this problem here in fact has the Gibbs uniqueness property.  So if you make your tree taller and taller, there's no way to construct a boundary condition that will match the root marginal away from the free boundary condition.  Okay, so one coronary one immediate application of this fact is this asymptotic independent statement here.  So what is this saying, this is saying that if you take any K specific variables in your random formula, for example, the first K variables.  Or more generally some you choose K variables in your formula at random and this is for any fixed K for example K is 500.  And you look at the joint probability that these variables these Boolean variables are assigned specific values.  Then this probability here is approximately equal to the product of the individual marginal probability so the true values assigned to a bunch of far away variables in your propositional formula is essentially a product distribution.  How do we how do we see that well we take a large number L we draw a large radius L around each of our variables.  If you choose either the first K variables in our formula or otherwise K random variables.  It's unlikely that they have distance, less than L that there's a pair wise distance less than L. So, we can draw these circles around x one up to x K.  We can actually not just fix the value of, let's say x one and x two, but we can, in order to study x three but we can actually fix the entire depth L boundary here.  And it's not going to influence x three. So that's a stronger statement than saying I'm going to fix x one and x two specific values and look at the impact on x three. In fact, something stronger is true, even if I fix this entire ball of radius L.  It's not going to influence x three. So this is an immediate consequence of the Gibbs uniqueness property.  Okay, so now let's move on to the next item to wants to prove of the main theory, namely the Eisenman Sim star coupling argument.  So here's, here's the core of the matter. What we are going to do is we are going to look at the change in that the change in the number of satisfying assignments.  If we move from a formula with n variables and random formula with n variables to a random formula with n plus one variables.  So how does the number of satisfying assignments change. If I make my system a bit bigger, if I add one more variable, and of course it's adjacent clauses to my random formula, how much is my number of satisfying assignments going to change.  And what we are going to prove is that this change is given precisely by the beta free entropy precisely by this crazy expectation of log of some product and so on and so forth.  And in fact, in the course of this we are going to see very precisely the combinatorial meaning of this beta free entropy formula.  Now, one or two words about this. I put this maximum of partition function and one here to avoid that by accident, the small minority of unsatisfiable formulas formulas without any satisfying assignments, drag this expectation to minus infinity.  So just to be sure just to be on the same side I put this maximum of one and set here.  And another thing is how this is actually related to the original partition function to the log of set.  Well, it's the following trick. And this is actually what I would probably call the Eisenmann Simstar trick or Eisenmann Simstar scheme if you like.  So as an immediate implication of this proposition here we can derive a corollary that says that as n goes to infinity one on an expectation long set I mean never mind this max between one and set here that's just a technicality.  So the limit as n goes to infinity one on an expectation long set is equal to beta free entropy.  How do we see that. Now what we simply do is we write this out here this expectation.  We write out as a telescoping some so we just write this expectation here as a difference of changes as we go from a system of size M to a system of size and plus one.  Now these individual summons here according to our proposition or converge to be D or converge to the beta free entropy.  So if I average them, the result is going to converge to the beta free entropy as well.  So that's how I'm getting the corollary out of this proposition. So once we understand the change of our free energy upon increasing the system size by one, we can actually calculate expectation long set.  Okay, so how does this Eisenmann Simstar scheme work. How do we pull off this. How do we prove the proposition up here.  Well, we use a coupling argument. And so more precisely we are going to use this two way coupling.  Starting from a formula phi n prime, a random two set formula phi n prime that contains almost as many clauses as the random formula of size M.  And it contains m prime clauses. So that's by bounded amount less by something like D over to less than the real formula on n variables.  So starting from this formula phi n prime here in the middle, we are going to construct phi n on the one side and phi n plus one, the random formula with n plus one variables on the other side.  And to be precise, we are going to obtain phi m by simply adding in the missing course or D over to random clauses.  So we will supplement.  So we are going to add the new clauses to turn fire and prime into fire and on the other side, what we are going to do is we are going to add one variable X n plus one and poison D adjacent clauses that link this new variable with the bulk of the random formula with  prime. So that's going to be our coupling on the one side we add the bounded number of random clauses. And on the other side, we add one variable and again, the small number of random clauses.  And so we are going to meticulously calculate the change in partition function upon going along this arrow and upon going upon going along that arrow.  And then we will take the difference. And if you take the difference between these two quantities, of course, the partition function of the guy in the middle is going to cancel.  So we end up with the quantity that we aim to compute.  So how do we, how do we do this calculation? What does this computation work?  Well, the beautiful thing now is that all we have to do is you only have to control local changes to our random formula. We don't have to look at a very big change.  We only add, for example, following this error, we only add a small number of clauses, not a lot of clauses.  What we have to do is we have to check out what happens if we add Poisson D over two clauses, how the partition function changes.  And if you remember the definition of these partition functions, this actually means that we have to compute the Boltzmann probability.  So that's what these brackets are supposed to indicate.  So the Boltzmann probability that a random satisfying assignment of phi and prime of this guy up here also happens to satisfy the two new clauses, or the Poisson D over two new clauses.  So this is going to tell you how much the partition function changes because all of the satisfying assignments are going to survive that happen to satisfy the additional clauses.  So how do we do this calculation here?  Well, now we use our spatial mixing property because these clauses that we are adding in here are random.  It is very unlikely that the variables that they connect are close together.  With overwhelming probability, these two variables that this clause here connects to are going to be far apart.  So we can apply our spatial mixing result.  And we can say, well, presumably the true values assigned to these two variables are actually stochastically independent or nearly stochastically independent because we already proved thanks to Gibbs uniqueness that there's no long range correlations in our model.  So we can write the probability that this particular clause here will be satisfied as well, one minus the probability that both these variables fail to satisfy it.  And because of independence, we can write this probability here as a product of probabilities, namely the probability that the first variable fails to satisfy it times the probability that the second variable fails to satisfy.  And because the number of clauses that we are adding is so small, the clauses that we are adding are not going to interfere with each other.  So this product here simply comes out of the logarithm and turns into a d over two.  So we end up with this expression d over two expectation log one minus mu one times mu two.  If you remember the formula for the beta free entropy from a few slides back.  So it's not so easy to go back with my mouse.  So if you.  So if you so this is precisely this expression back here.  So the formula combinatorial calculation explains this expression here in front.  And therefore, using this Eisenman-Sintz-Stahl scheme coupling argument together with the absence of long range correlations, we actually get not just this expression but also a combinatorial understanding of where this expression comes from.  We are almost done with the proof of this two sub theorem. There's one ingredient missing.  Namely, the missing ingredient is that up to this point I only computed the expectation of log Z of phi.  What I still have to show to you is that this convergence here also holds in probability that, in fact, log Z phi concentrates about its expectation.  And that I'm going to do tomorrow using the interpolation method.  It's not going to take long. It's going to take probably less than 10 minutes to finish this.  And after that, I'm going to show you an application of a belief propagation and this cavity method technology to a statistical inference problem, namely to the group testing problem of finding a small number of infected individuals in a large population.  So thanks for today. Thanks for your attention and I'm going to stick around to answer any questions.  We'll give everyone the possibility to unmute themselves.  Now you should have the, you can unmute yourself and we'll give a round of applause for Amin.  And now we'll do the usual turning off all the recordings and this way you can stand and now you can feel free to unmute yourself.
202007021132-Coja-Oghlan_0_83.png 202007021132-Coja-Oghlan_84_131.png 202007021132-Coja-Oghlan_132_239.png 202007021132-Coja-Oghlan_240_767.png 202007021132-Coja-Oghlan_768_1139.png 202007021132-Coja-Oghlan_1140_2243.png 202007021132-Coja-Oghlan_2244_4091.png 202007021132-Coja-Oghlan_4092_4775.png 202007021132-Coja-Oghlan_4776_9035.png 202007021132-Coja-Oghlan_9036_14747.png 202007021132-Coja-Oghlan_14748_14879.png 202007021132-Coja-Oghlan_14880_15515.png 202007021132-Coja-Oghlan_15516_17219.png 202007021132-Coja-Oghlan_17220_17315.png 202007021132-Coja-Oghlan_17316_18119.png 202007021132-Coja-Oghlan_18120_29339.png 202007021132-Coja-Oghlan_29340_29999.png 202007021132-Coja-Oghlan_30000_30083.png 202007021132-Coja-Oghlan_30084_32375.png 202007021132-Coja-Oghlan_32376_33599.png 202007021132-Coja-Oghlan_33600_34031.png 202007021132-Coja-Oghlan_34032_37523.png 202007021132-Coja-Oghlan_37524_39011.png 202007021132-Coja-Oghlan_39012_39059.png 202007021132-Coja-Oghlan_39060_40223.png 202007021132-Coja-Oghlan_40224_40727.png 202007021132-Coja-Oghlan_40728_40895.png 202007021132-Coja-Oghlan_40896_41171.png 202007021132-Coja-Oghlan_41172_41231.png 202007021132-Coja-Oghlan_41232_41279.png 202007021132-Coja-Oghlan_41280_41327.png 202007021132-Coja-Oghlan_41328_41387.png 202007021132-Coja-Oghlan_41388_41459.png 202007021132-Coja-Oghlan_41460_41519.png 202007021132-Coja-Oghlan_41520_41591.png 202007021132-Coja-Oghlan_41592_41843.png 202007021132-Coja-Oghlan_41844_42719.png 202007021132-Coja-Oghlan_42720_43019.png 202007021132-Coja-Oghlan_43020_43115.png 202007021132-Coja-Oghlan_43116_43271.png 202007021132-Coja-Oghlan_43272_43895.png 202007021132-Coja-Oghlan_43896_43967.png 202007021132-Coja-Oghlan_43968_44195.png 202007021132-Coja-Oghlan_44196_44315.png 202007021132-Coja-Oghlan_44316_45383.png 202007021132-Coja-Oghlan_45384_46595.png 202007021132-Coja-Oghlan_46596_46655.png 202007021132-Coja-Oghlan_46656_47231.png 202007021132-Coja-Oghlan_47232_48107.png 202007021132-Coja-Oghlan_48108_48311.png 202007021132-Coja-Oghlan_48312_49523.png 202007021132-Coja-Oghlan_49524_49631.png 202007021132-Coja-Oghlan_49632_49787.png 202007021132-Coja-Oghlan_49788_52427.png 202007021132-Coja-Oghlan_52428_53759.png 202007021132-Coja-Oghlan_53760_54563.png 202007021132-Coja-Oghlan_54564_56123.png 202007021132-Coja-Oghlan_56124_58487.png 202007021132-Coja-Oghlan_58488_61139.png 202007021132-Coja-Oghlan_61140_67235.png 202007021132-Coja-Oghlan_67236_67283.png 202007021132-Coja-Oghlan_67284_69119.png 202007021132-Coja-Oghlan_69120_80159.png 202007021132-Coja-Oghlan_80160_80291.png 202007021132-Coja-Oghlan_80292_80387.png 202007021132-Coja-Oghlan_80388_80831.png 202007021132-Coja-Oghlan_80832_83591.png 202007021132-Coja-Oghlan_83592_88871.png 202007021132-Coja-Oghlan_88872_89039.png 202007021132-Coja-Oghlan_89040_92291.png 202007021132-Coja-Oghlan_92292_97043.png 202007021132-Coja-Oghlan_97044_97115.png 202007021132-Coja-Oghlan_97116_97199.png 202007021132-Coja-Oghlan_97200_97247.png 202007021132-Coja-Oghlan_97248_97307.png 202007021132-Coja-Oghlan_97308_97379.png 202007021132-Coja-Oghlan_97380_97427.png 202007021132-Coja-Oghlan_97428_97475.png 202007021132-Coja-Oghlan_97476_100007.png 202007021132-Coja-Oghlan_100008_100127.png 202007021132-Coja-Oghlan_100128_100223.png 202007021132-Coja-Oghlan_100224_100283.png 202007021132-Coja-Oghlan_100284_100343.png 202007021132-Coja-Oghlan_100344_100487.png 202007021132-Coja-Oghlan_100488_100679.png 202007021132-Coja-Oghlan_100680_100763.png 202007021132-Coja-Oghlan_100764_100895.png 202007021132-Coja-Oghlan_100896_100937.png