Transcript PowerPoint Presentation on Statistical Physics

New science of complexity?
•
•
•
•
Much attention has been given to “complex adaptive
systems” in the last decade.
Popularization of not just information and entropy, but
phase transitions, criticality, fractals, self-similarity,
power laws, chaos, emergence, self-organization, etc.
Aim is to find universal characteristics of complexity.
From Physics: an emphasis on emergent complexity
via self-organization of a homogeneous substrate near
a critical or bifurcation point (SOC/EOC).
Highly
Optimized
Tolerance (HOT)
•
•
•
•
•
Complex systems in biology, ecology, technology,
sociology, economics, …
are driven by design or evolution to highperformance states which are also tolerant to
uncertainty in the environment and components.
This leads to specialized, modular, hierarchical
structures, often with enormous “hidden” complexity,
with new sensitivities to unknown or neglected
perturbations and design flaws.
“Robust, yet fragile!”
“Robust, yet fragile”
• Robust to uncertainties
– that are common,
– the system was designed for, or
– has evolved to handle,
• …yet fragile otherwise
• This is the most important feature of
complex systems (the essence of HOT).
HOT features of ecosystems
• Organisms are constantly challenged by environmental
uncertainties,
• And have evolved a diversity of mechanisms to minimize
the consequences by exploiting the regularities in the
uncertainty.
• The resulting specialization, modularity, structure, and
redundancy leads to high densities and high throughputs,
• But increased sensitivity to novel
perturbations not included in
evolutionary history.
• Robust, yet fragile!
• Complex engineering systems are
similar.
Example: Auto airbags
• Reduces risk in highspeed collisions
• Increases risk otherwise
• Increases risk to small
occupants
• Mitigated by new
designs with greater
complexity
• Could just get a heavier
vehicle
• Reduces risk without the
increase!
• But shifts it elsewhere:
occupants of other
vehicles, pollution
Robustness
Complexity
The simplest possible spatial model of HOT.
Square site
percolation
or
simplified
“forest fire”
model.
Carlson and Doyle,
PRE, Aug. 1999
empty square lattice
occupied sites
not connected
connected clusters
Assume one
“spark” hits the
lattice at a single
site.
A “spark” that hits
an empty site does
nothing.
A “spark” that hits
a cluster causes
loss of that cluster.
Yield = the density after one spark
yield
density
loss
1
no sparks
0.9
“critical point”
0.8
Y=
(avg.)
yield
0.7
0.6
0.5
0.4
N=100
0.3
sparks
0.2
0.1
0
0
0.2
0.4
0.6
0.8
 = density
1
1
0.9
Y=
0.8
(avg.)
yield
0.7
“critical point”
limit
N
0.6
0.5
0.4
0.3
0.2
c = .5927
0.1
0
0
0.2
0.4
0.6
0.8
 = density
1
Y
Fires
don’t
matter.
Cold

Y
Everything burns.
Burned

Critical point
Y

all sites
occupied
Percolation
P( ) =
probability a site
is on the  cluster
1
P( )
critical
point c
0

no  cluster
1
miss  full
cluster density
Y =
( 1-P() ) 
hit 
cluster
lose 
cluster
+ P() (  -P() )
= P()2
Y
P()
c

