SLE Revision 4: The Gaussian Free Field and SLE4

I couldn’t resist breaking the order of my revision notes in order that the title might be self-referential. Anyway, it’s the night before my exam on Conformal Invariance and Randomness, and I’m practising writing this in case of an essay question about the Gaussian Free Field and its relation to the SLE objects discussed in the course.

What is a Gaussian Free Field?

The most natural definition is too technical for this context. Instead, recall that we could very informally consider a Poisson random measure to have the form of a series of Poisson random variables placed at each point in the domain, weighted infinitissimely so that the integrals over an area give a Poisson random variable with mean proportional to the measure of the area, and so that different areas are independent. Here we do a similar thing only for infinitesimal centred Gaussians. We have to specify the covariance structure.

We define the Green’s function on a domain D, which has a resonance with PDE theory, by:

We want the covariance structure of the hypothetical infinitesimal Gaussians to be given by . So formally, we define for open A, by a centred Gaussian RV with covariance .

The good news is that we have a nice expression , and the Green’s functions are conformally invariant in the sense that , following directly for conformality of Brownian Motion.

The bad news is that the existence is not clear. The motivation for this is the following though. We have a so-called excursion measure for BMs in a domain D. There isn’t time to discuss this now: it is infinite, and invariant under translations of the boundary (assuming the boundary is , which is fine after taking a conformal map). Then take a Poisson Point Process on the set of Brownian excursions with this measure. Now define a function f on the boundary of the domain dD, and define to be the sum of the values of f at the starting point of BMs in the PPP passing through A, weighted by the time spent in A. We have a universality relation given by the central limit theorem: if we define h to be (in a point limit) the expected value of this variable, and we take n independent copies, we have:

where this limiting random variable is Gaussian.

For now though, we assume existence without full proof.

SLE_4

We consider chordal SLE_k, which has the form of a curve from 0 to in H. The g_t the regularising function as normal, consider for some fixed x. We are interested in the  evolution of the function arg x. Note that conditional on the (almost sure for K<=4) event that x does not lie on the curve, arg x will converge either to 0 or pi almost surely, depending on whether the curve passes to the left or the right (respectively) of x.

By Loewner’s DE for the upper half-plane and Ito’s formula:

So, when K=4, the dt terms vanish, which gives that log X is a local martingale, and so

is a true martingale since it is bounded. Note that

Note that also:

also.

SLE_4 and the Gaussian Free Field on H

We will show that this chordal SLE_4 induces a conformal Markov type of property in Gaussian Free Fields constructed on the slit-domain. Precisely, we will show that if is a GFF on , then , where c is a constant to be determined, and in keeping with the lecturer’s notation!

It will suffice to check that for all fixed p with compact support is a centred Gaussian with variance .

First, applying Ito and conformal invariance of the Green’s functions under the maps g_t,

The details are not particularly illuminating, but exploit the fact that Green’s function on H has a reasonable nice form . We are also being extremely lax with constants, but we have plenty of freedom there.

After applying Ito and some (for now unjustified) Fubini:

and so as we would have suspected (since h(x) was), this is a local martingale. We now deploy Dubins-Schwarz:

for B an independent BM and

So conditional on , we want to make up the difference to . Add to an independent random variable distribution as , where

Then

as desired.

Why is this important?

This is important, or at least interesting, because we can use it to reverse engineer the SLE. Informally, we let in the previous result. This states that taking a GFF in the domain left by removing the whole of the SLE curve (whatever that means) then adding at points on the left of the curve, which is the limit is the same as a normal GFF on the upper half plane added to the argument function. It is reasonable to conjecture that a GFF in a non-connected domain has the same structure as taking independent GFFs in each component, and this gives an interesting invariance condition on GFFs. It can also be observed (Schramm-Sheffield) that SLE_4 arises by reversing the argument – take an appropriate conditioned GFF on H and look for the interface between it being ‘large’ and ‘small’ (Obviously this is a ludicrous simplification). This interface is then, under a suitable limit, SLE_4.

Advertisement

SDEs and L-Diffusions

The motivation for the development of differential calculus by Newton et al. was to enable us to deduce concrete properties of, say, particle motion defined implicitly through ODEs. And we proceed similarly for the stochastic differential. Having defined all the terms through Ito’s formula, and concluded that BM is in some sense the canonical stochastic process, we seek to solve so-called stochastic differential equations of the form:

