Archive for the ‘Stochastic Processes’ Category

Thermodynamics of Small Systems

November 22, 2008

In a small system fluctuations can not be ignored, experiments can not be repeated. However, it is still desirable to have some understanding over the non-equilibrium behavior of the system.

Control Parameters vs Fluctuation Variables: For small systems the equation of state and the spectrum of fluctuations are fully determined by so-called control parameters.

The total change in the energy of the system has two components

dU = \sum_i {\partial U\over \partial x_i}|_{X} dx_i + \sum_a {\partial U\over \partial X_a}|_{x} dX_a

The first term can be interpretes as internal energy, dQ while the second term can be thought as work dW. For a specific experiment the value of \Delta Q and \Delta W are not reproducible due to the fluctuations in the system, although we can think of their probability distributions.

Probability Distributions: The work and heat probability distributions P(W) and P(Q) characterize the work and heat collected over an infinite number of experiments.

Fluctuation Theorems: The rate at which the system exchange heat with the bath is called the “entropy production“. It is convenient to define \sigma = Q/Tt where t is the interval of time over which the system exchange the heat Q. Associated with the entropy production is a time-dependent probability distribution P_t(\sigma). Under very general condition the following relation holds (Gallavotti and Cohen) for systems in steady states

\lim_{t\rightarrow \infty} {k_B \over t} \ln \left( P_{t}(\sigma) \over P_t(-\sigma) \right) =\sigma

Although the relation holds for infinite limit, it is considered as a good approximation for finite time. Note that the ratio P_t(\sigma)/P_t(-\sigma) for a system in equilibrium with the thermal bath is equal to $1$. This shows that steady state systems are more likely to deliver heat to the bath than it is to absorb heat form bath (Time reversal microscopic laws give birth to non time reversal macroscopic phenomenon, an answer to Loschmidt’s paradox).

The Jarzynski Equality: In a system in contact with thermal bath at temperature T, \Delta G the difference in free energy between equilibrium state A and B with x_A and x_B control parameter.

\exp \left(- {\delta G \over k_B T}\right)=\langle \exp \left(- {W \over k_B T}\right) \rangle,

the average being taken over infinite number of non-equilibrium processes.

The Crooks Fluctuation Theorem:

Non-Gaussian in the heat pobability distribution:

Generalized JE to arbitrary transition between non-equilibrium steady states:

for more information Ref to “The Nonequilibrium Thermodynamics of Small Systems”, by C. Bustamante, J. Liphardt and F. Ritort

Posted in Stochastic Processes | Leave a Comment »

Fluctuations in Network Dynamics

October 11, 2008

Taken from: “Fluctuations in Network Dynamics”, by M. Argollo de Menezes and A.-L. Barabasi

The flow through a node in a network is time dependent. This time dependence can be partly be described by mean flow, f_{\mathrm i}(t) and the fluctuation around this mean \sigma_{\mathrm i}(t).
In most natural networks, random, scale-free or small-world there is a functional dependence between mean and fluctuation of the flow through the nodes. In this paper it is claimed that the relation between f and \sigma in different networks (only scale-free and random network) fall into two different categories and characterized by their \alpha-exponent

\sigma \sim \langle f \rangle^{\alpha}

In all the networks they studied \alpha is equal to 1/2 or 1. In the networks with \alpha=1/2 the internal noise is responsible for flow fluctuations, while it was claimed that in networks with \alpha=1 the external noise is responsible for the fluctuations. Two different models are proposed.

Model 1: At any time step, W number of walkers are placed randomly on the network nodes, the preform M step walks.

Model 2: At any time step W random pairs of nodes are selected and they are connected through the shortest path between them (degeneracy problem is not discussed).

In both cases we observe \alpha=1/2 if W is fixed and \alpha=1 if W has large fluctuations. In general the fluctuations on a given nodes can be decompose into internal and external components
\sigma_{\mathrm i}^2=(\sigma_{\mathrm i}^{\mathrm {int}})^2 +(\sigma_{\mathrm i}^{\mathrm {ext}})^2
\sigma_{\mathrm i}^2 = a_{\mathrm i}^2 \langle f_{\mathrm i} \rangle +\left[ {\sigma_{\mathrm {dr}}\over \langle W(t)\rangle } \langle f_{\mathrm i} \rangle \right]^2

