In part II, we showed that the class of regularly varying distributions formalizes the notion of “approximately scale-invariant,” just like power-law tails formalize the notion of scale-invariant. The fact that regularly-varying distributions are exactly those distributions that are asymptotically scale-free suggests that they, in a sense, should be able to be analyzed (at least asymptotically) like they are simply power-law distributions. In fact, this can be formalized explicitly, and regularly varying distributions can be analyzed nearly as if they were power-law (Pareto) distributions as far as the tail is concerned. This makes them remarkably easy to work with and highlights that the added generality from working with the class of regularly-varying distributions, as opposed to working specifically with Pareto distributions, comes without too much added complexity.
This is part II in a series on scale invariance, power laws, and regular variation, so you should definitely click on over to part I if you haven’t read that. In part I, we talked about a formalization of the notion of scale invariance and showed that a distribution is scale-invariant if and only if it has a power-law tail. This highlights that scale invariance is a very fragile property that one should not expect to see in reality and, in the strictest sense, that is true. It is quite unusual for the distribution of an observed phenomenon to exactly match a power-law distribution, and thus be scale-invariant. Instead, what tends to be observed in practice is that the body of a distribution is not scale-invariant, and the tail of a distribution is only approximately scale-invariant. Thus, it is natural to focus on distributions that have asymptotically scale-invariant tails, rather than imposing exact scale invariance.
In Part I of this post, we have seen that the optimal power flow (OPF) problem in electricity networks is much more difficult than congestion control on the Internet, because OPF is nonconvex. In Part II, I will explain where the nonconvexity comes from, and how to deal with it.
Source of nonconvexity
Let’s again start with congestion control, which is a convex problem.
As mentioned in Part I, corresponding to each congestion control protocol is an optimization problem, called network utility maximization. It takes the form of maximizing a utility function over sending rates subject to network capacity constraints. The utility function is determined by the congestion control protocol: a different design to adapt the sending rate of a computer to congestion implies a different utility function that the protocol implicitly maximizes. The utility function is always increasing in the sending rates, and therefore, a congestion control protocol tends to push the sending rates up in order to maximize utility, but not to exceed network capacity. The key feature that makes congestion control simple is that the utility functions underlying all of the congestion control protocols that people have proposed are concave functions. More importantly, and in contrast to OPF, the network capacity constraint is linear in the sending rates. This means that network utility maximization is a convex problem.
This is the second series of posts I’m writing on topics related to what we are covering in our book on heavy-tails (which I discussed in an earlier post). The first was on the catastrophe principle (subexponential distributions) and now we move to one of the most commonly discussed aspects of heavy-tailed distributions: power laws and scale invariance.
Scale invariance in our daily lives
In our daily lives, many things that we come across have a typical size, or “scale,” that we associate with them. For example, the ratio of the maximum to minimum heights and weights that we see in a given day is usually less than 3, so none deviates too much from the population average. In contrast, the ratio of the maximum to minimum income of people we see in a particular day may often be 100 or more! This contrast is a consequence of the fact that light-tailed distributions, such as heights and weights, tend to have a “typical scale,” while many heavy-tailed distributions, such as incomes, are “scale invariant,” i.e., regardless of the scale on which you look at them, they look the same.
Upon first encounter, scale invariance is a particularly mysterious aspect of heavy-tailed distributions, since it is natural to think of the average of a distribution as a good predictor of what samples will occur. The fact that this is no longer true for scale invariant distributions leads to counter-intuitive properties. For example, consider the old economics joke: “If Bill Gates walks into a bar, on average, everybody in the bar is a millionaire.”
Though initially mysterious, scale invariance is a beautiful and widely-observed phenomenon that has received attention broadly beyond mathematics and statistics, e.g., in physics, computer
science, and economics.
I have discussed in a previous post that digitization (the representation of information by zeros and ones, and its physical implementation and manipulation) and layering have allowed us to confine the complexity of physics to the physical layer and insulate high-level functionalities from this complexity, greatly simplifying the design and operation of communication networks. For instance, routing, congestion control, search, and ad markets, etc. do not need to deal with the nonlinearity of an optical fiber or a copper wire; in fact, they don’t even know what the underlying physical medium is.
This is not the case for power networks.
The lack of an analogous concept of digitization in power means that we have been unable to decouple the physics (Kirchhoff’s laws) of power flow from high-level functionalities. For instance, we need to deal with power flows not only in deciding which generators should generate electricity when and how much, but also in optimizing network topology, scheduling the charging of electric vehicles, pricing electricity, and mitigating the market power of providers. That is, while the physics of the transmission medium is confined in a single layer in a cyber network, it permeates through the entire infrastructure in a cyber-physical network, and cannot be designed away.
How difficult is it to deal with power flows?
This post (and the one that follows) will illustrate some of these challenges by contrasting the problem of congestion control on the Internet and that of optimal power flow (OPF) in electricity.