Teoría del campo promedio

La definición presentada en esta sección de la teoría del campo promedio se obtuvo del trabajo realizado por Gutowitz en [22], [23] y [25].

La teoría del campo promedio es un modelo simple que proporciona propiedades estadísticas de los autómatas celulares. La teoría del campo promedio se basa en que los elementos del conjunto de estados $\Sigma$ son independientes entre si, es decir, no hay correlación entre cada uno de los elementos que se encuentran en el espacio de evoluciones, bajo esta condición es fácil estimar la probabilidad de los estados en una vecindad en términos de la probabilidad de un solo estado (el estado en que evoluciona la vecindad). La probabilidad de la vecindad es el producto de las probabilidades de los estados que forman la vecindad.

La probabilidad de que una célula tenga un estado en particular en el tiempo $t+1$, es la suma de las probabilidades de las vecindades que se transforman a este estado en el tiempo $t$. Se consideran únicamente las vecindades definidas para el estado de la célula en estudio, porque la regla de evolución es local. Sea $\varphi$ la regla de evolución de un autómata celular de orden $(k,r)$ con dos estados por célula, por lo tanto $\Sigma=\{0,1\}$.

La vecindad es de tamaño $2r+1$, $k^{2r+1}$ es el número de vecindades, $\varphi(x_{i-r},\ldots,x_{i},\ldots,x_{i+r})$ tomará el valor de 0 ó 1 dependiendo de la transformación de cada vecindad para una regla de evolución en particular, la vecindad $x_{i-r},\ldots,x_{i},\ldots,x_{i+r}$ se representará como $X$. Sea $p$ la probabilidad de tener el estado 1 en el tiempo $t$, $1-p$ es la probabilidad de tener el estado 0 en el tiempo $t$, $v$ es el número de veces que aparece el estado 1 en la vecindad, $n-v$ es el número de veces que aparece el estado 0 en la vecindad, la sumatoria tomará cada una de las vecindades definidas por el conjunto $\Sigma^{2r+1}$, entonces la teoría del campo promedio calcula la densidad en el tiempo $t+1$ como:

$$p_{t+1}=\sum_{j=1}^{k^{2r+1}}\varphi_{j}(X)p_{t}^{v}(1-p_{t})^{n-v}$$ (2.5.1)

nótese que $k^{2r+1}$ es el número de vecindades y $\Sigma^{2r+1}$ es el conjunto que define cada una de las vecindades, además la teoría del campo promedio puede ser empleada en autómatas celulares de diferentes dimensiones. Los puntos fijos que representa la teoría del campo promedio son una estimación de la densidad de los estados en un largo tiempo, esta densidad es independiente de la densidad inicial.

McIntosh hace notar la relación que existe entre la teoría del campo promedio y los polinomios de Bernstein en [44], la definición de los polinomios de Bernstein que se presenta se obtuvo de [37].

Sea una función $f(x)$ definida en el intervalo cerrado $[0,1]$ entonces la expresión:

$$B_{n}(x) = B_{n}^{f} (x) = \sum_{v=0}^{n} f \left( \frac{v}{n} \right) \left (\begin{array}{c} n v \end{array} \right ) x^{v} (1-x)^{n-v}$$ (2.5.2)

es llamado el Polinomio de Bernstein de orden $n$ de la función $f(x)$. $B_{n}(x)$ es un polinomio en $x$ de grado $\leq n$ donde $v=0,1,\ldots,n-1$. El polinomio $B_{n}(x)$ sería introducido por S. Bernstein para dar una demostración de la aproximación del teorema de Weierstrass. Pero si $f(x)$ es continua en $[0,1]$, entonces:

$$\lim_{x\rightarrow \infty} B_{n}(x) = f(x)$$ (2.5.3)

uniformemente en $[0,1]$. Aquí hay muchas otras expresiones llamadas ``integrales singulares'' y la relación que tienen con los polinomios de Bernstein es la aproximación que realizan ``generando'' la función $f(x)$ además de reproducir algunas de sus propiedades. La integral singular mas conocida es la integral de Dirichlet's

$$s_{n}(x) = \frac{1}{\pi} \int_{-\pi}^{+\pi}{ f(t) \left. \frac{sin(n+\frac{1}{2})(t-x)}{2 sin \frac{1}{2}(t-x)} \right. dt, }$$

representado las sumas parciales $s_{n}(x)$ de las series de Fourier de la función $f(x)$ integrable en $[-\pi,+\pi]$. Otro ejemplo es la integral de Fejér que representa la media aritmética $\sigma_{n}=(s_{0}+s_{1}+\ldots+s_{n})/(n+1)$ de $s_{n}(x)$. En general una integral singular puede ser escrita en la forma:

$$\Phi_{n}(x) = \int_{a}^{b}{ f(t) K_{n}(x,t)dt, }$$ (2.5.4)

