text:
# Asia Pacific Center for Theoretical Physics starts a new LQG group

#### marcus

Gold Member
Dearly Missed
Hanno Sahlmann has announced the formation of a new LQG group, at the APCTP in Korea. There are postdoc and PhD student positions to be filled and he indicates he would like to get them filled by this fall (which is fast approaching!)

sahlmann@particle.skipthis.uni-karlsruhe.andthis.de

Sahlmann is the S in the well-known L.O.S.T theorem which established, under fairly general assumptions, uniqueness of the holonomy/flux state space. If I'm not mistaken, his PhD advisor was Thiemann at the Einstein Institute (the T in L.O.S.T). As I recall, Sahlmann postdoc'd with Ashtekar 2003-2005 and at Utrecht 2006-2008 with Renate Loll. Since 2008 he holds a faculty position at Karlsruhe. It looks like he will lead the new LQG group.

I see that Spires lists PhD advisors:

Several new LQG groups have been established in the past couple of years---and previous groups have added permanent positions. 2008-2010 seems to have been a time of growth for the field. Probably the reasons for this are complicated---I'm not sure there is a single explanation.

To illustrate how many more Lqg venues there are now than there were a few years back, I will copy from Francesca's map. In some cases I think the primary interest of the permanent faculty listed here is in a neighboring field, but I guess it would be possible to do a Loop PhD thesis with almost any of those listed as your advisor.

AEI Berlin
Permanents: Bianca Dittrich, Daniele Oriti, Hermann Nicolai. http://www.aei.mpg.de/english/research/teams/ [Broken]

CPT Marseille
Permanents: Alejandro Perez, Carlo Rovelli, Simone Speziale. http://www.cpt.univ-mrs.fr/~quantumgravity/ Postdocs: Eugenio Bianchi, Muxin Han, Christian Roeken, Antonino Marcianò, Marco Valerio Battis...

LSU
Permanents: Kristina Giesel, Jorge Pullin, Parampreet Singh. http://relativity.phys.lsu.edu/