While there is no reason not to consider processes in , it is reasonable interesting to consider processes in one dimension. As with normal ODEs and PDEs, we have some intuitive notion if we specify some initial conditions, we should be able to set the differential equation up and ‘let it go’ like a functional clockwork mouse. Of course, we are conscious of the potential problems with uniqueness of solutions, stability of solutions, and general mathematical awkwardness that derives from the fact that we can’t treat all DEs as physical systems, with all the luxuries of definiteness that the physical world automatically affords. To establish some concreteness, we set up some definitions.

• For a solution to the SDE, , we require a nice filtration and a BM adapted to that filtration to drive the process , which satisfies , and we require this for each s.t. a.s.
• Uniqueness in law: all solutions to starting from each x have the same law. Obviously, this places no restriction on the underlying probability space and filtration.
• A stronger condition is Pathwise uniqueness: Given the filtration, solutions are almost surely indistinguishable (that is, paths are equal everywhere).
• We have not specified any conditions on the filtration . It would be natural to consider only the minimal such filtration that works. If we can take , the natural filtration of the driving BM, we say the solutions is strong. If every solution is strong, then we have pathwise uniqueness, otherwise we would have a solution where we could choose which path to follow independently of the BM.

The key theorem here is Yamada-Watanabe: If there exist solutions and we have pathwise uniqueness, then we have uniqueness in law. Then for every , and -BM, the unique solution is strong.

Existence of solutions is particularly tractable when are Lipschitz, as this opens the way for implicit constructions as the fixed points of contracting mappings. We make particular use of Gronwall’s lemma, which confirms an intuitive thought that differential inequalities have solutions bounded by solutions to the corresponding ODE. Concretely, for $latex f\geq 0,\,f(t)\leq a+b\int_0^tf(s)ds,\quad 0\leq t\leq T$, the lemma states that . The case a=0 is obviously of particular interest for demonstrating convergence results. We deploy this method to show that when are Lipschitz, the SDE has pathwise uniqueness and for any triple of filtration , -adapted BM, and starting point x, there is a strong solution. Uniqueness in law then follows by Yamada-Watanabe, but we knew this anyway by composing measurable maps.

Now, given L, an operator on functions by:

We define X to be an L-diffusion if X’s local behaviour is specified (in distribution) by L(X). The first sum in the expression for L corresponds to diffusivity, while the second corresponds to (deterministic) drift. Formally, for a, b, bounded a L-diffusion is :

is a martingale.

Alternatively, can relax boundedness condition, and require . To make a link to SDEs, define (so in one dimension ), then solutions to are L-diffusions if boundedness conditions are met. Remember bounded implies Lipschitz implies solutions to SDEs. The result then follows directly from Ito’s formula.

Dubins-Schwarz Theorem

In developing the stochastic integral, much of our motivation has come from considering integrals with respect to Brownian Motion. In this section, we develop some results which justify that Brownian Motion is the canonical stochastic process with non-zero quadratic variation (which is related, but not directly equivalent to the property of infinite total variation). In particular, we shall observe the Dubins-Schwarz theorem, which shows that martingales with unbounded (as time ) quadratic variation ARE Brownian Motion, up to a (stochastic) time change.

Recall Levy’s characterisation of a d-dimensional BM, which allows us to avoid considering independent normal increments. Given :

a BM iff

Obviously, one direction has been shown as part of the construction and properties of quadratic variation. For the other direction,, because laws are precisely defined by characteristic functions, it suffices to show that

We set , and deduce and , and furthermore is bounded on compact [0,t], hence is a true martingale. So which is pretty much what was required.

Now, Dubins-Schwarz states

Theorem: Given almost surely, if we set , then is a -BM, with .

This final result is clear if is almost surely strictly increasing in t: just take in the definition.

We know B is cadlag: we first show B as defined is almost surely continuous. It remains to show , noting that (by continuity) is a stopping time also.

The only interesting case is if , for which need to show [M] is constant. This is intuitively obvious, but formally, we must appeal to which is UI, since . Now may apply OST to obtain which implies M is almost surely constant on . We need to lift this to the case where it holds for all s simultaneously almost surely. Note that cadlag almost surely plus almost surely continuous at each point does not implies almost surely continuous everywhere (eg consider H(U(0,1)) with H the Heaviside function and U a uniform distribution). Instead, we record intervals of constancy of both . That is, we set

Then these are cadlag, and by above a.s. therefore almost surely. Thus M, [M] are constant on the same intervals.