donde $K_{n}(x,t)$ es el ``kernel'' definido por $a \leq x \leq b$ y $a \leq t \leq b$, que tiene propiedades de las funciones $f(x)$ de una cierta clase, $\Phi_{n}(x)$ converge a $f(x)$ cuando $n \rightarrow \infty$.

El polinomio de Bernstein de la Ecuación 2.5.2 es una suma finita de un tipo correspondiente a la integral de la Ecuación 2.5.4. Ambas ecuaciones son casos especiales de la integral de Stieltjes en la variable $t$,

$$B_{n}(x) = \int_{0}^{1}{ f(t) d_{t} K_{n}(x,t), }$$ (2.5.5)

con el kernel

$$K_{n}(x,t) = \sum_{v \leq n,t} \left (\begin{array}{c} n \\ v \end{array} \right ) x^{v} (1-x)^{n-v}, 0 < t \leq 1,$$ (2.5.6)

$$K_{n}(x,0) = 0$$

que es constante en algún intervalo $v/n \leq t < (v+1)/n, v=0,1,\ldots,n-1$ y tiene el salto

$$\left (\begin{array}{c} n \\ v \end{array} \right ) x^{v} (1-x)^{n-v}$$

que es el punto básico de la interpolación $t=v/n$. En este sentido la teoría de los polinomios de Bernstein, además de la teoría de las series de Fourier, son un capítulo de la teoría de integrales singulares.

Los polinomios de Bernstein están conectados con la teoría de la probabilidad, con problemas de momentos y con la teoría de sumas en series divergentes. Un problema complejo e interesante que no ha sido completamente resuelto, concierne a los polinomios de Bernstein en funciones analíticas.

La expresión:

$$p_{v} = p_{n,v}(x) = \left (\begin{array}{c} n v \end{array} \right ) x^{v} (1-x)^{n-v}$$ (2.5.7)

contenida en la Ecuación 2.5.2 es la binomial o las probabilidades de Newton conocidas en la teoría de la probabilidad. Si $0 \leq x \leq 1$ es la probabilidad de un evento $E$, entonces $p_{n,v}(x)$ es la probabilidad de que $E$ debe ocurrir exactemente $v$ veces en $n$ intentos independientes.

La relación que existe entre la teoría del campo promedio y los polinomios de Bernstein se establece entre las Ecuaciones 2.5.1 y 2.5.7. La Ecuación 2.5.1 genera el polinomio completo derivado de todas las evoluciones de cada una de las vecindades, es decir, analiza todos los términos que puede generar la regla de evolución, por otra parte el polinomio de Bernstein de la Ecuación 2.5.7 calcula todas las combinaciones que se pueden generar de un estado en una vecindad de tamaño $2r+1$, ésto da como resultado un término del polinomio de la Ecuación 2.5.1 en específico para un $n$ y $v$ dado, donde $n$ tomará el valor $2r+1$ y $v$ tomará el número de veces que un estado de $\Sigma$ puede estar en la vecindad, es decir, $v$ tomará valores entre $0 \leq v \leq 2r+1$.

Finalmente los polinomios de Bernstein ayudan a no calcular todos los términos posibles del polinomio, como lo hace la teoría del campo promedio, simplemente calculando las combinaciones para un número de veces en que estará un estado en la vecindad, excluyendo todos aquellos términos que no formarán parte del polinomio para una regla de evolución en específico, aunque se sigue empleando la sumatoria pero ahora de binomiales. Esta sumatoria a diferencia de la Ecuación 2.5.1, solo sumará los términos que son calculados por las binomiales.

Para ejemplificar estos conceptos se construye el polinomio de un autómata celular en una dimensión de orden $(k=2,r=1)$ regla 110. El conjunto de estados $\Sigma=\{0,1\}$, la vecindad es de tamaño $2r+1=2(1)+1=3$ y el número de vecindades es igual a $k^{2r+1}=2^{3}=8$. Entonces la regla de evolución para la regla 110 se representa como:

$\varphi(0,0,0)$	=	0
$\varphi(0,0,1)$	=	1
$\varphi(0,1,0)$	=	1
$\varphi(0,1,1)$	=	1
$\varphi(1,0,0)$	=	0
$\varphi(1,0,1)$	=	1
$\varphi(1,1,0)$	=	1
$\varphi(1,1,1)$	=	0

las vecindades son $\Sigma^{2r+1}=\{000,001,010,011,100,101,110,111\}$, $p$ es la probabilidad de obtener el estado 1 en la siguiente generación, el complemento de la probabilidad de $p$ es $q$ que es igual a $q=1-p$ y $q$ es la probabilidad de obtener el estado 0 en la siguiente generación, por lo tanto $p+q=1$ donde $p$ y $q$ tomarán valores del intervalo cerrado $[0,1]$.