QG Nottingham
Permanents: John Barrett, Kirill Krasnov, Jorma Louko. http://www.maths.nottingham.ac.uk/research/applied_mathematics/quantum_gravity/ [Broken]
(Affiliated: Ed Copeland http://www.nottingham.ac.uk/physics/research/particles/)

Morelia
Permanents: Alejandro Corichi, Robert Oeckl, José Zapata. http://www.matmor.unam.mx/~corichi/lqgindex.html

PennState
Permanents: Abhay Ashtekar, Martin Bojowald. Postdocs:Claudio Perini,Elena Magliaro,Jacobo Diaz Polo,William Nelson,Simone Mercuri. PhD:Miguel Campiglia, Adam Henderson, Artur Tsobanjan, Edward Wilson...

Erlangen
Permanents: Thomas Thiemann and one more faculty soon! Postdocs: Emanuele Alesci, ..... PhD studens: .....

Perimeter Institute for Theoretical Physics
Permanents: Laurent Freidel, Fotini Markopoulou, Lee Smolin.

Permanents: Fernando Barbero, Guillermo Mena Marugán. Postdoc: Tomasz Pawlowski. http://www.iem.csic.es/departamentos/qft/index.html

University of Warsaw
Permanent: Jerzy Lewandowski. http://www.fuw.edu.pl/~lewand/homepage.html

Beijing Normal University
Permanent: Yongge Ma http://physics.bnu.edu.cn/application/research/gravity/LQG/eng/research.html

Universität Hamburg
Permanent: Catherine Meusburger. http://www.math.uni-hamburg.de/home/meusburger/ Postdoc: Winston Fairbain.

Florida Atlantic University
Permanent: Jonathan Engle, Warner Miller.

École normale supérieure de Lyon
Permanent: Etera Livine

Universite De Paris XI Paris Sud
Permanent: Vincent Rivasseau http://www.rivasseau.com/index.html

Tours
Permanent: Karim Noui

Universite Montpellier II
Permanent: Sergei Alexandrov

Grenoble
Permanent: Aurelien Barreau http://lpsc.in2p3.fr/ams/aurelien/

Cinvestav Zacatenco
Permanent: Merced Montesinos

Montevideo
Permanents: Rodolfo Gambini, Michael Reisenberger.

Cambridge
Permanent: Ruth M. Williams

King's College London

UMC Utrecht
Permanent: Renate Loll http://www.phys.uu.nl/~loll/Web/title/title.html

Niels Bohr Instituttet
Permanent: Jan Ambjorn http://www.nbi.ku.dk/english/

Rheinische Friedrich-Wilhelms-Universität
Permanent: Klaus Kiefer

Permanent: Christian Fleischhack

Haverford College
Permanent: Stephon Alexander. Postdoc:Antonino Marcianò.

Western Ontario
Permanents: Daniel Christensen

McMaster University

New Brunswick
Permanents: Viqar Husain http://www.math.unb.ca/~husain/ [Broken]

University of Lethbridge
Permanents: Saurya Das, Arundhati Dasgupta, Mark Walton. Post-Doc: Wissam Chemissany. Students: Borislav Belchev, Ahmed Farag Ali, Ali Nassar, Steve Sidhu. http://people.uleth.ca/~saurya.das/TPG/TPG.h [Broken]...

Raman Research Institute

University of Sydney/Macquarie University
Permanent: Daniel Terno http://www.qscitech.info/ Postdoc: Florian Girelli

American University of Beirut
Permanent: Tamer Tlas.

Kansas State University
Permanent: Louis Crane. http://www.math.ksu.edu/main/contact_info/personnel_detail?person_id=1330

Riverside

Caltech
Permanent: Matilde Marcolli. http://www.its.caltech.edu/~matilde/

Berkeley
Permanent: Robert Littlejohn. http://www.physics.berkeley.edu/research/faculty/littlejohn.html [Broken]

Pavia
Permanents: Mauro Carfora and Annalisa Marzuoli Students: Hal Haggard and Francesca Vidotto (2011)

Torino
Permanent: Lorenzo Fatibene http://www.dm.unito.it/personalpages/fatibene/index.htm

Sapienza University of Rome
Permanents: Giovanni Montani, Giovanni Amelino Camelia. Giovanni Montani http://www.icra.it/cgm/welcome.htm http://www.roma1.infn.it/~amelino/

Uniwersytet Wrocławski Wydział Fizyki i Astronomii Instytut Fizyki Doświadczalnej
Permanent: Jerzy Kowalski-Glikman.

Uniwersytet Jagielloński Wydział Fizyki Astronomii i Informatyki Stosowanej
Permanent: Marek Szydlowski.

IUCAA Pune

National Cheng Kung University
Permanent: Chopin Soo

Permanent: Hoi-Lai Yu

======================
The information for some of these is only partial. It comes from this map:
In any case, Hanno starting a LQG group at Pohang, Korea is not an isolated example. There seems to be a "Loop diaspora" in progress.

Last edited by a moderator:
Related Beyond the Standard Model News on Phys.org

#### marcus

Gold Member
Dearly Missed
The question came up in another thread "what would it take for Princeton IAS to establish a LQG group?" The question is sociological, but relevant to the progress of science. Science is a community/tradition-based process and can't be understood in isolation from human institutions.

I won't try to answer the "what would it take?" question but it's worth thinking about a related question: how do you recognize a QG research center? Like for example the first item on the above list: AEI Berlin. Also called Einstein Institute at Potsdam (which is just outside Berlin).

I guess the focus needs to be on understanding how change happens. Thiemann just moved from AEI to set up a new QG center at University of Erlangen (famous for Felix Klein's "Erlangen Program" in geometry/group theory). What you see at AEI now is kind of a TEMPLATE or model for what to expect at Erlangen, or at the Asia Pacific center where Thiemann's student Sahlmann is forming a QG group.

Change happens in the list of places which are prominent. For example the heaviest investment in string has been at Princeton and Rutgers. But we hear less and less about Princeton and Rutgers and we hear more and more about AEI, Marseille, Perimeter.

Well Einstein Potsdam has 3 relevant research teams:

Canonical and Covariant Dynamics of Quantum Gravity (7 people, Thiemann's student Dittrich is leader)
http://www.aei.mpg.de/english/research/teams/canonicalCovariantDynamics/index.html [Broken]
http://www.aei.mpg.de/english/research/teams/canonicalCovariantDynamics/members/index.php [Broken]

Microscopic Quantum Structure & Dynamics of Spacetime (8 people, Oriti is the group leader)
http://www.aei.mpg.de/english/research/teams/microscopicQuantumStructure/index.html [Broken]
http://www.aei.mpg.de/english/research/teams/microscopicQuantumStructure/members/index.php [Broken]

Quantum Gravity and Unified Theories (only has two specifically Lqg)
http://www.aei.mpg.de/english/research/teams/quantumGravity/members/index.php [Broken]

The last here used to be the place for the AEI Loop people, before the two new teams were established. It has Baratin, who got his PhD with Freidel, and is now postdoc---and Tambornino, a PhD student of Dittrich. Most of the specifically Lqg people at the Potsdam Einstein Institute are now in the first two research teams.

The point is that one should not be looking for the appearance of institutional set-ups labeled "LQG". Look at the team names:
"dynamics of quantum gravity"
"microscopic dynamics of spacetime"

Whatever it takes for Princeton to set up a LQG research group has already happened, but Princeton is stuck and can't move. In effect, AEI is the new "Princeton IAS". It has taken the lead while the IAS is immobilized by its investment in people who are getting old (and who study stuff that is getting old.)
The new AEI research team titles do not say "LQG". They simply say quantum gravity, or words to that effect. You have to click on the links and look closer to see where it says Lqg, usually in the first paragraph of the mission statement.

Last edited by a moderator:

#### marcus

Gold Member
Dearly Missed
To get a better understanding of how change takes place in Academia we should look at what IAS Princeton is actually doing.
What it looks like is a quiet gradual de-emphasis of string and a shift of their HEP emphasis into phenomology relevant to LHC.

Last year they brought in Nima Arkani-Hamed, and Nima has proposed a program to retrain some young string people and get them into more LHC-relevant research. He got an NSF grant that is partly for that purpose. Here's a November 2009 report on those trends.

== http://www.math.columbia.edu/~woit/wordpress/?p=2447 ==
Since the late eighties, the two institutions in the US most heavily invested in string theory have been Princeton and Rutgers. Recently they have been moving aggressively to try and diversify, especially in the direction of LHC phenomenology, with the hiring of Nima Arkani-Hamed at the IAS and Matt Strassler at Rutgers. Last year the two institutions collaborated on a proposal for a new Physics Frontier Center with a budget of $1 million or so per year. This would be called the PARTICLE Center (Princeton And Rutgers Theory Institute for Collaboration with LHC Experiments) and would aim to be the main US center for LHC phenomenology. The proposal promoted the possibility of experimental anomalies to be discovered by the LHC in fall 2009, quickly followed by PARTICLE physicists inventing a model that would explain the data and predict a subtle effect that would require a new triggering strategy to see. The result of this would be a surprising measurement that would explain supersymmetry breaking. Anyway, that proposal doesn’t appear to have been funded, with reviewers rather dubious about the idea of retraining Princeton and Rutgers string theorists as LHC phenomenologists, as well as the idea of devoting significant new resources to funding the Princeton and Rutgers theory groups, centralizing LHC phenomenology efforts there. However, two new year-long grants for$130,000 each were awarded to Strassler and Arkani-Hamed, who promise to use them to “create the nucleus of an LHC center on the East Coast” at Princeton and Rutgers. One of the goals of these grants is listed as “to help in the process of … retraining postdocs from more formal areas of high-energy theory”, since the job market for young string theorists has more or less collapsed.
==endquote==

The key phrase here is retraining postdocs. Institution inertia has to do with investment in human capital.

Some NEW research centers are poised to take the lead in fundamental physics, and are able to move faster, because they are not so heavily invested in string researchers.
What the older institutions need to work on is gradually shifting emphasis and bit-by-bit redirecting their focus.

Whatever happens in Academia-USA will happen slowly and will not have a visible "LQG" headline.
For example one thing is the slow gain in prestige of a place like Penn State. You saw the funding of a big new intitute there last year: Ashtekar's IGC (Institute for Gravitation and Cosmology.) There is no visible "LQG" flag being waved, but we know the kind of research they do and the people that come out of there. And the place has been gaining in prominence.

Also we have to read the code: what Nima said about getting out of "the more formal areas of high-energy theory" means getting out of string. The older universities with a heavier pre-committment cannot immediately set up new QG groups--that's institutionally too big a jump for their people--first they have to find some way to retrain/redirect the researchers they have already.

Last edited:

#### marcus

Gold Member
Dearly Missed
What are the underlying physical reasons for the rapid expansion of LQG research in the past few years, say since 2005?

I think one important reason is that it has come to be recognized as the leading form of manifold-less QG where one knows how to calculate.

Of course there is no sharp border between LQG/spinfoam and group field theory (as pursued by Oriti's group at the Einstein Institute in Potsdam) and simplicial QG (e.g. Dittrich's group at Potsdam combines both approaches).

The main thing is to have a manifold-less QG where there is enough structure on the table so one can calculate stuff---operator spectra, transition amplitudes, correlations functions, a graviton propagator. There seems to have been a merging of approaches in this direction.

So we can look at the list that Francesca and friends put up on Google---the LQG map--- and see the potential for what is actually a mix of allied manifold-less approaches.

And the question to think about is "why manifold-less?"

It has to do with diff-invariance. I have to go out briefly. Will discuss this later.

#### atyy

And the question to think about is "why manifold-less?"

It has to do with diff-invariance. I have to go out briefly. Will discuss this later.
No.

"LQG is a diffeomorphism invariant theory of fields on manifolds."

http://arxiv.org/abs/0909.0939

#### marcus

Gold Member
Dearly Missed
Something of a cherry-pick In that paper Lewandowski is presenting an excellent valuable result, and finds it convenient to use his own special terminology. He distinguishes between "SFM" (spinfoam models) and what he calls "LQG" which is based on embedded spin-networks. Old LQG.

That was a 2009 paper by Lewandowski et al, but it harks back to much earlier canonical formulations.
Rovelli's April 2010 review is more up-to-date and I will try to adhere to his terminology as much as possible. Hope you will do likewise so we don't talk at cross-purposes so much.

Last edited:

#### marcus

Gold Member
Dearly Missed
This reminds me of an earlier thread where there was some confusion as to what a diffeomorphism is.

A diffeomorphism is simply a smooth 1-1 onto map.

An example would be let the manifold be the real line R with the usual differential structure---usual idea of smooth map.
Let the map be x --> 2x
"multiply every number by 2."

A smooth map does not assume the existence of a metric and has no automatic connection to one if it exists.
So it's obvious that one can add the natural metric to the picture: |x-y|. Let us assume we have that metric and no other.

This example of a diffeomorphism changes the distances between points. In fact it doubles the distances.
(Clearly a diffeo does not have to be linear, so with a more complicated example it could change distances by lots of different ratios.)

You can only say that a diffeomorphism preserves distances if you explicitly specify that the metric is mapped as well. You "take the metric along with you" so to speak. There was, I think, a lot of confused talk recently in one or more threads about diff-invariance. Rather than go back to those threads, I will just develop the ideas I need here. Simpler, and avoids wasting time with sematic bickering.

Last edited:

#### atyy

I think only Markopoulou is working on a manifoldless approach.

Maybe Bianca Dittrich.

I mean, are spin foams manifoldless? I think of them as GFT, which has a manifold.

BTW, since your list of LQG related researchers is so broad - that's ok - did you consider http://arxiv.org/abs/0907.2994 ?

Last edited:

#### marcus

Gold Member
Dearly Missed
...
I mean, are spin foams manifoldless? I think of them as GFT, which has a manifold.
..
I already commented on that in the "Five Principles" thread, at length . When I say manifold-less I mean no manifold representing the spacetime continuum. One can still use Lie groups! Rovelli's April survey of "new LQG" starts right off with cartesian products of copies of SU(2). It's how one does gauge theory on spin-networks (without a spacetime manifold) and how one defines the Hilbert space of LQG states.

#### marcus

Gold Member
Dearly Missed
I guess the point should be made here that General Relativity itself is a prototypical manifold-less theory in the sense that after one does the construction one throws the manifold away.

The gravitational field, in GR, is not a particular metric on a particular manifold. It is an equivalence class of solutions under diffeos. Two given setups (manifold, metric, distribution of matter) are equivalent if there exists a diffeo which maps one to the other (TAKING EVERYTHING ALONG.)

Individual points of the spacetime manifold have no physical significance, nor does any particular manifold---the gravitational field is more abstract than that. It is an abstract geometry--an insubstantial bunch of spatial and temporal relationships.

Since the theory is constructed using a spacetime manifold, people commonly think in terms of some concrete representative of the equivalence class---which works just fine for most things.

However it doesn't work so well when you do QG, because it is wrong at a fundamental philosophical level. There is no spacetime geometry which we can determine any more than there are particle trajectories which we can determine using a finite number of slits and detectors. GR took us partway on the journey and we must begin where GR took us--we begin with the insight GR attained, by discarding the spacetime manifold as gauge.

(It's always possible to go back à la Lewandowski and restore continuity with the past. There are useful theorems to prove and things to discover by hooking the present up with earlier LQG development! But the philosophical basis, and the principal formulation, is manifold-less. Specifically it is a type of manifoldless formulation Rovelli calls "combinatorial.")

I think basically the reason we are seeing rapid growth in LQG since 2005 or 2006 is a spreading realization of the importance of this insight. (Also LQG has made remarkable advances starting in 2008, just technically speaking. That has probably helped.)

Last edited:

#### atyy

So is this philosophically wrong? My own hope is that really it is GFT that is fundamental, but historically, spin foams do come from a spacetime manifold. And of course, manifolds are only defined up to diffeomorphism.

"Spin foam models are discrete versions of a functional integral, usually constructed using a triangulation of the space-time manifold (‘foam’), local variables (‘spins’), and local amplitudes for the simplexes in the triangulation." http://arxiv.org/abs/0907.2440

#### ensabah6

GR took us partway on the journey and we must begin where GR took us--we begin with the insight GR attained, by discarding the spacetime manifold as gauge.
)
do these insights still apply if GR is just an entropic "equation of state"? or, as in string theory, it's just a low-energy quantized spin-2 field of a more complex 11-D M-theory?

Last edited:

#### atyy

or, as in string theory, it's just a low-energy quantized spin-2 field of a more complex 11-D M-theory?
Or AdS/CFT for that matter. Would the Rovellian philosophy predict that the AdS/CFT conjecture will turn out to be false?

#### marcus

Gold Member
Dearly Missed
Would the Rovellian philosophy predict that the AdS/CFT conjecture will turn out to be false?
Certainly not! How can you say such a thing, Atyy! AdS/CFT is a mathematical conjecture concerning differential manifolds! I suspect that it will be proven as a math theorem. Or as several theorems.

One makes the required assumptions and definitions and one (hopefully eventually) can prove the theorem.

It would be naive to imagine that the Poincaré conjecture must be "false" if it turns out that there is some better way than a manifold with metric to represent space and the grav. field!

#### marcus

Gold Member
Dearly Missed
do these insights still apply if GR is just an entropic "equation of state"?...
Yes of course. Ask yourself what "molecules" of geometry underlie the entropy.

#### atyy

Certainly not! How can you say such a thing, Atyy! AdS/CFT is a mathematical conjecture concerning differential manifolds! I suspect that it will be proven as a math theorem. Or as several theorems.

One makes the required assumptions and definitions and one (hopefully eventually) can prove the theorem.

It would be naive to imagine that the Poincaré conjecture must be "false" if it turns out that there is some better way than a manifold with metric to represent space and the grav. field!
But AdS/CFT is a theory of quantum gravity!

So is it actually an instantiation then of Rovellian philosophy? If you look at the CFT - there is no spacetime, only its boundary. In my thinking, AdS/CFT is the reason (well, more a gut feeling) that GFT should be primary. Actually there is some indication that Rovelli might agree! "In this sense, this approach has similarities with the philosophy of the Maldacena duality in string theory: a nonperturbative theory is dual to a more quantum field theory. But here there is no conjecture involved: the duality between certain spin-foam models and certain group field theories is a theorem." http://relativity.livingreviews.org/Articles/lrr-2008-5/ [Broken]

Last edited by a moderator:

#### marcus

Gold Member
Dearly Missed
That's an interesting quote from Rovelli:
"... a nonperturbative theory is dual to a more quantum field theory. But here there is no conjecture involved: the duality between certain spin-foam models and certain group field theories is a theorem." http://relativity.livingreviews.org/Articles/lrr-2008-5/ [Broken]
I don't disagree with what you quote, but my perspective (as retired mathematician) is different from what I think yours is. I tend to keep mathematical theorems separate from physical theories of nature.
I think of the AdS/CFT conjecture as a (not-yet-proven) theorem. The theorem is among other things about manifolds.

As an interesting piece of mathematics, it could be applicable in several different circumstances (wherever the idealization is a good fit) at several different scales. I don't normally take mathematical tools too literally.

In any case AdS/CFT is not the topic here. I'm sure you would agree it's a big subject and needs its own thread.

Last edited by a moderator:

#### marcus

Gold Member
Dearly Missed
I did some organizing and editing on the Google-maps list of LQG "places". I organized it alphabetically by country, and brought it up to date as best I could. I erased some information I thought might be out of date or where a link had gone dead. Can't vouch for everything, but on the whole it matches what I know from other sources.

Basically what it shows is a kind of explosive growth and a "diaspora". The appearance of new centers. A large number of those I first knew of as students and postdocs have moved into permanent positions.

I will get the list.

Francesca and others have compiled a list of people and places where LQG-and-allied research is in progress, or where a PhD student interested in LQG might connect with an advisor. I want to re-organize and edit the list to the best of my knowledge, and bring it up to date as well as I can. (In some cases I can't independently verify but just have to go along with the Google list.)

Australia
University of Sydney/Macquarie University
Permanent: Daniel Terno http://www.qscitech.info/ Postdoc: Florian Girelli

Britain
QG Nottingham
Permanents: John Barrett, Kirill Krasnov, Jorma Louko. http://www.maths.nottingham.ac.uk/research/applied_mathematics/quantum_gravity/ [Broken]
(Affiliated: Ed Copeland http://www.nottingham.ac.uk/physics/research/particles/)

Cambridge
Permanent: Ruth M. Williams

King's College London

Perimeter Institute for Theoretical Physics
Permanent: Laurent Freidel, Fotini Markopoulou, Lee Smolin.

Western Ontario
Permanent: Daniel Christensen

McMaster University

New Brunswick
Permanent: Viqar Husain http://www.math.unb.ca/~husain/ [Broken]

Denmark
Niels Bohr Instituttet
Permanent: Jan Ambjorn http://www.nbi.ku.dk/english/

France
CPT Marseille
Permanent: Alejandro Perez, Carlo Rovelli, Simone Speziale. http://www.cpt.univ-mrs.fr/~quantumgravity/ Postdocs: Eugenio Bianchi, Muxin Han, Christian Roeken, Antonino Marcianò, Marco Valerio Battisti... Students: Roberto Pereira, Valentin Bonzom, Daniele Pranzetti, You Ding, Matteo Smerlak.

École normale supérieure de Lyon
Permanent: Etera Livine. Postdoc: Johannes Tambornino

Universite De Paris XI Paris Sud
Permanent: Vincent Rivasseau http://www.rivasseau.com/2.html

Tours
Permanent: Karim Noui

Universite Montpellier II
Permanent: Sergei Alexandrov

Grenoble
Permanent: Aurelien Barreau http://lpsc.in2p3.fr/ams/aurelien/

Germany
AEI Berlin
Permanent: Bianca Dittrich, Daniele Oriti, Hermann Nicolai. http://www.aei.mpg.de/english/research/teams/ [Broken]
http://www.aei.mpg.de/english/research/teams/canonicalCovariantDynamics/index.html [Broken]

Erlangen
Permanent: Thomas Thiemann and one more faculty soon! Postdocs: Emanuele Alesci, Enrique Fernandez Borja, Derek Wise,...PhD students: Christian Boehmer,... http://theorie3.physik.uni-erlangen.de/people.html

Universität Hamburg
Permanent: Catherine Meusburger. http://www.math.uni-hamburg.de/home/meusburger/ Postdoc: Winston Fairbairn.

Rheinische Friedrich-Wilhelms-Universität
Permanent: Klaus Kiefer

Permanent: Christian Fleischhack

India
Raman Research Institute

IUCAA Pune

Italy
Pavia
Permanent: Mauro Carfora and Annalisa Marzuoli. Students: Hal Haggard and Francesca Vidotto (2011)

Torino
Permanent: Lorenzo Fatibene http://www.dm.unito.it/personalpages/fatibene/index.htm

Sapienza University of Rome
Permanent: Giovanni Montani, Giovanni Amelino Camelia. Giovanni Montani http://www.icra.it/cgm/welcome.htm http://www.roma1.infn.it/~amelino/

Korea
Asia Pacific Center for Theoretical Physics
Permanent: Hanno Sahlmann

Lebanon
American University of Beirut
Permanent: Tamer Tlas.

Mexico
Morelia
Permanent: Alejandro Corichi, Robert Oeckl, José Zapata. http://www.matmor.unam.mx/~corichi/lqgindex.html

Cinvestav Zacatenco
Permanent: Merced Montesinos

Netherlands
University of Utrecht
Permanent: Renate Loll http://www.phys.uu.nl/~loll/Web/title/title.html

People's Republic of China
Beijing Normal University
Permanent: Yongge Ma http://physics.bnu.edu.cn/application/research/gravity/LQG/eng/research.html

Permanent: Hoi-Lai Yu

Poland
University of Warsaw
Permanent: Jerzy Lewandowski. http://www.fuw.edu.pl/~lewand/homepage.html

Uniwersytet Wrocławski (University of Wroclaw)
Permanent: Jerzy Kowalski-Glikman.

Uniwersytet Jagielloński (Jagelonian University)
Permanent: Marek Szydlowski.

Spain
Permanent: Fernando Barbero, Guillermo Mena Marugán. Postdoc: Tomasz Pawlowski. http://www.iem.csic.es/departamentos/qft/index.html

Taiwan
National Cheng Kung University
Permanent: Chopin Soo

United States
PennState
Permanent: Abhay Ashtekar, Martin Bojowald. Postdocs: Andy Randono, Claudio Perini, Elena Magliaro, Jacobo Diaz Polo, William Nelson, Simone Mercuri. PhD:Miguel Campiglia, Adam Henderson, Artur Tsobanjan, Edward Wilson...

Louisiana State University
Permanent: Kristina Giesel, Jorge Pullin, Parampreet Singh. http://relativity.phys.lsu.edu/

Florida Atlantic University
Permanent: Jonathan Engle, Warner Miller

Haverford College
Permanent: Stephon Alexander.

Kansas State University
Permanent: Louis Crane. http://www.math.ksu.edu/main/contact_info/personnel_detail?person_id=1330

Riverside

Caltech
Permanent: Matilde Marcolli. http://www.its.caltech.edu/~matilde/

Uruguay
Montevideo
Permanent: Rodolfo Gambini, Michael Reisenberger
Some of the senior people on the Google-maps list have only tentative association with LQG, but were included for whatever reason. Marcolli is mainly NCG and has only one recent spinfoam paper. Baez main interests are outside QG, as far as I know. He might be willing to advise PhD students in quantum gravity, but I am not sure. Loll and Ambjorn work with simplicial QG---they actually have a rival approach to LQG. Stephon Alexander has co-authored with LQG people in the past but again I don't think LQG is a central interest of his. So the list as we get it off Google contains periferal people. Rivals and alternatives. Actually I don't know how I would have compiled it myself---distinctions are not sharply drawn. But it seems right to me in the main.

Last edited by a moderator:


text:
Robert J. Webber

I am currently a Ph.D. candidate advised by Jonathan Weare at the Courant Institute of Mathematical Sciences.

My goal as a researcher is to uncover the mathematical foundations of Monte Carlo methods in order to optimize their efficiency. In pursuit of this goal, I combine numerical analysis of existing Monte Carlo methods with development of new methods that improve accuracy.

To find out more, check out my curriculum vitae or take a look at the projects below. You can also reach me at rw2515 [AT] nyu [DOT] edu.

## Projects

Monte Carlo methods are needed to identify probabilities of rare, impactful events. However, to estimate a rare probability $$p$$ with just a single digit of accuracy, direct Monte Carlo sampling requires a very large sample size ($$> 100p^{-1}$$). Since generating such a large sample can be prohibitively computationally expensive, are there more practical rare event sampling methods that calculate rare probabilities with reduced sample size requirements?

### Collaborators

Dorian Abbot, David Aristoff, Gideon Simpson, Morgan O'Neill, David Plotkin, and Jonathan Weare.

### Papers

• A splitting method to reduce MCMC variance [arXiv, 2020] [PDF]
I proved that the weighted ensemble method can reduce MCMC's variance by multiple orders of magnitude when calculating the probability of rare events.

• Practical rare event sampling for extreme mesoscale weather [Chaos, 2019] [PDF]
I invented an efficient new rare event sampling algorithm and applied the algorithm to study intense tropical cyclones.

• Unifying sequential Monte Carlo with resampling matrices [arXiv, 2019] [PDF]
I investigated the mathematical properties of resampling schemes, which are an essential ingredient in rare event sampling.

• Maximizing simulated tropical cyclone intensity with action minimization [Journal of Advances in Modeling Earth Systems, 2019] [PDF]
We developed a method that identifies the likeliest pathway to an extreme tropical cyclone event.

In quantum mechanics and the analysis of Markov processes, Monte Carlo methods are needed to identify low-lying eigenfunctions of dynamical generators. The standard Monte Carlo approaches for identifying eigenfunctions, however, can be inaccurate or slow to converge. What limits the efficiency of the currently available spectral estimation methods, and what is needed to build more efficient methods for the future?

### Collaborators

Timothy Berkelbach, Aaron Dinner, Douglas Dow, Samuel Greene, Chatipat Lorpaiboon, Erik Thiede, and Jonathan Weare.

### Papers

• Error bounds for dynamical spectral estimation [SIAM Journal on Mathematics of Data Science, to appear] [arXiv, 2020] [PDF]
I proved the convergence of the leading spectral estimation method in biochemistry, called the "variational approach to conformational dynamics" (VAC), and derived detailed error bounds.

• Integrated VAC: A robust strategy for identifying eigenfunctions of dynamical operators [Journal of Physical Chemistry B, 2020] [PDF]
In this follow-up work, we extended VAC to make it more robust for applications with limited data and flexible neural network approximation spaces.

• Beyond walkers in stochastic quantum chemistry: Reducing error using fast randomized iteration [Journal of Chemical Theory and Computation, 2019] [PDF]
I helped design a Monte Carlo scheme for computing the ground-state energy of small molecules that produced efficiency gains of up to a thousand compared to traditional approaches.

• Improved fast randomized iteration approach to full configuration interaction [Journal of Chemical Theory and Computation, 2020] [PDF]
We recently wrote this second paper which further improved the efficiency of the Monte Carlo scheme.

In many Bayesian inverse problems, Markov chain Monte Carlo (MCMC) methods are needed to approximate distributions on infinite-dimensional function spaces. Yet designing efficient and broadly applicable MCMC methods for function spaces has proved challenging. The available samplers are either inefficient, or they require gradient or covariance information that can be challenging to obtain. This raises the question: are there functional samplers that perform efficiently without requiring any gradient or covariance information?

### Paper

• Ensemble sampler for infinite-dimensional inverse problems [arXiv, 2020] [PDF]
We developed a new sampler for infinite-dimensional inverse problems that outperforms other gradient-free methods.

## Talks

You can hear me talk (virtually) at:

Lastly, here is a talk I gave at SIAM MPE2020 about rare event sampling:

format: plain


text:
# When does the regularity of $A$ implies the regularity of $A[w]$?

Let $A$ be a commutative noetherian ring (I do not mind to assume that $A$ is a UFD), and assume that $A$ is regular.

Recall that a commutative noetherian ring is called regular if all its localizations at maximal ideals are regular local rings.

Let $w$ be algebraic over $A$ (I do not mind to assume that $w$ is integral over $A$. I do NOT want to assume that $w$ is in the field of fractions of $A$), and assume that $A[w]$ is noetherian.

My question: When is $A[w]$ regular? (I suspect there exists a counterexample, even under the additional conditions: $A$ is a UFD, $w$ is integral over $A$).

Notice the following question, which deals with $w$ transcendental over $A$: Does the regularity of $A$ imply the regularity of $A[X]$?

• Some simplifications that don't really answer your question: I think $A$ will automatically be a UFD (Auslander-Buchsbaum) and in particular normal. And certainly $A[w]$ will be Noetherian by the Hilbert basis theorem. – Hoot Jun 11 '15 at 1:35
• Thanks for trying to help. A clarification: In the specific example I have in mind, $A$ is not local but a UFD. (If I am not wrong, generally: A regular ring is normal-- this can be found in Matsumura's book. A regular local ring is a UFD). I thought the Hilbert basis theorem works when $w$ is transcendental over $A$, not algebraic? – user237522 Jun 11 '15 at 1:51
• Thanks! Actually, I have once asked a similar question (in which $A$ is a polynomial ring in two indeterminates): math.stackexchange.com/questions/1287044/… – user237522 Jun 11 '15 at 2:29
• I don't understand your emphasis on $A[w]$ noetherian: AFAIK a regular ring is assumed noetherian (that is, $A$ is noetherian by definition), and I don't think there are many books in CA which miss this condition. – user26857 Jun 11 '15 at 9:02

The nonregular ring $R=k[x,y]/\langle x^2 - y^3\rangle$, which is the coordinate ring of the cusp (not regular at the maximal ideal $\langle x,y\rangle$), is of this form. Indeed, you can set $A:=k[t^2]\cong k[t]$ which is a polynomial ring and then, $R=A[t^3]$. Here, $t^3$ is integral over $A$, but it is not in the field of fractions for reasons of degree.

Geometry: You are basically taking a smooth affine scheme $X$ and then you consider a closed subscheme $Z\subseteq \mathbb A^1_X$ whose projection to $X$ is finite. That closed subscheme may well be singular. However, this is not the case if that finite projection is actually étale, i.e. smooth of relative dimension zero - in this case $Z$ must be smooth. There are several equivalent definitions of being étale, one would be flat and unramified. These are now just properties of the ring extension $A\subseteq A[w]$.

Edit. When you can guarantee flatness and you want to use the above criterion, you have to check the following: For any prime ideal $\mathfrak q\subseteq A[w]$, the prime ideal $\mathfrak p := \mathfrak q\cap A$ (of $A$) generates the maximal ideal of the local ring $A[w]_{\mathfrak q}$. This is the condition for $A\hookrightarrow A[w]$ to be unramified.

• very nice answer, especially the geometric interpretation. One can note that in this case the extension (or the morphism) is not flat. – Parisien Jun 11 '15 at 7:40
• @Jesko Huttenhain: Thanks! What if I know that the extension $A \subset A[w]$ is flat? (in the special example I have in mind, $A[w]$ is actually a free $A$-module). – user237522 Jun 11 '15 at 16:03
• @user237522 In spite of the first comment above, the given example is such $A\subset A[w]$ is flat, in fact even free. (I've thought this is pretty clear from the way I've constructed this example in my answer.) – user26857 Jun 11 '15 at 16:24
• @user26857: That's what I thought...next time I will count on myself. – user237522 Jun 11 '15 at 16:53
• @user237522: I added an explanation of "unramified". I am not sure how easy that is to check, though. – Jesko Hüttenhain Jun 11 '15 at 17:20

If $A$ is regular, then $A[X]$ is regular. Now let $f$ be a monic polynomial in the square of a maximal ideal of $A[X]$. Then $A[X]/(f)=A[w]$ is not regular. (It's worthwhile to mention that $A[w]$ is however CM; see Bruns and Herzog, Proposition 2.2.11.)

Concrete example: $A=k[t]$, and $f(X)=X^2-t^3$. The maximal ideal $\mathfrak m=(t,X)$ has the property $f\in\mathfrak m^2$. (I've chosen this example on purpose, to show that the example given by the other answer is a particular case of the construction I proposed: just replace here $t$ by $t^2$.)

• Thanks! In the special example I have in mind (in which $A$ is a UFD and $A[w]$ is a domain), $A[w]$ is even a complete intersection ring (regular $\subset$ complete intersection $\subset$ Gorenstein $\subset$ Cohen-Macaulay). However, I am not able to show it is regular. Actually it is good enough for me to show that $A[w]$ is integrally closed. – user237522 Jun 11 '15 at 16:18
• @user237522 Please rephrase your comment in such a way I can understand exactly what's the hypothesis and what you want to show. – user26857 Jun 11 '15 at 16:21
• Thank you very much! Now, $A$ is a regular UFD, $w$ is not in the field of fractions of $A$, $w$ is integral over $A$, so $A[w]$ is a finitely generated $A$-module (then by a corollary on page 58 of one of Bourbaki's books, $A[w]$ is a projective $A$-module. But my $A$ is $K[x,y]$, so $A[w]$ is a f.g. free $A$-module, by Quillen-Suslin). I wish to show that $A[w]$ is integrally closed (if I am not wrong, for a domain being normal and integrally closed is the same. If one shows $A[w]$ is regular, then it is normal; however, showing normality is good enough for me). – user237522 Jun 11 '15 at 16:43
• @user237522 "Now, A is a regular UFD, w is not in the field of fractions of A, w is integral over A, so A[w] is a finitely generated A-module. I wish to show that A[w] is integrally closed." As far as I can see you wanted to generalize this to A a regular UFD. I suggest you to ask the question for A = K[X,Y] as a new question, as now we are far from the original one. (I don't understand why you ask a general question if have in mind a clear one.) – user26857 Jun 11 '15 at 18:49
• I admit it was not clear if my question was about a regular UFD $A$, or $A=K[x,y]$. The reason for me asking a more general question than the specific example I have in mind, is that only recently I have started to be interested in regularity, separability, normality etc., so I thought that maybe I am missing some known facts that can be applied to my case. After asking some relevant questions and getting counterexamples, it seems that my specific case needs special attention. – user237522 Jun 11 '15 at 20:02


text:
# C++ 40 seconds to compile a .cpp file - is it totally normal?

## Recommended Posts

In my most complex gameplay source file (single .cpp) with a lot of necessary #include,

... whenever I edit it (e.g. add a single space character), it needs to recompile 40 seconds.

• Is it what to be expected?
• Do you also face this issue?
• Should I just buy a new computer or more RAM?

I am using Visual Studio 2017.  I am not using Unity Build (single compilation unit technique).

Just thinking that the cause is my code, I can't eat and sleep well.  It also induces nightmare at my bedtime. Please help.

##### Share on other sites

How many lines long is it? If it is huge you should refactor into smaller files.

How long is the .cpp file? How much RAM and what CPU do you have?

##### Share on other sites

Compilation depends on many circumstances. First the compiler has to handle your preprocessor directives, these are includes but also anything conditional you define with a # in front. Therefore the preprocessing unit has to resolve all of these statements from top to bottom before anything else can take place.

Every include will be processed, the file will be loaded and added to the process too. After the conditionals are resolved and the preprocessor knows what code to push to the compiler, macro replacement takes place. Any macro definition (so a define with additional arguments required) are resolved recursively wherever you used the definition in code. It is truely recursively until either the preprocessor dosen't find anymore defined identifiers in the macro code or the macro calls itself, then the processor breaks. This steps may happen at the same time, this is preprocessor dependant.

The preprocessor I wrote in C# to detect dependencies between C++ files does all of this on the fly for example.

Templates are resolved (specific code is generated for each template for each different arguments passed to them, this is why templates may cause code bloat) and then the code is pushed finally to the compilation unit.

So to answer your question, it depends: how many include files do you have, how much and complex are the macros you use, how many templates do you use with different arguments. Did you set the include guards correctly (to not include a file twice as you already processed it in this compilation unit) or included more files as necessary, does a simple forward declare can be used instead of the whole header?

By the way, 40 seconds are nothing. Huge projects like game engines (Unreal for example) use so called "Unity Files" where anything is included at once in one file. This is a try to reduce huge build times that may occure else, our Unreal project for example took more than 10 minutes to compile before we toggled it to generate a Unity File.

What I like to do in such cases is to have our custom build tool generate a dependency graph of each include and where it has been used. This not just helps avoid circular dependencies and helps modularizing the project but also shows unnecessary include directives that can cause much higher compile times

##### Share on other sites

• My computer is Intel Core i5-4460 CPU @ 3.20GHZ, memory 8GB, Windows7 64 bit.
• My problematic .cpp is 230 lines.  It has around 30 #includes.    I don't know how to count summation of the line including all in #include. (5000? not sure)
• My program (all=100K line) are currently splited into a lot of header.  Most implementation is in source file (not header).
20 minutes ago, Shaarigan said:

our Unreal project for example took more than 10 minutes to compile before we toggled it to generate a Unity File.

Thank.  How much the recompiling took after you generate the Unity File?

Is the Unity File you mentioned is a part of unity build technique?

##### Share on other sites
2 hours ago, hyyou said:

My problematic .cpp is 230 lines.  It has around 30 #includes.

Ther is some option in Visual Studio, and enabling it lists how inclusion dependencies are resolved, so while compiling it prints all header files in order, and from that you can see unnecessary cycles or something. Helps to fix it.

I think it's this option:

A helpful work around is to make certain files compile faster by using debug build, even if release build is selected.

snippet from @Hodgman

	#if defined _MSC_VER
#define MAKE_DEBUGGABLE __pragma(optimize("", off))
#elif defined __clang__
#define MAKE_DEBUGGABLE _Pragma ("clang optimize off")
#else
#define MAKE_DEBUGGABLE
#endif

With this included, just add MAKE_DEBUGGABLE on top of your slowly compiling files (before or after the includes matters ofc.)

Very helpful also in case debug builds run too slow to be useful.

##### Share on other sites
3 hours ago, hyyou said:

Is the Unity File you mentioned is a part of unity build technique?

To not get any misapprehensions, Unity File dosen't involve anything from Unity3D or Unity Technologies Inc, it is just named like this because it has all dependencies in one file. The only resource I was able to find about it without pointing you to the source code is UnrealBuildTool Build Configuration chapter

Our compile time was reduced to round about 3 minutes after turning Unity Build Mode on

##### Share on other sites

Without seeing code, my guess is that you include unnecessary headers, or else you're using a lot of 'header only' libraries.

You can reduce the number of unnecessary headers by only including those you need, and by using forward declarations (which, for compile safety, can be placed in smaller simpler headers) and making sure you use include guards properly.

Header only libraries make distribution of the library easier, but the cost is increased compilation times.

My next guess is that you're using template-heavy code.  It's going to increase compilation times.  Header only libraries and template-heavy code go hand-in-hand, and both are compile-time performance killers.

Sometimes you jut need to go back to the olden days.  When I was young, compilation could take hours between when you submitted the job at the card reader and when you got the results back at the line printer.  The best time-saving technique was to make sure your code was correct in the first place, a term called 'desk checking'.  It seems modern technology is expanding to consume all of the time- and labour-saving convenience it has introduced.

##### Share on other sites
1 hour ago, JoeJ said:

A helpful work around is to make certain files compile faster by using debug build, even if release build is selected.

Thank!  I set optimization flag (only) of the most-frequently-changed project to false, and it becomes 25-30 seconds.

It takes some large performance hit, but it is acceptable.      Yeah thank, JoeJ!!

##### Share on other sites
6 hours ago, hyyou said:

In my most complex gameplay source file (single .cpp) with a lot of necessary #include,

... whenever I edit it (e.g. add a single space character), it needs to recompile 40 seconds.

• Is it what to be expected?
• Do you also face this issue?
• Should I just buy a new computer or more RAM?

I am using Visual Studio 2017.  I am not using Unity Build (single compilation unit technique).

Just thinking that the cause is my code, I can't eat and sleep well.  It also induces nightmare at my bedtime. Please help.

8 RAM is a lot. So is 3.2 GHz.

##### Share on other sites
13 hours ago, Acosix said:

8 RAM is a lot. So is 3.2 GHz.

For a dev machine in 2019? Not really. 3.2GHz i5 is fine, but not excessive. 8Gb is definitely on the low side.

That said, for a 320 line file, it should be fine.

## Create an account

Register a new account

• 9
• 56
• 18


text:
Theoretical Analysis of Stochastic Search Algorithms

# Theoretical Analysis of Stochastic Search Algorithms

Per Kristian Lehre
School of Computer Science,
University of Birmingham,
Birmingham, UK
Pietro S. Oliveto
Department of Computer Science,
University of Sheffield,
Sheffield, UK
###### Abstract

Theoretical analyses of stochastic search algorithms, albeit few, have always existed since these algorithms became popular. Starting in the nineties a systematic approach to analyse the performance of stochastic search heuristics has been put in place. This quickly increasing basis of results allows, nowadays, the analysis of sophisticated algorithms such as population-based evolutionary algorithms, ant colony optimisation and artificial immune systems. Results are available concerning problems from various domains including classical combinatorial and continuous optimisation, single and multi-objective optimisation, and noisy and dynamic optimisation. This chapter introduces the mathematical techniques that are most commonly used in the runtime analysis of stochastic search heuristics. Careful attention is given to the very popular artificial fitness levels and drift analyses techniques for which several variants are presented. To aid the reader’s comprehension of the presented mathematical methods, these are applied to the analysis of simple evolutionary algorithms for artificial example functions. The chapter is concluded by providing references to more complex applications and further extensions of the techniques for the obtainment of advanced results.

## 1 Introduction

Stochastic search algorithms, also called randomised search heuristics, are general purpose optimisation algorithms that are often used when it is not possible to design a specific algorithm for the problem at hand. Common reasons are the lack of available resources (e.g., enough money and/or time) or because of an insufficient knowledge of the complex optimisation problem which has not been studied extensively before. Other times, the only way of acquiring knowledge about the problem is by evaluating the quality of candidate solutions.

Well-known stochastic search algorithms are random local search and simulated annealing. Other more complicated approaches are inspired by processes observed in nature. Popular examples are evolutionary algorithms (EAs) inspired by the concept of natural evolution, ant colony optimisation (ACO) inspired by ant foraging behaviour and artificial immune systems (AIS) inspired by the immune system of vertebrates.

The main advantage of stochastic search heuristics is that, being general purpose algorithms, they can be applied to a wide range of applications without requiring hardly any knowledge of the problem at hand. Also, the simplicity for which they can be applied implies that practitioners can use them to find high quality solutions to a wide variety of problems without needing skills and knowledge of algorithm design. Indeed, numerous applications report high performance results which make them widely used in practice. However, through experimental work and applications it is difficult to understand the reasons for these successes. In particular, given a stochastic search algorithm, it is unclear on which kind of problems it will achieve good performance and on which it will perform poorly. Even more crucial is the lack of understanding of how the parameter settings influence the performance of the algorithms. The goal of a rigorous theoretical foundation of stochastic search algorithms is to answer questions of this nature by explaining the success or the failure of these methods in practical applications. The benefits of a theoretical understanding are threefold: (a) guiding the choice of the best algorithm for the problem at hand, (b) determining the optimal parameter settings, and (c) aiding the algorithm design, ultimately leading to the achievement of better algorithms.

Theoretical studies of stochastic optimisation methods have always existed, albeit few, since these algorithms became popular. In particular, the increasing popularity gained by evolutionary and genetic algorithms in the seventies led to various attempts at building a theory for these algorithms. However, such initial studies attempted to provide insights on the behaviour of evolutionary algorithms rather than estimating their performance. The most popular of these theoretical frameworks was probably the schema theory introduced by Holland [13] and made popular by Goldberg [11]. In the early nineties a very different approach appeared to the analysis of evolutionary algorithms and consequently randomised search heuristics in general, driven by the insight that these heuristics are indeed randomised algorithms, albeit general-purpose ones, and as such they should be analysed in a similar spirit to that of classical randomised algorithms [25]. For the last 25 years this field has kept growing considerably and nowadays several advanced and powerful tools have been devised that allow the analysis of the performance of involved stochastic search algorithms for problems from various domains. These include problems from classical combinatorial and continuous optimisation, dynamic optimisation and noisy optimisation. The generality of the developed techniques, has allowed their application to the analyses of several families of stochastic search algorithms including evolutionary algorithms, local search, metropolis, simulated annealing, ant colony optimisation, artificial immune systems, particle swarm optimisation, estimation of distribution algorithms amongst others.

The aim of this chapter is to introduce the reader to the most common and powerful tools used in the performance analysis of randomised search heuristics. Since the main focus is the understanding of the methods, these will be applied to the analysis of very simple evolutionary algorithms for artificial example functions. The hope is that the structure of the functions and the behaviour of the algorithms are easy to grasp so the attention of the reader may be mostly focused on the mathematical techniques that will be presented. At the end of the chapter references to complex applications of the techniques for the obtainment of advanced results will be pointed out for further reading.

## 2 Computational Complexity of Stochastic Search Algorithms

From the perspective of computer science, stochastic search heuristics are randomised algorithms although more general than problem specific ones. Hence, it is natural to analyse their performance in the classical way as done in computer science. From this perspective an algorithm should be correct, i.e., for every instance of the problem (the input) the algorithm halts with the correct solution (i.e., the correct output) and it should be efficient in terms of its computational complexity i.e., the algorithm uses the computational resources wisely. The resources usually considered are the number of basic computations to find the solution (i.e., time) and the amount of memory required (i.e., space).

Differently from problem-specific algorithms, the goal behind general-purpose algorithms such as stochastic search heuristics is to deliver good performance independently of the problem at hand. In other words, a general-purpose algorithm is “correct” if it visits the optimal solution of any problem in finite time. If the optimum is never lost afterwards, then a stochastic search algorithm is said to converge to the optimal solution. In a formal sense the latter condition for convergence is required because most search heuristics are not capable of recognising when an optimal solution has been found (i.e., they do not halt). However, it suffices to keep track of the best found solution during the run of the algorithm, hence the condition is trivial to satisfy. What is particularly relevant and can make a huge difference on the usefulness of a stochastic search heuristic for a given problem is its time complexity. In each iteration the evaluation of the quality of a solution is generally far more expensive than its other algorithmic steps. As a result, it is very common to measure time as the number of evaluations of the fitness function (also called objective function) rather than counting the number of basic computations. Since randomised algorithms make random choices during their execution, the runtime of a stochastic search heuristic to optimise a function is a random variable . The main measure of interest is:

1. The expected runtime : the expected number of fitness function evaluations until the optimum of is found;
For skewed runtime distributions, the expected runtime may be a deceiving measure of algorithm performance. The following measure therefore provides additional information.

2. The success probability in steps : the probability that the optimum is found within steps.

Just like in the classical theory of efficient algorithms the time is analysed in relation to growing input length and usually described using asymptotic notation [3]. A search heuristic is said to be efficient for a function (class) if the runtime grows as polynomial function of the instance size. On the other hand, if the runtime grows as an exponential function, then the heuristic is said to be inefficient. See Figure 1 for an illustrative distinction.

## 3 Evolutionary Algorithms

A general framework of an evolutionary algorithm is the (+) EA defined in Algorithm 1. The algorithm evolves a population of candidate solutions, generally called the parent population. At each generation an offspring population of individuals is created by selecting individuals from the parent population uniformly at random and by applying a mutation operator to them. The generation is concluded by selecting the fittest individuals out of the parents and offspring. Algorithm 1 presents a formal definition.

In order to apply the algorithm for the optimisation of a fitness function , some parameters need to be set. The population size , the offspring population size and the mutation rate . Generally is considered a good setting for the mutation rate. Also, in practical applications a stopping criterion has to be defined since the algorithm does not halt. A fixed number of generations or a fixed number of fitness function evaluations are usually decided in advance. Since the objective of the analysis is to calculate the time required to reach the optimal (approximate) solution for the first time, no stopping condition is required, and one can assume that the algorithms are allowed to run forever. The + symbol in the algorithm’s name indicates that elitist truncation selection is applied. This means that the whole population consisting of both parents and offspring are sorted according to fitness and the best are retained for the next generation. Some criterion needs to be decided in case the best individuals are not uniquely defined. Ties between solutions of equal fitness may be broken uniformly at random. Often offspring are preferred over parents of equal fitness. In the latter case if are set, then the standard (1+1) EA is obtained, a very simple and well studied evolutionary algorithm. On the other hand if some stochastic selection mechanism was used instead of the elitist mechanism and a crossover operator was added as variation mechanism, then Algorithm 1 would become a genetic algorithm (GA) [11]. Given the importance of the (1+1) EA in this chapter, a formal definition is given in Algorithm 2.

The algorithm is initialised with a random bitstring. At each generation a new candidate solution is obtained by flipping each bit with probability . The number of bits that flip can be represented by a binomial random variable where is the number of bits (i.e., the number of trials) and is the probability of a success (i.e. a bit actually flips), while is the probability of a failure (i.e., the bit does not flip). Then, the expected number of bits that flip in one generation is given by the expectation of the binomial random variable, .

The algorithm behaves in a very different way compared to the random local search (RLS) algorithm that flips exactly one bit per iteration. Although the (1+1) EA flips exactly one bit in expectation per iteration, many more bits may flip or even none at all. In particular, the (1+1) EA is a global optimiser because there is a positive probability that any point in the search space is reached in each generation. As a consequence, the algorithm will find the global optimum in finite time. On the other hand, RLS is a local optimiser since it gets stuck once it reaches a local optimum because it only flips one bit per iteration.

The probability that a binomial random variable takes value (i.e., bits flip) is

 Pr(X=j)=(nj)pj(1−p)n−j.

Hence, the probability that the (1+1) EA flips exactly one bit is

 Pr(X=1)=(n1)⋅(1n)⋅(1−1n)n−1=(1−1n)n−1≥1/e≈0.37

So the outcome of one generation of the (1+1) EA is similar to that of RLS only approximately 1/3 of the generations. The probability that two bits flip is exactly half the probability that one flips:

 Pr(X=2) =(n2)(1n)2(1−1n)n−2 =n(n−1)2(1n)2(1−1n)n−2 =12(1−1n)n−1≈1/(2e)

On the other hand the probability no bits flip at all is:

 Pr(X=0)=(n0)(1/n)0⋅(1−1/n)n≈1/e

The latter result implies that in more than 1/3 of the iterations no bits flip. This should be taken into account when evaluating the fitness of the offspring, especially for expensive fitness functions.

In general, the probability that bits flip decreases exponentially with :

 Pr(X=i)=(ni)⋅1ni⋅(1−1n)n−i=1i!⋅(1−1n)n−i≈1i!⋅e

In the worst case all the bits may need to flip to reach the optimum in one step. This event has probability . Since, this is always a lower bound on the probability of reaching the optimum in each generation, by a simple waiting time argument an upper bound of may be derived for the expected runtime of the (1+1) EA on any pseudo-Boolean function . It is simple to design an example trap function for which the algorithm actually requires expected steps to reach the optimum [10]. This simple result further motivates why it is fundamental to gain a foundational understanding of how the runtime of stochastic search heuristics depends on the parameters of the problem and on the parameters of the algorithms.

## 4 Test Functions

Test functions are artificially designed to analyse the performance of stochastic search algorithms when they face optimisation problems with particular characteristics. These functions are used to highlight characteristics of function classes which may make the optimisation process easy or hard for a given algorithm. For this reason they are often referred to as toy problems. The analysis on test functions of simple and well understood structure has allowed the development of several general techniques for the analysis. Afterwards these techniques have allowed to analyse the same algorithms for more complicated problems with practical applications such as classical combinatorial optimisation problems. Furthermore, in recent years several standard techniques originally developed for simple algorithms have been extended to allow the analyses of more realistic algorithms. In this section the test functions that will be used as example functions throughout the chapter are introduced.

The most popular test function is Onemax (x) := which simply counts the number of one-bits in the bitstring. The global optimum is a bitstring of only one-bits. Onemax is the easiest function with unique global optimum for the (1+1) EA [5].

A particularly difficult test function for stochastic search algorithms is the needle-in-a-haystack function. consists of a huge plateau of fitness value zero apart from only one optimal point of fitness value one represented by the bitstring of only one-bits. This function is hard for search heuristics because all the search points apart from the optimum have the same fitness. As a consequence, the algorithms cannot gather any information about where the needle is by sampling search points.

Both Onemax and Needle (as defined above) have the property that the function values only depend on the number of ones in the bitstring. The class of functions with this property is called functions of unitation

 \textscUnitation(x):=f(n∑i=1xi)

Throughout this chapter, functions of unitation will be used as a general example class to demonstrate the use of the techniques that will be introduced. For simplicity of the analysis, the optimum is assumed to be the bitstring of only one-bits.

For the analysis the function of unitation will be divided into three different kinds of sub-blocks: linear blocks, gap blocks and plateau blocks. Each block will be defined by its length parameter (i.e. the number of bits in the block) and by its position parameter (i.e., each block starts at bitstrings with zeroes and ends at bitstrings with zeroes). Given a unitation function it is divided into sub-blocks proceeding from left to right from the all-zeroes bitstring towards the all-ones bitstring. If the fitness increases with the number of ones, then a linear block is created. The linear block ends when the function value stops increasing with the number of ones.

 \textscLinear(|x|)={a|x|+b if k

See Figure 2 for an illustration.

If the fitness function decreases with the number of ones, then a gap block is created. The gap block ends when the fitness value reaches for the first time a higher value than the value at the beginning of the block.

 \textscGap(|x|)={a if n−|x|=k+m0 otherwise.

See Figure 3 for an illustration.

If the fitness remains the same as the number of ones in the bitstrings increases, then a plateau block is created. The block ends at the first point where the fitness value changes.

 \textscPlateau(|x|)={a if k

See Figure 4 for an illustration.

By proceeding from left to right the whole search space is subdivided into blocks. See Figure 5 for an illustration.

Let the unitation function be subdivided into sub-functions , and let be the runtime for an elitist search heuristic to optimise each sub-function . Then by linearity of expectation, an upper bound on the expected runtime of an elitist stochastic search heuristic for the unitation function is:

 E[T]≤E[r∑i=1Ti]=r∑i=1E[Ti].

Hence, an upper bound on the total runtime for the unitation function may be achieved by calculating upper bounds on the runtime for each block separately. Once these are obtained, summing all the bounds yields an upper bound on the total runtime. Attention needs to be put when calculating upper bounds on the runtime to overcome a plateau block when this is followed by a gap block because points straight after the end of the plateau will have lower fitness values, hence will not be accepted. In these special cases, the upper bound for the Plateau block needs to be multiplied by the upper bound for the Gap block to achieve a correct upper bound on the runtime to overcome both blocks. In the remainder of the chapter upper and lower bounds for each type of block will be derived as example applications of the presented runtime analysis techniques. The reader, will then be able to calculate the runtime of the (1+1) EA and other evolutionary algorithms for any such unitation function.

By simply using waiting time arguments it is possible to derive upper and lower bounds on the runtime of the (1+1) EA for the Gap block. Assuming that the algorithm is at the beginning of the gap block then to reach the end it is sufficient to flip zero-bits into one-bits and leave the other bits unchanged. On the other hand it is a necessary condition to flip at least zero-bits because all search points achieved by flipping less than zero-bits have a fitness value of zero and would not be accepted by selection. Given that there are zero-bits available at the beginning of the block, the following upper and lower bounds on the probability of reaching the end of the block follows

 (m+knm)m1e≤(m+km)(1n)m1e≤p≤(m+km)(1n)m≤((m+k)enm)m.

Here the outer inequalities are achieved by using for . Then by simple waiting time arguments, the expected time for the (1+1) EA to optimise a Gap block of length and position is upper and lower bounded by

 (nm(m+k)e)m≤(m+km)−1nm≤E[T]≤enm(m+km)−1≤e(nmm+k)m.

## 5 Tail Inequalities

The runtime of a stochastic search algorithm for a function (class) is a random variable and the main goal of a runtime analysis is to calculate its expectation . Sometimes the expected runtime may be particularly large, but there may also be a high probability that the actual optimisation time is significantly lower. In these cases a result about the success probability within steps, helps considerably the understanding of the algorithm’s performance. In other occasions it may be interesting to simply gain knowledge about the probability that the actual optimisation time deviates from the expected runtime. In such circumstances tail inequalities turn out to be very useful tools by allowing to obtain bounds on the runtime that hold with high probability. An example of the expectation of a random variable and its probability distribution are given in Figure 6.

Given the expectation of a random variable, which often may be estimated easily, tail inequalities give bounds on the probability that the actual random variable deviates from its expectation [25, 24]. The most simple tail inequality is Markov’s inequality. Many strong tail inequalities are derived from Markov’s inequality.

###### Theorem 1 (Markov’s Inequality).

Let be a random variable assuming only non-negative values. Then for all ,

 Pr(X≥t)≤E[X]t.

The power of the inequality is that no knowledge about the random variable is required apart from it being non-negative.

Let be a random variable indicating the number of bits flipped in one iteration of the (1+1) EA. As seen in the previous section, one bit is flipped per iteration in expectation, i.e., . One may wonder what is the probability that more than one bit is flipped in one time step. A straightforward application of Markov’s Inequality reveals that in at least half of the iterations either one bit is flipped or none:

 Pr(X≥2)≤E[X]2=12

Similarly, one may want to gain some information on how many ones are contained in the bitstring at initialisation, given that in expectation there are (here is a binomial random variable with parameters and ). An application of Markov’s inequality yields that the probability of having more than ones at initialisation is bounded by

 Pr(X≥(2/3)n)≤E[X](2/3)n=n/2(2/3)n=3/4 (1)

Since is binomially distributed it is reasonable to expect that, for large enough , the actual number of obtained ones at initialisation would be more concentrated around the expected value. In particular while the bound is obviously correct, the probability that the initial bitstring has more than ones is much smaller than . However, to achieve such a result more information about the random variable should be required by the tail inequality (i.e., that it is binomially distributed). An important class of tail inequalities used in the analysis of stochastic search heuristics are Chernoff bounds.

###### Theorem 2 (Chernoff Bounds).

Let be independent random variables taking values in . Define , which has expectation .

• for .

• for .

An application of Chernoff bounds reveals that the probability that the initial bitstring has more than one-bits is exponentially small in the length of the bitstring. Let be the random variable summing up the random values of each of the bits. Since each bit is initialised with probability , it holds that and . By fixing it follows that and finally by applying inequality (b),

 Pr(X>(2/3)n)≤(e1/3(4/3)4/3)n/2<(2930)n/2

In fact an exponentially small probability of deviating from by a constant factor of the search space for any constant may easily be obtained by Chernoff bounds.

## 6 Artificial Fitness Levels (AFL)

The artificial fitness levels technique is a very simple method to achieve upper bounds on the runtime of elitist stochastic optimisation algorithms. Albeit its simplicity, it often achieves very good bounds on the runtime.

The idea behind the method is to divide the search space of size into disjoint fitness-based partitions of increasing fitness such that . The union of these partitions should cover the whole search space and the level of highest fitness should contain the global optimum (or all global optima if there is more than one).

###### Definition 3.

A tuple is an -based partition of if

1. for

For functions of unitation, a natural way of defining a fitness-based partition is to divide the search space into levels, each defined by the number of ones in the bitstring. For the Onemax function, where fitness increases with the number of ones in the bitstring, the fitness levels would be naturally defined as .

### 6.1 AFL - Upper Bounds

Given a fitness-based partition of the search space, it is obvious that an elitist algorithm using only one individual will only accept points of the search space that belong to levels of higher or equal fitness to the current level. Once a new fitness level has been reached, the algorithm will never return to previous levels. This implies that each fitness level has to be left at most once by the algorithm. Since in the worst case all fitness levels are visited, the sum of the expected times to leave all levels is an upper bound on the expected time to reach the global optimum. The artificial fitness levels method simplifies this idea by only requiring a lower bound on the probability of leaving each level rather than asking for the exact probabilities to leave each level.

###### Theorem 4 (Artificial Fitness Levels).

Let be a fitness function, a fitness-based partition of and be lower bounds on the corresponding probabilities of leaving the respective fitness levels for a level of better fitness. Then the expected runtime of an elitist algorithm using a single individual is .

The artificial fitness level method will now be applied to derive an upper bound on the expected runtime of (1+1) EA for the Onemax function. Afterwards, the bound will be generalised to general linear blocks of unitation.

###### Theorem 5.

The expected runtime of the (1+1) EA on Onemax is .

###### Proof.

The artificial fitness levels method will be applied to the partitions defined by the number of ones in the bitstring, i.e., . This means that all bitstrings with ones and zeroes belong to fitness level . For each level , the method requires a lower bound on the probability of reaching any level where . To reach a level of higher fitness it is necessary to increase the number of ones in the bitstring. However, it is sufficient to flip a zero into a one and leave the remaining bits unchanged. Since the probability of flipping a bit is and there are zeroes that may be flipped, a lower bound on the probability to reach a level of higher fitness from level is:

 si≥(n−i)⋅1n⋅(1−1n)n−1≥n−ien

where is the probability of leaving bits unchanged and the inequality follows because for all .

Then by the artificial fitness levels method (Theorem 4),

 E[T(1+1) EA,\textscOnemax]≤m−1∑i=01/si≤n−1∑i=0enn−i=enn∑i=11i=O(nlnn).

###### Theorem 6.

The expected runtime of the (1+1)-EA for a linear block of length ending at position is .

###### Proof.

Apply the artificial fitness levels method where each partition consists of the bitstrings in the block with zeroes. Then the probability of leaving a fitness level is bounded by . Given that at most fitness levels need to be left and that the block starts at position and ends at position , by Theorem 4 the expected runtime is:

 E[T]≤k+m∑i=k+1eni≤enk+m∑i=k+11i≤en(k+m∑i=11i−k∑i=11i)≤enln(m+kk)

### 6.2 AFL - Lower Bounds

Recently Sudholt introduced an artificial fitness levels method to obtain lower bounds on the runtime of stochastic search algorithms [35]. Since lower bounds are aimed for, apart from the probabilities of leaving each fitness level, the method needs to also take into account the probability that some levels may be skipped by the algorithm.

###### Theorem 7.

Consider a fitness function and a fitness-based partition of . Let be the probability of starting in level , be an upper bound on the probability of leaving and be an upper bound on the probability of jumping from level to level . If there exists some such that for all

 pi,j≥χ⋅m−1∑k=jpi,k,

then the expected runtime of an elitist algorithm using a single individual is

 E[TA,f]≥χ⋅m−1∑i=1uim−1∑j=i1sj

The method will first be illustrated for the (1+1) EA on the Onemax function. Afterwards, the result will be generalised to general linear blocks of unitation.

###### Theorem 8.

The expected runtime of the (1+1) EA on Onemax is .

###### Proof.

Apply the artificial fitness levels method on the partitions defined by the number of ones in the bitstring, i.e., . This means that all bitstrings with ones and zeroes belong to fitness level . To apply the artificial fitness levels method, bounds on and need to be derived. An upper bound on the probability of leaving fitness level is simply because it is a necessary condition that at least one zero flips to reach a better fitness level. The bound follows because each bit flips with probability and there are zeroes available to be flipped. In order to obtain an upper bound on , the method requires a lower bound on and an upper bound on . For the lower bound on notice that in order to reach level , it sufficient to flip zeroes out of the zeroes available and leave all the other bits unchanged. Hence the following bound is obtained:

 pij≥(n−ij−i)(1n)j−i(1−1n)n−(j−i)

For an upper bound on the sum, notice that to reach any level from level it is necessary to flip at least zeroes out of the available zeroes. So,

 n−1∑k=jpi,k≤(n−ij−i)(1n)j−i

and for the condition of Theorem 7 is satisfied as follows:

 pi,j≥(1−1n)n−(j−i)⋅n−1∑k=jpi,k≥χ⋅n−1∑k=jpi,k

By Eq. (1), the probability that the initial search point has less than 1-bits is at least

 (2/3)n∑i=1ui≥1−34

The statement of Theorem 7 now yields

 E[TA,f] ≥(1e)⋅n−1∑i=1uin−1∑j=i1sj >(1e)⋅⎛⎝(2/3)n∑i=1ui⎞⎠n−1∑j=(2/3)n1sj ≥(1e)⋅(1−34)n−1∑j=(2/3)nnn−j ≥(n4e)⋅n/3∑j=11j.

It now follows that . ∎

Similarly the following result may also be proved for linear blocks of unitation functions by defining the fitness partitions as for .

###### Theorem 9.

The expected runtime of the (1+1)-EA for a linear block of length ending at position is .

### 6.3 Level-based analysis of non-elitist populations

A weakness with the classical artificial fitness level technique is that it is limited to search heuristics that only keep one solution, such as the (1+1) EA, and it heavily relies on the selection mechanism to use elitism. [4] recently introduced the so-called level-based analysis, a generalisation of fitness level theorems for non-elitist evolutionary algorithms which is also applicable to search heuristics with populations, and using higher arity operators such as crossover.

Their theorem applies to any algorithm that can be expressed in the form of Algorithm 3, such as genetic algorithms [4] and estimation of distribution algorithms UMDA [7]. The main component of the algorithm is a random operator which given the current population returns a probability distribution over the search space . The next population is obtained by sampling individuals independently from this distribution.

In contrast to classical fitness-level theorems, the level-based theorem (Theorem 10) only assumes a partition of the search space , and not an -based partition (see Definition 3). Each of the sets is called a level, and the symbol denotes the set of search points above level . Given a constant , a population is considered to be at level with respect to if and meaning that at least a fraction of the population is in level or higher.

###### Theorem 10 ([4]).

Given any partition of a finite set into non-overlapping subsets , define to be the first point in time that elements of appear in of Algorithm 3. If there exist parameters , , and a constant such that for all , , and it holds

(C1)

(C2)

, and

(C3)

with , and

then

 E[T]≤2cε(mλ(1+ln(1+cλ))+m∑j=11zj).

The theorem provides an upper bound on the expected optimisation time of Algorithm 3 if it is possible to find a partition of the search space and accompanying parameters such that conditions (C1), (C2), and (C3) are satisfied. Condition (C1) requires a non-zero probability of creating an individual in level or higher if there are already at least individuals in level or higher. In typical applications, this imposes some conditions on the variation operator. The condition is analogous to the probability in the artificial fitness level technique. Condition (C2) requires that if in addition there are individuals at level or better, then the probability of producing an individual in level or better should be larger than by a multiplicative factor . In typical applications, this imposes some conditions on the strength of the selective pressure in the algorithm. Finally, condition (C3) imposes minimal requirements on the population size in terms of the parameters above.

As an example application of the level-based theorem, the EA is analysed, which is the non-elitist variant of the EA shown in Algorithm 1. The two algorithms differ in the selection step (line 8) where the new population in EA is chosen as the best individuals out of and breaking ties uniformly at random. While the EA always retains the best individuals in the population (hence the name elitist), the EA always discards the old individuals .

At first sight, it may appear as if the EA cannot be expressed in the form of Algorithm 3. The individuals that are kept in each generation are not independent due to the inherent sorting of the offspring. However, taking a different perspective, the population of the algorithm at time could also be interpreted as the offspring . In this alternative interpretation, the new population is now created by sampling uniformly at random among the best individuals in the population, and applying the mutation operator. The operator in Algorithm 3 can now be defined as in Algorithm 4.

The following lemma will be useful when estimating the probability that the mutation operator does not flip any bit positions.

###### Lemma 11.

For any and , if then

 (1−χn)n≥(1−δ)e−χ.
###### Proof.

Note first that , hence

 (nχ−1)(χ−ln(1−δ))≥n+nδχ−(χ+δ)≥n.

By making use of the fact that and simplifying the exponent as above

 (1−χn)n≥[(1−χn)(n/χ)−1]χ−ln(1−δ)≥(1−δ)e−χ.

The expected optimisation time of the  EA on Onemax can now be expressed in terms of the mutation rate and the problem size assuming some constraints on the population sizes and . The theorem is valid for a wide range of mutation rates . In the classical setting of , the expected optimisation time reduces to .

###### Theorem 12.

The expected optimisation time of the EA with bitwise mutation rate where , and population sizes and satisfying for any constant

 λμ≥(1+δ1−δ)eχ, and λ≥4δ2eχln(24576n(n+1)δ7χ)

on Onemax is for any no more than

 1536nδ5(λln(λ)+eχln(n+2)χ(1−δ))+O(nλ).
###### Proof.

Apply the level-based theorem with the same partitions as in the proof of Theorem 8. Since the parameter is assumed to be some constant , it also holds that the parameters and are positive constants. The parameters and will be chosen later.

To verify that conditions (C1) and (C2) hold for any , it is necessary to estimate the probability that operator produces a search point with one-bits when applied to a population containing at least individuals, each having at least one-bits (formally ). Such an event is called a successful sample.

Condition (C1) asks for bounds for each on the probability that the search point returned by Algorithm 4 contains one-bits. First chose the parameter setting . This parameter setting is convenient, because the selection step in Algorithm 4 always picks an individual among the best individuals in the population. By the assumption that , the algorithm will always select an individual containing at least one-bits for some non-negative integer .

Assume without loss of generality, that the first bit-positions in the selected individual are one-bits, and let , be any of the other bit positions. If there is a zero-bit in position or if , then a successful sample occurs if the mutation operator flips only bit position . If there is a one-bit in position , and if , then the step is still successful if the mutation operator flips none of the bit positions. Since the probability of not flipping a position is higher than the probability of flipping a position, i.e., , the probability of a successful sample is therefore in both cases at least

 (n−j)(χ/n)(1−χ/n)n−1. (2)

By Lemma 11, the probability above is at least The parameter is chosen to be the minimal among these probabilities, i.e. .

Condition (C2) assumes in addition that individuals have fitness or higher. In this case, it suffices that the selection mechanism picks one of the best individuals among the individuals, and that none of the bits are mutated in the selected individual. The probability of this event is at least

 γλμ(1−χ/n)n≥γλμe−χ(1−δ)

Hence, to satisfy condition (C2), it suffices to require that

 γλμexp(−χ)(1−δ)≥γ(1+δ),

which is true whenever

 λμ≥(1+δ1−δ)eχ.

To check condition (C3), notice that , and , hence

 a =δ2(λ/μ)2(1+δ)≥δ2eχ2(1−δ), and acεz∗ ≥δ2χ2ncε=δ7χ1536n

Condition (C3) is now satisfied, because the population size is required to fulfil

 2aln(16macεz∗) ≤4(1−δ)δ2eχln(24576mnδ7χ)≤λ

All conditions are satisfied, and the theorem follows. ∎

### 6.4 Conclusions

The artificial fitness levels method was first described by Wegener [37]. The original method was designed for the achievement of upper bounds on the runtime of stochastic search heuristics using only one individual such as the (1+1) EA. Since then, several extensions of the method have been devised for the analysis of more sophisticated algorithms. Sudholt introduced the method presented in Section 7 for the obtainment of lower bounds on the runtime [35]. In an early study, [38] used a potential function that generalises the fitness level argument of [37] to analyse the (+1) EA. His analysis achieved tight upper bounds on the runtime of the (+1) EA on LeadingOnes and Onemax by waiting for a sufficient amount of individuals of the population to take over a given fitness level before calculating the probability to reach a fitness level of higher fitness. Chen et al. extended the analysis to offspring populations by analysing the (+) EA, also taking into account the take over process [2]. Lehre introduced a general fitness-level method for arbitrary population-based EAs with non-elitist selection mechanisms and unary variation operators [20]. This technique was later generalised further into the level-based method presented in Section 6.3 [4]. The method allows the analysis of sophisticated non-elitist heuristics such as genetic algorithms equipped with mutation, crossover and stochastic selection mechanisms, both for classical as well as noisy and uncertain optimisation [6].

## 7 Drift Analysis

Drift analysis is a very flexible and powerful tool that is widely used in the analysis of stochastic search algorithms. The high level idea is to predict the long term behaviour of a stochastic process by measuring the expected progress towards a target in a single step. Naturally, a measure of progress needs to be introduced, which is generally called a distance function. Given a random variable representing the current state of the process at step , over a finite set of states , a distance function is defined such that if and only if is a target point (e.g., the global optimum). Drift analysis aims at deriving the expected time to reach the target by analysing the decrease in distance in each step, i.e., . The expected value of this decrease in distance, is called the drift. See Figure 8 for an illustration. If the initial distance from the target is and a bound on the drift (i.e., the expected improvement in each step) is known, then bounds on the expected runtime to reach the target may be derived.

The additive drift theorem was introduced to the field of evolutionary computation by He and Yao [12]. The theorem allows to derive both upper and lower bounds on the runtime of stochastic search algorithms. Consider a distance function indicating the current distance, at time , of the stochastic process from the optimum. The theorem simply states that if at each time step , the drift is at least some value (i.e., the process has moved closer to the target) then the expected number of steps to reach the target is at most . Conversely if the drift in each step is at most some value , then the expected number of steps to reach the target is at least .

###### Theorem 13 (Additive Drift Theorem).

Given a stochastic process over an interval and a distance function such that if and only if contains the target. Let for all , define , and assume .
Verify the following conditions:

Then,

1. If (C1+) holds for an , then .

2. If (C1) holds for an , then .

An Example application of the additive drift theorem follows concerning the (1+1) EA for plateau blocks of functions of unitation of length positioned such that .

###### Theorem 14.

The expected runtime of the (1+1)-EA for a plateau block of length ending at position is .

###### Proof.

The additive drift theorem will be applied to derive both upper and lower bounds on the expected runtime. The starting point is a bitstring with zeroes and the target point is a bitstring with zeroes. Choose to use the natural distance function that counts the number of zeroes in the bitstring. Subtract from the distance such that target points with zeroes have distance 0 and the initial point has distance . As long as points on the plateau are generated, they will be accepted because all plateau points have equal fitness. Given that each bit flips with probability , and at each step the current search point has zeroes and ones, the drift is

 Δt:=E[Yt−Yt+1∣Yt>0]=Ytn−n−Ytn=2⋅Ytn−1

A lower bound on the drift is obtained by considering that as long as the end of the plateau has not been reached there are always at least zeroes that may be flipped (i.e., ). Accordingly for an upper bound, at most zeroes may be available to be flipped (i.e., ). Hence,

 2kn−1≤Δt≤2(m+k)n−1

Then by additive drift analysis (Theorem 13),

 E[T∣Y0]≤m(2k)/n−1=mn2k−n=O(m)

and

 E[T∣Y0]≥m2(m+k)/n−1=mn2(m+k)−n=Ω(m)

where the last equalities hold as long as . ∎

Note again that if the plateau block is followed by a gap block, then an upper bound on the expected time to optimise both blocks is achieved by multiplying the upper bounds obtained for each block. This is necessary because points in the gap will not be accepted by the (1+1) EA.

### 7.2 Multiplicative Drift Theorem

In the additive drift theorem the worst case decrease in distance is considered. If the expected decrease in distance changes considerably in different areas of the search space, then the estimate on the drift may be too pessimistic for the obtainment of tight bounds on the expected runtime.

Drift analysis of the (1+1) EA for the classical Onemax function will serve as an example of this problem. Since the global optimum is the all-ones bitstring and the fitness increases with the number of ones a natural distance function is which simply counts the number of zeroes in the current search point. Then the distance will be zero once the optimum is found. Points with less one-bits than the current search point will not be accepted by the algorithm because of their lower fitness. So the drift is always positive, i.e., and the amount of progress is the expected number of ones gained in each step. In order to find an upper bound on the runtime, a lower bound on the drift is needed (i.e., the worst case improvement). Such worst case occurs when the current search point is optimal except for one 0-bit. In this case the maximum decrease in distance that may be achieved in a step is and to achieve such progress it is necessary that the algorithm flips the zero into a one and leaves the other bits unchanged. Hence, the drift is

 Δt≥1⋅1n(1−1n)n−1≥1en:=ε

Since the expected initial distance is due to random initialisation, the drift theorem yields

 E[T∣Y0]≤E[Y0]ε=n/21/(en)=e/2⋅n2=O(n2)

In Section 6 it was proven that the runtime of the (1+1) EA for Onemax is , hence a bound of is not tight. The reason is that on functions such as Onemax the amount of progress made by the algorithm depends crucially on the distance from the optimum. For Onemax in particular, larger progress per step is achieved when the current search point has many zeroes that may be flipped. As the algorithm approaches the optimal solution the amount of expected progress in each step becomes smaller because search points have increasingly more one-bits than zero-bits in the bitstring. In such cases a distance function that takes into account these properties of the objective function needs to be used. For Onemax a correct bound is achieved by using a distance function that is logarithmic in the number of zeroes , i.e., where a is added to in the argument of the logarithm such that the global optimum has distance zero (i.e., ). With such distance measure, the decrease in distance when flipping a zero and leaving the rest of the bitstring unchanged is

 ln(i+1)−ln(i)=ln(1+1i)≥12i

where the last inequality holds for all . Since it is sufficient to flip a zero and leave everything else unchanged to obtain an improvement, the drift is

 Δt≥ien⋅12i=12en:=ε

Given that the maximum possible distance is , the drift theorem yields

 E[T]≤Y01/(2en)=2en⋅ln(n+1)=O(nlnn).

The multiplicative drift theorem was introduced as a handy tool to deal with situations as the one described above where the amount of progress depends on the distance from the target.

###### Theorem 15 (Multiplicative Drift Theorem [8]).

Let be random variables describing a Markov process over a finite state space . Let be the random variable that denotes the earliest point in time such that . If there exist such that for all ,

1. and

2. ,

then

 E[T]≤2δ⋅ln(1+cmaxcmin)

The following derivation of an upper bound on the runtime of the (1+1) EA for linear blocks illustrates the multiplicative drift theorem.

###### Theorem 16.

The expected time for the (1+1)-EA to optimise a linear unitation block of length ending at position is

###### Proof.

Let be the number of zero-bits in the bitstring at time step , representing the distance from the end of the linear block. By remembering that increases in distance are not accepted due to elitism, the expected decrease in distance at time step can be bounded by

 E[Xt+1|Xt]≤Xt−1⋅Xten=Xt(1−1en)

simply by considering that if a zero-bit is flipped and nothing else then the distance decreases by 1. Then the drift is:

 E[Xt−Xt+1|Xt]≥Xt−Xt(1−1en)=1enXt:=δXt

By fixing the multiplicative drift theorem yields

 E[T]≤2δ