We also check B is adapted to . STP is -measurable for X cadlag adapted. Approximating T discretely from above gives the result, exploiting that the result is clear if T has countable support. Now, obtain , so UI by Doob, so by OST, get , to get B a martingale. The finally:

And so we can apply Levy’s characterisation to finish the result.

Working towards the Ito Isometry

We have defined the stochastic integral for a finite variation, continuous adapted process A, and H a previsible process. We want to extend this to integrals with respect to continuous local martingales. Analogous to defining the Lebesgue integral by extending linearly from indicator functions, we define integrals of simple processes with respect to martingales. A simple process is a disjointly (time-)supported linear combination of the canonical previsible process . It will be convenient to demand that the variables of integration are in . Then the space is preserved under this integral operation, that is , and in particular

By Doob’s inequality, , so it makes sense to define as the set of cadlag adapted processes s.t. . Of particular interest is that is complete, by finding limits for subsequences and lifting to the whole sequence by Fatou.

We aim to construct integrals over by taking limits of integrals over . For this space, we have that is not just but in fact a UI true martingale. Then, as a natural extension of the orthogonality trick (remembering that ), we obtain

We then define for the norm by with the space of H s.t. that this is finite. Then for , we have the Ito isometry:

with

Now, we also have S dense in . Why? We know linear combinations of are dense, so it STP . Use a typical Dynkin’s lemma argument on , which contains -system generating . So extend to generally. We recover the original motivating result that . Take a sequence of stopping times reducing both H and M to force boundedness of integrand, and . Stopping the integral is equivalent to stopping the integrand, and checking limits in stopping times allows us to lift the Ito Isometry result to this one about quadratic variations.

Brownian Motion is not finite variation

There is a natural definition of ‘pathwise’ stochastic integrals of a certain type of ‘simple’ process with respect to cadlag non-decreasing processes. It can be a shown that a function is of finite variation iff it can be expressed as the difference of two such functions. Hence, these finite variation processes can be used as variable of integration via an obvious linear extension. One direction of this result is obvious; the other is fiddly. To proceed, we show that the total valuation process is cadlag (and, obviously, increasing), and then check that are processes satisfying the conditions of the result.

Our overall aim is to define integrals with respect to Brownian Motion since that is (in a sense to be made precise through the Dubins-Schwarz theorem later) the canonical non-trivial stochastic process with non-zero quadratic variation. The result we demonstrate shows that it is not possible to define the integral with respect to BM through pathwise finite variation integrals.

Theorem:  a.s. is of finite variation. Then M is indistinguishable from 0.

We will show this for M a bounded martingale with bounded variation. Why does this suffice? In general, set , noting that V is continuous adapted non-decreasing. If , then we are done, as the s are increasing. But this is a bounded martingale with bounded variation.

To prove this, we make use of the orthogonality relation which is a key trick for this sort of result: If M is a martingale, with , for s<t, then just by multiplying out:

a.s.

Now, for this particular result, we decompose

and then we bound this last term as

Now, as , we have by the boundedness assumption. Furthermore, M is almost surely continuous on [0,t] and so it is in fact uniformly continuous, which allows us to conclude that

By bounded convergence, this limit applies equally under the expectation, and so conclude that for each time t, and so for each time t the martingale is almost surely equal to 0. In the usual, can lift this to rational points by countability, then to all points by continuity.

Loss Networks and Erlang’s Fixed Point

Loss Networks

In Erlang’s telephone line model discussed in the previous post, we considered users competing for a finite set of resources. When insufficient resources are available, the call is lost. A loss network generalises this situation to more complicated resource configurations. We think of links 1, …, J, each with some integer capacity . Each incoming call requires 1 units of each link in some subset of the set of links, and lasts for a time distributed as an exponential random variable with parameter 1, independent of everything else in the model. We call this subset the route, and denote by the incidence matrix of links on routes. Calls arrive as PP()$ independently for each route: no queueing occurs – a call is lost if some link required is operating at full capacity. We call the probability of this event , the loss probability. Observe that , the number of calls on each route r, is a Markov chain on the truncated space .

By checking the DBEs, it is clear that an ED for this Markov chain is proportional to the ED for the MC without the capacity constraint, with state-space restricted to the truncated space. But without capacity constraints, the system is a linear migration process, for which we discovered the form of the ED in the previous section. If we write in the linear migration process, we can compute the acceptance probability for the finite capacity system as:

Approximating Blocking Probabilities