Empleando la Ecuación 2.5.1, $\varphi(X)$ tomará el valor que produzcan las células de evolución para cada una de las vecindades de $\Sigma^{2r+1}$, $p_{t}$ la probabilidad de obtener el estado 1 en la siguiente generación, $(1-p_{t})$ la probabilidad de obtener el estado 0 en la siguiente generación, $v$ es el número de veces que aparece el estado 1 en la vecindad y $n-v$ es el número de veces que aparece el estado 0 en la vecindad, de esta manera se tiene que:

$$p_{t+1} = (0)p_{t}^{0}(1-p_{t})^{3} + (1)p_{t}^{1}(1-p_{t})^{2} + (1)p_{t}^{1}(1-p_{t})^{2}$$

$$+ (1)p_{t}^{2}(1-p_{t})^{1} + (0)p_{t}^{1}(1-p_{t})^{2} + (1)p_{t}^{2}(1-p_{t})^{1}$$

$$+ (1)p_{t}^{2}(1-p_{t})^{1} + (0)p_{t}^{3}(1-p_{t})^{0}$$

simplificando el polinomio se tiene que:

$$p_{t+1} = 2p_{t}(1-p_{t})^{2}+3p_{t}^{2}(1-p_{t})$$

poniendolo en términos de $p$ y $q$ finalemente se obtiene el polinomio de la regla 110:

$$p_{t+1} = 2p_{t}q_{t}^{2}+3p_{t}^{2}q_{t}$$

como se había mencionado la sumatoria calcula todas las vecindades que deriva la regla de evolución, ahora se emplearán los polinomios de Bernstein de la Ecuación 2.5.7 para ver que resultado produce.

El grado del polinomio $n$ es igual al tamaño de la vecindad, entonces $n=2r+1=3$ y $v$ tomará valores de $v=0,1,2,3$ que es el número de veces que puede aparecer el estado 1 en la vecindad, $x=p$ y $1-x=q$.

Para $n=3$ y $v=0$ se tiene:

$$p_{0,3} = \left (\begin{array}{c} 3 \\ 0 \end{array} \right ) x^{0} (1-x)^{3-0} = \left( \frac{3!}{0!(3-0)!} \right) (1) (1-x)^{3}$$

$$= \left( \frac{3!}{3!} \right) (1-x)^{3} = (1-x)^{3}$$

en términos de $p$ y $q$ finalmente tenemos:

$$p_{0,3} = q^{3}.$$

Para $n=3$ y $v=1$ se tiene:

$$p_{1,3} = \left (\begin{array}{c} 3 \\ 1 \end{array} \right ) x^{1} (1-x)^{3-1} = \left( \frac{3!}{1!(3-1)!} \right) x (1-x)^{2}$$

$$= \left( \frac{3!}{2!} \right) x (1-x)^{2} = 3x (1-x)^{2}$$

en términos de $p$ y $q$ finalmente tenemos:

$$p_{1,3} = 3pq^{2}.$$

Para $n=3$ y $v=2$ se tiene:

$$p_{2,3} = \left (\begin{array}{c} 3 \\ 2 \end{array} \right ) x^{2} (1-x)^{3-2} = \left( \frac{3!}{2!(3-2)!} \right) x^{2} (1-x)^{1}$$

$$= \left( \frac{3!}{2!} \right) x^{2} (1-x) = 3x^{2} (1-x)$$

en términos de $p$ y $q$ finalmente tenemos:

$$p_{2,3} = 3p^{2}q.$$

Para $n=3$ y $v=3$ se tiene:

$$p_{3,3} = \left (\begin{array}{c} 3 \\ 3 \end{array} \right ) x^{3} (1-x)^{3-3} = \left( \frac{3!}{3!(3-3)!} \right) x^{3} (1-x)^{0}$$

$$= \left( \frac{3!}{0!} \right) x^{3} = x^{3}$$

en términos de $p$ y $q$ finalmente se tiene que:

$$p_{3,3} = p^{3}.$$

Nótese que los polinomios de Bernstein calculan todos los términos que puede generar el polinomio de la Ecuación 2.5.1, estos términos no toman en cuenta la regla de evolución, sin embargo empleando los dos conceptos se puede simplificar el calculo del polinomio de la teoría del campo promedio para reglas de evolución muy grandes.

La manera en que se simplifica el proceso es calculando los polinomios de Bernstein que determinan la probabilidad de obtener el estado 1 en la siguiente generación, es decir, tomando en cuenta aquellas vecindades que evolucionan al estado 1 y que la suma del estado 1 en cada una de las vecindades correspondan de igual manera, este concepto solo es utilizado para reglas de evolución totalísticas y semitotalísticas. Si las reglas de evolución no fueran de estos dos tipos, entonces se tiene que aplicar la Ecuación 2.5.1 y este método no puede ser aplicado.