2
10
Power laws
cumulative
frequency
Criticality
1
10
0
10
-1
10
0
10
1
10
2
10
3
10
cluster size
4
10
Average
cumulative
distributions
fires
clusters
size
high density
cumulative
frequency
low density
Power laws:
only at the
critical point
cluster size
yield
Tremendous attention has
been given to this point.
density
Edge-of-chaos, criticality,
self-organized criticality
(EOC/SOC)
Claim:
Life, networks, the
brain, the universe and
everything are at
“criticality” or the
“edge of chaos.”
yield
density
Edge-of-chaos, criticality,
self-organized criticality
(EOC/SOC)
Essential claims:
• Nature is adequately described yield
by generic configurations (with
generic sensitivity).
• Interesting phenomena is at
criticality (or near a bifurcation).
yield
density
18 Sep 1998
Forest Fires: An Example of Self-Organized
Critical Behavior
Bruce D. Malamud, Gleb Morein, Donald L. Turcotte
4 data sets
10
6
WWW files
Mbytes
Cumulative
10
(Crovella)
4
Frequency
10
-1
-1/2
Forest fires
1000 km2
2
(Malamud)
10
0
10
-6
10
-4
10
-2
10
0
Size of events
10
2
10
WWW
Cumulative
10
4
FF
Frequency
10
-1/2
2
SOC FF
10
Exponents
are way off.
6
.15
0
10
-6
10
-4
10
-2
10
0
Size of events
10
2
3
10
2
10
-1/2
1
10
SOC FF
0
10
-2
10
-1
10
0
10
1
10
2
10
Additional 3 data sets
3
10
4
10
?
Forget random,
generic
configurations.
Would you design a
system this way?
What about high
yield configurations?
Barriers
What about high
yield configurations?
Barriers
1
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0
0
0.2
0.4
0.6
0.8
1
• Rare, nongeneric, measure zero.
• Structured, stylized configurations.
• Essentially ignored in stat. physics.
• Ubiquitous in
• engineering
• biology
• geophysical phenomena?
What about high
yield configurations?
Highly Optimized Tolerance (HOT)
critical
Cold
Burned
Why power laws?
Almost any
distribution
of sparks

Optimize
Yield
Power law
distribution
of events
both analytic and numerical results.
Special cases
Singleton
(a priori
known spark)
Uniform
spark
Optimize
Yield
Optimize
Yield
No fires
Uniform
grid
Special cases
No fires
In both cases, yields 1 as N .
Uniform
grid
Generally….
1.
2.
3.
4.
Gaussian
Exponential
Power law
….
Optimize
Yield
Power law
distribution
of events
Numerical
Example
32x32 grid
1
0.9
“optimized”
0.8
0.7
yield
0.6
0.5
0.4
random
0.3
0.2
0.1
0
0
0.2
0.4
0.6
0.8
density
1
Probability distribution (tail of normal)
x1=2.^(- ((1+ (1:n)/n)/.3 ).^2 );
x2=2.^(- ((.5+ (1:n)/n)/.2 ).^2 );
p ( x, y )  p ( x ) p ( y )
p( x)  2
 (1  x ) / .32
p( y)  2
 (.5  y ) / .2 2
x, y  (1,2,..., n) / n
Probability distribution (tail of normal)
2.9529e-016
0.1902
High probability region
5
10
15
20
25
30
5
2.8655e-011
10
15
20
25
30
4.4486e-026
• We expect barriers concentrated in the upper left.
• Computing the global optimal is difficult, since
the number of configurations is
322
1024
2
 2