We want to calculate , the equilibrium blocking probability, that a given link j is full. We have two methods: firstly, to find the distribution for with maximum probability, for which the blocking probabilities appear as shadow prices. And secondly, to make a reasonable approximation about blocking independence, and solve explicitly. We want to show that these methods give the same answers.

To maximise the probability on , we take logs and maximise using Stirling’s approximation, which is reasonable as we are implicitly working under a regime where the throughput tends to infinity while preserving ratios.

The primal problem is

which has Lagrangian

We observe that complementary slackness here has the form , and remember that by Strong Duality, which applies here because everything relevant is convex, this equality holds at the primal optimum. Differentiating the Lagrangian at the optimum allows us to specify the optimal x in terms of y:

The dual problem is then to minimise

At this point, we make the suggestive substitution , observing that this gives B non-negative by default since y is non-negative. After further work, we will deduce that these B do indeed have a sensible interpretation as blocking probabilities, but it should be stressed that this is in no way obvious yet. Now complementary slackness asserts:

Note that the primal objective function is strictly convex so as discussed is the unique optimum. The dual objective is strictly convex in , so if A has full rank J, this induces a unique optimum in terms of y. We assume A is full rank (since for example we can perturb slightly) and that there is no degeneracy in the blocking.

Now we consider a sequence of networks with proportionally increasing arrival rates and capacities

Elastic Networks and TCP

Now, suppose each route is given a rate , and there is a utility function . Links have capacities as before, so seek to solve the optimisation problem

This is called the SYSTEM problem. However, the system might not know the utility functions U, or the incidence matrix A. We can alternatively consider the USER problem, where for a given route we assume the cost of the rate is linear, and maximise (utility – cost). That is:

where the constant of linearity has been absorbed into the utility function. For the NETWORK problem, we essentially repeat the system problem, only under the assumption that utility functions are for fixed w. That is

These optimisation problems are linked formally by the following theorem:

Theorem: We can find that solve USER and NETWORK, for which . Furthermore, x then solves SYSTEM.

To prove this result, write down SYSTEM’s Lagrangian . The Lagrangian of NETWORK is similar, and at the optimum of USER, these Lagrangians are in fact the same, with shadow prices for resources and routes respectively.

We discuss two regimes for fairness of allocations:

1) is max-min fair if it is a feasible flow, and if the smallest flow component is as large as possible. That is, if y is another feasible flow, then such that , ie you can’t increase a flow component without taking away from some other component which is smaller to begin with. Such a vector exists if the feasible region is convex, which in all practical examples it ought to be.

2) is proportionally fair if it is feasible, and if for any other feasible vector, the change in the sum, weighted by x is non-positive, that is:

Alternatively, can think of this as saying that the sum of the percentage changes in each component is non-positive. We say the distribution is weighted proportionally fair with respect to w if

Then it can be seen by considering behaviour in a neighbourhood of the optimum of the Lagrangian, that x solves NETWORK iff it weighted proportionally fair.

TCP and Lyapunov functions

Assume rates are controlled by the ODE

where . The motivation is that the increase in flow is linear (we increase it whenever it appears possible) and the decrease is multiplicative (that is, after negative feedback – a sign of failure to transmit a packet – the flow is halved). We seek a so-called Lyapunov function, which is a function of the system monotone along trajectories. In this case, a suitable example is

Such a function is differentiable, and has a unique maximum. Bounding the derivative away from 0 ensures that the maximum is actually attained in every case.

Related articles

• TCP Effective Bandwidth (1) (gkf168.wordpress.com)

Effective Bandwidth

Here, devices have fixed capacity, but packet sizes are random. So, we still have a capacity constraint for the links, but we accept that it won’t be possible to ensure that we stay within those limits all the time, and seek instead to minimise the probability that the limits are exceeded, while keeping throughput as high as possible.

An important result is Chernoff’s Bound: . The proof is very straightforward: apply Markov’s inequality to the non-negative random variable . So in particular , where , and Cramer’s Theorem asserts that after taking a limit in n on the LHS, equality holds, provided .

We assume that the traffic has the form , where these summands are iid, interpreted as one of the loads used on source j. We have

so

so we want this to hold for large .

We might then choose to restrict attention to

So, when operating near capacity, say with call profile n* on (ie near) the boundary of A, with s* the argmin of the above. Then the tangent plane is , and since A’s complement is convex, it suffices to stay on the ‘correct’ side (ie halfspace) of this tangent plane.

We can rewrite as . Note that this is reasonable since s* is fixed, and we call , the effective bandwidth. It is with respect to this average that we are bounding probabilities, hence ‘effective’.