where \sigma_{\mathrm{dr}}=\sigma_{\mathrm{dr}}(\Delta W), represent the external driving force in the noise magnitude. Moreover, by increasing \Delta W a transition form \alpha =1 /2 to \alpha=1 behavior can be seen (some issues regarding the fitting process should be considered.).

In conclusion: “The \alpha=1/2 captures an endogenous behavior determined by the system’s internal fluctuations” while “The \alpha=1 exponent describes driven systems, in which the fluctuations of individual nodes are dominated by the time dependent changes in the external driving forces.”

Posted in Stochastic Processes | Leave a Comment »

Polya Problem

August 19, 2007

Consider a dynamical system under the influence of random noise. In such a general setting, the Polya problem questions the probability of coming back to the place that the system has started. If the configuration space of the system had finite volume then the probability would have been 1 (in the absence of attractors) somewhat in the same setting as ergodicity.

In the random walk frameworks the problem can be formalized easily. Define Q_n(r) as the probability of reaching to position r for the first time after n-steps. The generating function F(r,z) is defined as

F(r,z) = \sum_{n=1}^{\infty} z^n Q_n(r)

The probability of being as position r after n-steps, p_n(r) is following the consistency equation

p_n(r) = \sum_{j=1}^{n} p_{n-j}(0) Q_j(r)

The above equation relates the generating function for p_n(r) to the Q_n generating function

G(r,z) = \delta_{r,0} + F(r,z) G(0,z)

So the total return probability F(0,1)=Q_1(0)+Q_2(0)+ \ldots can be written as

F(0,1)=1-{1 \over {G(0,1)}}

The generating function G can be related to jump vector distribution, f(r), where p_n(r) = \sum f(r-r^{\prime} ) p_{n-1}(r^{\prime}) through convolution

G(r,z) = {1 \over 2 \pi} \int dk {\exp(-i kr) \over 1 - z{\tilde f}(k) }

Posted in Stochastic Processes | Leave a Comment »

Random Number Generators

June 8, 2007

Generating random numbers is a very challenging task. The result of any algorithm at best will be pseudo-random.

Linear Congruential Generators:

By choosing carefully three integer parameters, A, B and M, we can generate a sequence of random numbers, X_i

X_i= {1 \over M}\left( A \, X_{i-1} + B \right) \mod M

One of the shortcoming of such a method is that it has at most a period of order M. In addition, the sequence can be highly correlated. In order to correct these problems we can extend this method to higher dimensions.

Combined Linear Congruential Generators:

A collection of n carefully assigned triplets, A_a, B_a and M_a can be used to build a sequence of random numbers with a period of order $\prod_a M_a$. First we build $n$ parallel sequence of random numbers

x^a_i = \left( A_a \, x_{i-1}^a + B_a \right) \mod M_a

then out of them we build a sequence of random numbers with better quality.

X_i= {1 \over M}\left( \prod_a x^a_i \right) \mod M

were M is defined as \max(M_a). Also a extra shuffling procedure can reduce the correlation in any sequence.

Lagged Fibonacci Generators:

We can use more than one of the previous number in building the next number in the sequence, e.g. X_i = {1\over M} \left( \sum_{k=0}^K A_k X_{i-k} +B \right) \mod M. Finally they don’t need to be even sequential and can lag by any predetermined integers. For the Fibonacci generator to work properly we need a starter generator of other kind to build the first K random number (maximum lag) needed for Fibonacci algorithm.

Posted in Stochastic Processes | Leave a Comment »

Ito’s Lemma

May 31, 2007

Ito’s lemma can be thought as a generalization of Taylor’s expansion to stochastic processes. Taylor expansion connects the differential of a function F({x}) to d{{x}}.

dF({x}) = {\partial F \over \partial x } dx + {1\over 2 } {\partial^2 F \over \partial x^2} dx^2 + O(dx^3)

In the same spirit Ito’s lemma connects the differential of a function of a stochastic process F(X_t, t) to dX_t and dt.

dF(X_t, t)= \left( {\partial F \over \partial t} + {\partial^2 F \over \partial x^2} \right)dt + \left(\partial F\over \partial x \right) dX_t

This relation can be understood by applying the multiplication rule (dX_t)^2 =dt. The multiplication rule originates from the definition of the Brownian motion.

Posted in Stochastic Processes | Leave a Comment »