Wednesday, 1 January 2020

A practical understanding of ergodicity

Preamble

In this tutorial, we will provide a brief introduction on what does ergodicity means and how to detect when a dynamical system behaves ergodically. The very definition of ergodicity is not uniform in the literature, especially definitions of Boltzmann and Birkhoff are not the same. So, one should talk about a set of ergodicity, i.e., ergodic theorems, rather than a single one. We follow the basic definition that, the system is ergodic for a given observable when the ensemble-averaged value of the observable is the same as its time-averaged value. But beware that this definition is a purely statistical definition and does not reflect Boltzmann's ergodicity from Physics.

Boltzmann: Father of ergodicity
(Wikipedia)
What are the ensemble and time averaging?

The ensemble is a fancy word. It doesn't mean a group of musical instruments but it is short for the statistical ensemble. It is developed by Gibbs, an American theoretical physicist. Essentially all possible state of a physical system. In statistics, this actually has another name, a sample space.
For example, sample space for the outcome of two fair coins tossed at the same time would be
$$ \Omega = \{HH, HT, TH, TT\}$$
Let's say we represent them as bits $H=1, T=0$ and we want to compute an observable $\mathscr{A}$, the sum of outcomes, in the entire ensemble would read.
$$\Omega_{\mathscr{A}} = \{2,1,1,0\}$$
And the ensemble average, arithmetic mean, would be $\langle \mathscr{A} \rangle_{ensemble} = 1.0$. A time-averaging can be computed via an experiment, so-called trials. Let's say we had 6 trials
$$ \Omega_{time} = \{HH, TH, HH, HT, TH, HT\}$$
and time-averaged observable will be $\langle \mathscr{A} \rangle_{time} = 1.33$. Note that larger the trials time-averaged values approach to ensemble averaged ones.

Note that this sounds very naive and useless example, but if we have very large sample space with the complicated setting, so-called in thermodynamic ensembles and limits, computing time-averaged values are much easier, whereby comping ensemble average is intractable most of the cases.

Connection to the law of large numbers 

Statistically  inclined readers might catch that the above definition sounds like the law of large numbers. It is indeed the strong form of the law of large numbers and it is a special case of an ergodic theorem.


Conclusions: Why would I care about ergodicity?

Apart from the intellectual appeal, ergodicity is very important in statistical physics. Almost all computations rely on the ergodic theorems. So-called N-body systems are simulated based on this for computing physical properties. Ergodicity pops up everywhere from economics to deep learning.

Further Reading with Notes