Observe that is increasing by Jensen as for t>1 implies that for t>s, .

In particular,

Models for Random Access Channels

To describe a situation where, for example, mobile phones compete for the use of a satellite for transmitting their messages, we consider a random access network. Here, we assume packets arrive at (necessarily different) stations at Poisson rate , and times of transmissions are discrete. A station will always attempt to transmit a packet which has just arrived, then, if that fails, will retransmit after a time given by a independent random variables. Transmissions fail if at least two stations attempt to use the same window. For the ALOHA protocol, we assume these RVs are geometric with mean . We hope that the backlog, that is the number of stations with packets to retransmit at time t eventually clears. Say is the number of attempts in (t,t+1)$, proportional to where Y is the number of arrivals in (t,t+1), and then .

Then the drift in N is positive once N gets large. This is, however, not enough to prove that the system is transient. Instead we compute p(n), the probability that the channel unjams (that is, an instance where no transmissions are attempted) before the backlog increases, given that the backlog is currently n. We can calculate that this probability is and so . Applying Borel-Cantelli to the record process, that is the times at which the backlog increases, it can be shown that almost surely, the channel unjams only finitely many times.

To maximise throughput, we would take , but of course the individual stations don’t know what n is. However, they could guess. Suppose they view the process and keep a counter:

Then transmission happens with probability , with the idea that S tracks N well, especially when N is large. Observe that

where . So (a,b,c)=(2-e,0,1) for example gives negative S drift when k>1, and positive drift when k<1, which is required to draw S towards N. But S might still diverge asymptotically away from N? We don’t want N to increase too fast when k>1, but

so demanding is what we require when , which is satisfied by the example suggested.

If a station only knows its own transmission attempts, we can use Ethernet, where after r unsuccessful attempts, wait for a time chosen uniformly from . This is called binary exponential backoff. When , get infinitely many successful transmissions almost surely. But for positive recurrence, would have an equilibrium distribution, so by Little’s Law, we can equate arrival and departure rates. Considering the probabilities of 0 and 1 transmissions, obtain

So can be non-recurrent, but have infinitely many successful transmissions!

Braess’s Paradox and Traffic Networks

For a traffic network, we have routes and links as before, only here we specify the delay on a link as a function of the flow along that link , where as before. Then a natural notion of an equilibrium is a distribution of flows such that no customer stands to gain by changing route. Formally, take S the set of source-destination pairs, the incidence matrix of pairs s and routes r, and S(r) the routes between the same source-destination pair as r.

Then define a Wardrop equilibrium to be a flow vector such that for any ,

that is, the delay on this route is less than or equal to the delay on any route between that pair of vertices.

A natural assumption would be that is increasing in for each j, and if we further assume that each is continuously differentiable, then we can prove that a Wardrop Equilibrium exists.

Why? Consider the optimisation problem

where f is the flow requirement. The feasible region is convex and the objective function is convex differentiable so the optimum exists. The Lagrangian is

and at the minimum

So the delay on j, and then

So can interpret as the minimum delay for this route, and so a solution to this problem is a Wardrop Equilibrium. If s are strictly increasing, then have uniqueness in , from the optimisation problem, but not in . For example, you could have two essentially identical routes from A to B, and from B to C, and it then doesn’t matter how you concatenate them to form a flow from A to C.

Note the counterintuitive Braess’s Paradox, where adding a route increasing the size of the delay at the Wardrop Equilibrium. The canonical example can be seen here, where the addition of the road across causes the delay to increase from 83 to 92. And indeed such effects have been observed in ‘real life’ as well.

Note that one explanation for why this seems counter-intuitive is that the objective function isn’t necessarily the most natural one. For a Wardrop equilibrium, the agents are acting entirely selfishly given present information. From the point of view of society, it might make more sense to minimise the average delay . In this case the Lagrangian gives

So if add a congestion charge of to the delay function, the Wardrop Equilibrium becomes equal to the societal optimal. Note that this is NOT the societal optimal for (delay + charge). However, we have seen that a toll will enable selfish behaviour to produce a societal optimum. This is an example of mechanism design, which can be considered a branch of game theory, where the aim is to design systems so that agents work in a societally optimal manner.

Related articles

• Why Blocking Roads Can Speed Up Traffic (measureofdoubt.com)
• So You Want to Reduce Your Costs? Don’t Focus on Cost Reductions (empwaynek.wordpress.com)