• But practically anything you do…
• …gives high yields and power laws…
• …at almost all densities.
Grid design:
optimize the
position of “cuts.”
cuts = empty sites in
an otherwise fully
occupied lattice.
Compute the global optimum for this constraint.
Optimized grid
Small events likely
large events
are unlikely
density = 0.8496
yield = 0.7752
Optimized grid
density = 0.8496
yield = 0.7752
1
0.9
0.8
High yields.
0.7
0.6
grid
0.5
0.4
random
0.3
0.2
0.1
0
0
0.2
0.4
0.6
0.8
1
“Evolutionary”
algorithm
“grow” one site at a
time to maximize
incremental (local)
yield
density= 0.8
yield = 0.8
“grow” one site at a
time to maximize
incremental (local)
yield
density= 0.9
yield = 0.9
“grow” one site at a
time to maximize
incremental (local)
yield
Optimal “evolved”
density= 0.97
yield = 0.96
“grow” one site at a
time to maximize
incremental (local)
yield
Several small events
A very
large
event.
Optimal “evolved”
density= 0.9678
yield = 0.9625
Small events likely
large events
are unlikely
Optimal “evolved”
density= 0.9678
yield = 0.9625
“optimized”
1
0.9
High yields.
0.8
0.7
0.6
At almost all densities.
0.5
0.4
random
0.3
0.2
0.1
0
0
0.2
0.4
0.6
0.8
density
1
Very sharp “phase transition.”
1
0.9
0.8
0.7
0.6
0.5
0.4
random
0.3
0.2
0.1
0
0
0.2
0.4
0.6
0.8
density
1
Robust,
yet fragile?
Extreme robustness and extreme hypersensitivity.
Small
flaws
Robust,
yet fragile?
1
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0
0
0.2
0.4
0.6
0.8
1
1
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0
0
0.2
0.4
0.6
0.8
1
If probability of sparks changes.
disaster
“Robust, yet fragile”
• Robust to uncertainties
– that are common,
– the system was designed for, or
– has evolved to handle,
• …yet fragile otherwise
• This is the most important feature of
complex systems (the essence of HOT).
Conserved?
Sensitivity to:
sparks
assumed
p(i,j)
flaws
Uniform
grid
Can eliminate
sensitivity to:
assumed
p(i,j)
Eliminates power laws as well.
Thick open barriers.
There is a yield penalty.
Can reduce
impact of:
flaws
0
10
“critical”
-1
10
Cum.
Prob.
“evolved”
-2
10
-3
10
All produce
Power laws
grid
-4
10
0
10
1
10
2
3
10
10
size
Evolution
10
optimal
density= 0.9678
yield = 0.9625
10
10
1
10
0.9
yield
0
-2
-4
.9
-6
0.8
0.7
10
0.6
.8
-8
0.5
0.4
random
0.3
10
-10
.7
0.2
0.1
0
0
0.2
0.4
0.6
0.8
density
1
10
-12
10
0
10
1
10
2
10
3
This source of power
laws is quite universal.
Almost any
distribution
of sparks
Optimize
Yield
Power law
distribution
of events
10
WWW files
Mbytes
Cumulative
10
(Huffman)
(Crovella)
4
Frequency
10
Data
compression
6
-1
-1/2
Forest fires
1000 km2
2
(Malamud)
10
0
10
-6
10
-4
10
-2
10
0
Size of events
10
2
Universal network behavior?
throughput
Congestion
induced
“phase
transition.”
Similar for:
• Power grid?
• Freeway traffic?
• Gene regulation?
• Ecosystems?
• Finance?
demand
Networks
log(thru-put)
Making a “random network:”
• Remove protocols
– No IP routing
– No TCP congestion control
• Broadcast everything
 Many orders of magnitude
slower
random
networks
Broadcast
Network
log(demand)
Networks
real
networks
log(thru-put)
HOT
random
networks
Broadcast
Network
log(demand)
The yield/density curve
predicted using random
ensembles is way off.
designed
Yield,
flow, …
HOT
random
Densities, pressure,…
Similar for:
• Power grid
• Freeway traffic
• Gene regulation
• Ecosystems
• Turbulence
• Finance?
10
WWW files
Mbytes
Cumulative
10
(Huffman)
(Crovella)
4
Frequency
10
Data
compression
6
-1
-1/2
Forest fires
1000 km2
2
(Malamud)
10
0
10
-6
10
-4
10
-2
10
0
Size of events
10
2
document
split into N files
to minimize
download time
A toy website model
(= 1-d grid HOT design)
Forest fires?
Fire suppression
mechanisms must
stop a 1-d front.
Burnt regions are 2-d
d-dimensional
li = volume enclosed
ri = barrier density
li   , ri 
d
pi = Probability
of event

d 1
li
Resource/loss relationship:
l r
d
PLR optimization
Minimize
expected loss
J
P: uncertain events
with probabilities pi
Resource/loss
relationship
 pili  ri  R
R: limited
resources ri
L: with
loss li
l (r ) 

r

c


1
 d
PLR optimization
J
 pili  ri  R