The literature is vast in ergodicity. Due to its mathematical nature, text on ergodicity can easily be non-accessible for an average scientist, well, even for an average mathematician.

  • Modern Ergodic Theory, Joel L, Lebowitz and Oliver Penrose link (excellent for an introduction)
  • Computational Ergodic Theory, Choe, link (advanced text)
  • An introduction to Chaos and Nonequilibrium Statistical Mechanics, link (explains why Boltzmann's ergodicity is different)
  • Deep Learning and complexity: link (ergodicity in spectra, different kind of ergodicity)
  • Ergodicity and economics: link (ergodicity in risk decisions, different kind of ergodicity)






Monday, 2 January 2017

Testing emergent gravity: Gravitational Lensing to atom interferometer

Paranal Telescopes in Chile. (ESO/H.H. Heyer)
In this post, I would like to briefly discuss emergent gravity, an idea, that gravity itself is an artefact of more fundamental description, such as entropy. Despite the fact that we have an experimental evidence of gravitational waves, thus gravity really exist and physically detectable: The recent results of Laser Interferometer Gravitational-Wave Observatory (LIGO) programme in detecting gravitation waves was a landmark experimental evidence supporting Einstein's General Relativity theory.

Emergent Gravity: Verlinde's thesis

Eric Verlinde has proposed a controversial hypothesis in 2010 that gravity is originated from an entropic force [here]. He has shown that both Newtonian and Einstein's gravitational equations are artefacts of entropic force and in 2016 he proposed a similar approach in explaining galactic motions without the need of using dark matter [here].

Testing Emergent Gravity: Gravitational Lensing

Margot M. Brouwer and her co-workers have published a work [here], using weak gravitational lensing data from ESO telescopes. This was the first evidence for Verlinde's theory which attracted a lot of media attention because of implications in our understanding of the nature of gravity.

Testing Entropic Gravity Directly: Atom Interferometer

Despite this initial test of emergent gravity, there is still a lack of direct experimental evidence for Verlinde's initial hypothesis that force laws are artefacts of entropic force. Recently another approach is proposed to test this entropic force argument, [here], using mater-wave interferometry via utilising part of Newton-Schroedinger. The core idea is there is a direct relationship between the gravitational constant G and the atomic system's quantum state. If this is experimentally feasible, maybe with next generation atom interferometer systems, this could be a direct test for Verlinde's entropic force argument.



Monday, 1 August 2016

Understanding the empirical law of large numbers and the gambler's fallacy

One of the misconceptions in our understanding of statistics, or a counter-intuitive guess, fallacy, appears in the assumption of the existence of the law of averages. Imagine we toss a fair coin many times, most people would think that the number of heads and tails would be balanced over the increasing number of trails, which is wrong. If you don't, then you might have a very good statistical intuition. Briefly,  we will illustrate this, a kind of gambler's fallacy with a simple simulation approach and discuss the empirical law of large numbers.
Figure 1: Empirical law of large numbers, ratio of
occurances approach to a constant.

Empirical law of large numbers

If we repeat an experiment long enough, we would approach to expected outcome. The simplest example is a coin-toss experiment, that an expected 
fair coin toss would lead to equal likelihood for head and tail, 1 or 0.  This implies that, the ratio of head and tails will approach to one with increasing number of repeats. Let's say, we toss the coin $N$ times. The number of  heads and tails would be $n_{1}$ and $n_{0}$. The emprical law of large numbers states

$ \frac{n_{1}}{n_{0}} \to 1.0 $ if $N$ is very large, $N >>1$


But note that, the absolute difference, $|n_{1}-n_{0}|$ does not approach to any constant, on the contrary, it will increase with increasing number of repeats. This is classic example of gambler's fallacy that an outcome would balance out as there are more repeats. 


Fair coin-toss: Evolution of Bernoulli process
Figure 2: No low of averages. Absolute difference
of occurances
increases over repeats.

The Bernoulli process expresses binary outcomes, 1 or 0, i.e., success or failure, true or false. Bernoulli distribution reads,

$Ber(p, k) = p^{k} (1-p)^{1-k}$ for $k \in \{0,1\}$.

$p$ is the probability of success. We draw 50K samples from this distribution to get a Bernoulli process with $p=0.5$ and repeat the experiment 50 times, in order to obtain a "generalised" behaviour with uncertainty. This situation corresponds to a fair coin-toss experiment.  

Results


Empirical results of ratio of two outcomes and their absolute difference over repeats are reported in Figure 1 and 2 respectively..



Appendix: Source codes

R and Rcpp functions are shown in this section to reproduce the plots in this post. Source files are also available on github (here).
#'
#'  Misconception of the law of averages: Understanding the empirical law of large numbers
#' 
#'  (c) 2016 Mehmet Suzen 
#'  

rm(list=ls())
set.seed(987231)
library(Rcpp)          # law level implementations
library(LaplacesDemon) # for drawing samples from Bernoulli distribution
library(matlab)        # for tic/toc
# Set working directory to script directory 
Rcpp:::sourceCpp("empirical_law_of_large_numbers.cpp") # diff_binary_vec2
#'
#' Calculate the running difference in a binary vector 
#' 
diff_binary_vec  <- function(bvec) {
 ll <- length(bvec) 
 diff_vec  <- vector("double", ll)
 diff_vec  <- sapply(1:ll, function(i) { abs(i-2.0*sum(bvec[1:i])) } )
 diff_vec
}
#'
#' Calculate the running ratio in a binary vector 
#'
ratio_binary_vec  <- function(bvec) {
 ll         <- length(bvec) 
 ratio_vec  <- vector("double", ll)
 ratio_vec  <- sapply(1:ll, function(i) { abs(i/sum(bvec[1:i])-1.0) } )
 ratio_vec  <- sapply(ratio_vec, function(rv) {if(is.infinite(rv)) { rv <- 0; }; rv })
 ratio_vec
}

#' Wall-call timing difference 
tb <- rbern(20000, 0.5) # a fair-coin
tic()
t1 <- diff_binary_vec(tb)
toc()
tic()
t2 <- diff_binary_vec2(tb)
toc()
tic()
r1 <- ratio_binary_vec(tb)
toc()
tic()
r2 <- ratio_binary_vec2(tb)
toc()
#' 
#' Generate Bernoulli Process
#' 
nr        <- 50    # repeats
nt        <- 20000 # Bernoulli trails
tic()
bern_df <- data.frame(trail=c(), diff=c(), ratio=c())
for(i in 1:nr) {
  cat("repeat:",i, "\n")
  trail   <- rbern(nt, 0.5) # a fair-coin
  diff    <- diff_binary_vec2(trail)
  ratio   <- ratio_binary_vec2(trail)
  bern_df <- rbind(bern_df, cbind(1:nt, diff, ratio))
}

#' Now plot ratio and diff evolution with local regression in ggplot2
names(bern_df) <- c("trail", "diff", "ratio")
library(ggplot2)
p_diff <- ggplot(data=bern_df, aes(x=trail, y=diff)) + geom_smooth(formula="y~x") + 
          theme(
                panel.background = element_blank(), 
                axis.text.x      = element_text(face="bold", color="#000000", size=11),
                axis.text.y      = element_text(face="bold", color="#000000", size=11),
                axis.title.x     = element_text(face="bold", color="#000000", size=11),
                axis.title.y     = element_text(face="bold", color="#000000", size=11))  +
           xlab("Bernoulli Trails") + ylab("Difference between occurance of two outcomes") +
           ggtitle("No Law of Averages: Tail/Heads do not balanced out!")

png(file="no_law_of_averages.png")
p_diff
dev.off()

p_ratio <- ggplot(data=bern_df, aes(x=trail, y=ratio)) + geom_smooth(formula="y~x") + 
          theme(
                panel.background = element_blank(), 
                axis.text.x      = element_text(face="bold", color="#000000", size=11),
                axis.text.y      = element_text(face="bold", color="#000000", size=11),
                axis.title.x     = element_text(face="bold", color="#000000", size=11),
                axis.title.y     = element_text(face="bold", color="#000000", size=11))  +
           xlab("Bernoulli Trails") + ylab("Difference between occurance of two outcomes") +
           ggtitle("Empirical Law of Large Numbers: Ratio of Tails/Heads approach to one")

png(file="law_of_large_numbers.png")
p_ratio
dev.off()

#include <Rcpp.h>
#include <stdlib.h>
using namespace Rcpp;

//
// Sum a numeric vector up to an index
//
double sum_nv(NumericVector x, int s) {
  int i=0;
  double ss=0.0;
  for(i=0;i<(s+1);i++) {
   ss=ss+x[i];
  }
  return(ss);
}

//
// Calculate the running difference in a Bernoulli process (binary_vec)
//
// [[Rcpp::export]]
//
NumericVector diff_binary_vec2(NumericVector binary_vec) {
  int ll = binary_vec.size();
  int i  = 0;
  NumericVector diff_vec(ll, 0.0);
  for(i=0;i<ll;i++) {
    diff_vec[i] = std::abs(i+1.0-2.0*sum_nv(binary_vec, i));
  }
  return(diff_vec);
}

//
// Calculate the running ratio in a Bernoulli process (binary_vec)
//
// [[Rcpp::export]]
NumericVector ratio_binary_vec2(NumericVector binary_vec) {
  int ll = binary_vec.size();
  int i  = 0;
  NumericVector ratio_vec(ll, 0.0);
  for(i=0;i<ll;i++) {
    ratio_vec[i] = std::abs(((i+1.0)/sum_nv(binary_vec, i))-1.0);
  }
  return(ratio_vec);
}

Sunday, 3 May 2015

Constants or integrals of motion: Invariants of a dynamical flow

In this post we will shortly review a concept in dynamical systems namely of invariants of a dynamical flow with a simple derivation using famous Lotka-Volterra system as an example, due to Lotka (1925) and Volterra (1927).

Concept

A dynamical flow associated with an observation vector ${\bf y}(t)$ may have functions, $I({\bf y})$ that are time independent, being $dI/dt=0$. The number of invariants and the length of the observation vector have an effect on overall dynamics.

Lotka-Volterra (LV) System

The LV dynamics explains the behaviour between population of the prey $v$  and population of predators $u$, a case of predator-prey model. We will use a special case of the LV dynamics, remember the dot notation, meaning time derivatives, for predators,
$$ \dot{u}  =  u (v-2) $$
and for prays,
$$ \dot{v}  = v (1-u) $$
Observation vector will consist of $y=(u,v)$.

If we divide these equations, hoping that we can collect $u$ and $v$ in separate terms,

$$
\begin{eqnarray}
\frac{\dot{u}}{\dot{v}}            & = & \frac{u (v-2)}{v(1-u)} \\
\dot{u} v (1-u)                            & = & \dot{v} u (v-2) \\
\dot{u} v (1-u) - \dot{v} u (v-2)  & = & 0 \\
\dot{u} (1-u) - \dot{v} u/v (v -2) & = & 0\\
\dot{u} (1-u)/u - \dot{v}(v-2)/v   & = & 0
\end{eqnarray}
$$

If we integrate both sides over time $dt$,
$$
\begin{eqnarray}
\int \frac{1-u}{u} \frac{du}{dt} dt - \int \frac{v-2}{v} \frac{dv}{dt} dt & = &0 \\
\int \frac{1-u}{u}du - \int \frac{v-2}{v} dv & = &0 \\
\end{eqnarray}
$$

Solution of these indefinite integrals yields to a an invariant of the LV dynamics
$$ d I({\bf y})/dt = ln u - u + 2 ln v - v  $$
We have shown one invariant of the system. This is important to determine the structure of the system, such as volume preserving dynamics, i.e., Hamiltonian Dynamics.

Further Reading
(c) Copyright 2008-2020 Mehmet Suzen (suzen at acm dot org)

Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License.