l (1)  0
l (r )  cr
Set amplitudes and
small scale cutoff
  1
l (r ) 

r

c


1
 d
PLR optimization
J
=0
=1
=2
=
“dimension”
 pili  ri  R
data compression
web layout
forest fires
l (r ) 

r

c


1
 d
PLR optimization
J
=0
 =0 is
Shannon
source coding
 pili  ri  R
data compression

  log( r )

l (r )  
 c 
  r 1



 0
 0
Minimize average cost using
standard Lagrange multipliers
J 
 pili  ri
 R
Leads to optimal solutions for
resource allocations and the
relationship between the
event probabilities and sizes.
With optimal
cost
R  c 1
 pi  1
  log( r )

l (r )   c  
r 1
 


 0
 0




1 /(1  ) 



Rp i
c


li  

1
   p1j /(1  ) 


 j






  pi log( Rp i )   pi log(  pi )

J 
1 
 c
1





 R  p 1    p 



i
i

  




 0
 0
Minimize average cost using
standard Lagrange multipliers
J 
 pili  ri
 R
Leads to optimal solutions for
resource allocations and the
relationship between the
event probabilities and sizes.
With optimal
cost
R  c 1
 pi  1
  log( r )

l (r )   c  
r 1
 


 0
 0




1 /(1  ) 



Rp i
c


li  

1
   p1j /(1  ) 


 j





  pi log( pi )
 0


1 
J  

1


1
   pi 1  
 1   0

  


 
To compare with data.
plot
sizes
from
data
l , Pˆ 
i
i
compute
using
model
Cumulative
order
li  li 1




1 /(1  ) 



Rp i
c


li  

1
   p1j /(1  ) 


 j




Solve for p(l) gives
pˆ i  c1 li  c2 
 (11 /  )
ˆ i li  li 1 
Pˆi   p
k i
10
6
DC
HOT WWW
10
10
10
4
HOT FF
2
0
10
-6
10
-4
10
-2
10
0
10
2
10
6
DC
HOT WWW
10
10
10
4
HOT FF
2
SOC FF
0
10
-6
10
-4
10
-2
10
0
10
2
6
10
5
10
4

5
4
10
4

3
3
10
2
10

5

4
1

3

4
1
10
0
10 -6
10
-4
10
-2
10
0
10
2
10
SOC
HOT
d=1
SOC
d
d
d=1
HOT
10
DC and WWW
are prescriptive.
6
DC
HOT WWW
10
10
4
HOT FF
2
SOC FF
Why are
the HOT PRL
0
10
-6
-4
predictions
10 so good?
10
10
-2
10
0
10
2
18 Sep 1998
Forest Fires: An Example of Self-Organized
Critical Behavior
Bruce D. Malamud, Gleb Morein, Donald L. Turcotte
4 data sets
3
10
HOT FF
=2
2
10
1
10
SOC FF
0
10
-2
10
-1
10
0
10
1
10
2
10
Additional 3 data sets
3
10
4
10
Forest fires?
Fire suppression
mechanisms must
stop a 1-d front.
Burnt regions are 2-d
Forest fires?
Geography could make
 <2.
California geography:
further irresponsible speculation
• Rugged terrain, mountains, deserts
• Fractal dimension   1?
5
10
California brushfires
4
10
=1
3
10
2
d=2
10
SOC FF
1
10
d=1
0
10
0
10
1
10
2
10
3
10
4
10
5
10
6
10
Characteristic Critical
HOT
Yield/density
Low
High
Robustness
Generic
Robust, yet fragile
Events/structure
Generic, fractal
Structured, modular
External behavior Complex
Internally
Simple
Nominally simple
Complex
Power laws
at criticality
everywhere
Details
Don’t matter
Do matter
Characteristic Critical
HOT
Yield/density
Low
High
Robustness
Generic
Robust, yet fragile
Characteristics
Generic, fractal Structured, modular
Events/structure
External behavior Complex
Internally
Simple
Nominally simple
Complex
Power laws
at criticality
everywhere
Details
Don’t matter
Do matter
Toy models
?
• Power systems
• Computers
Examples/
• Internet
• Software
Applications
• Ecosystems
• Extinction
• Turbulence
Characteristic Critical
HOT
Yield/density
Low
High
Robustness
Generic
Robust, yet fragile
Events/structure
Generic, fractal
Structured, modular
External behavior Complex
Internally
Simple
Nominally simple
Complex
Power laws
at criticality
everywhere
Details
Don’t matter
Do matter
But when we look in detail
at any of these examples...
…they have all the HOT
features...
• Power systems
• Computers
• Internet
• Software
• Ecosystems
• Extinction
• Turbulence
Robust
Humans have
exceptionally robust
systems for vision
and speech.
Yet fragile
…but we’re not so
good at surviving,
say, large meteor
impacts.
Yet fragile
…but we’re not so
good at surviving,
say, large meteor
impacts.
Robustness and uncertainty
Sensitive
Error,
sensitivity
Robust
Types of uncertainty
Robustness and uncertainty
Humans
Sensitive
Error,
sensitivity
Archaebacteria
Robust
speech/
vision
Meteor
impact
Types of uncertainty
Robustness and uncertainty
Sensitive
Humans
yet
fragile
Error,
sensitivity
Archaebacteria
Robust
Robust
speech/
vision
Meteor
impact
Types of uncertainty
“Complex” systems
yet
fragile
Sensitive
Error,
sensitivity
Robust
Robust
Types of
uncertainty
Automobile
air bags
children
low-speed
Error,
sensitivity
high speed
head-on
collisions
Types of uncertainty
Multiscale modeling: Homogeneous systems
Sensitive
Sensitive details
Error,
sensitivity
Robust statistics
Robust
Types of uncertainty
Multiscale, homogeneous example
Sensitive
Sensitive details
Gas molecules
in this room
Error,
sensitivity
Statistical
Mechanics
Robust
Temperature
and pressure
Robust statistics
initial conditions
Types of uncertainty
Multiscale, homogeneous example
Gas molecules
...of theSensitive
microscopic
details details...
Sensitive
in this room
Error,
sensitivity
Robust
and can be obtained
by taking ensemble
averages
The macroscopic
statistics
Robust statistics
are uniformly and robustly
independent...
initial conditions
Types of uncertainty
Statistical
Mechanics
Temperature
and pressure
“Complex” systems
…to the microscopic details...
Sensitive
…and ensemble averages
are of limited usefulness.
yet
fragile
Error,
sensitivity
The macroscopic behavior
has both extreme robustness
Robust
and hypersensitivity...
Types of
uncertainty
Robust
“Complex” systems
yet
fragile
Sensitive
• Thus we are (forced into) redoing
Error, statistical physics from scratch for
these systems.
sensitivity
• The HOT results are among the
first outcomes.
Robust
•These are just steps toward...
Types of
uncertainty
Robust
“Complex” systems
yet
fragile
Sensitive
Error,
sensitivity
The ultimate goal of
Robust simulation, and
modeling,
analysis is to create this
plot for specific systems.Types of
uncertainty
Robust
Modeling “complex” systems
May need great detail here
Sensitive
Error,
sensitivity
And much less detail here.
Robust
Types of uncertainty
Required
model
complexity
Why “scientific supercomputing” has disappointed.
Still haven’t captured
important phenomena.
Sensitive
googaflops
Error,
sensitivity
petaflops
average
teraflops
Robust
Types of uncertainty
Why “scientific supercomputing” has disappointed.
Still haven’t captured
important phenomena.
•
Relied
too
heavily
on
the
Sensitive
homogeneous view of multiscale
googaflops
phenomena from physics.
• Deep misunderstanding of the
Error,
petaflops
sensitivity “robust, yet fragile” character of much
complex phenomena.
average
teraflops
Robust
Types of uncertainty