Repositorio Institucional de Documentos

SISTEMAS INTERACTIVOS MODELO DEL VOTANTE Jorge Velilla Gambó Trabajo de fin del grado de Matemáticas Universidad de Zaragoza English summary The two main objectives of this project are: - introducing spin systems as a particular kind of Markov processes and show some skills to study them, - describing some of the voter models in an easy way with intuitive results. A more exhaustive study can be found in [L], just like the proofs of the results that I am going to use. Interacting particle systems and spin systems Markov processes A Markov process is a random process indexed by a parameter (which is often the time) and obeying the Markov property: the future probability distribution depends only on the present and not on the past values of the process. Let Xbe a metric and compact space with measurable structure given by the σ-algebra of Borel sets, B(X). Let D[0,∞)be the set of all functions η.:[0,∞)−→ X s7−→ ηs right continuous and with left limits. For s∈[0,∞), let πsbe the evaluating map from D[0,∞)to Xand let Fbe the smallest σ-algebra on D[0,∞)which makes all πsmeasurable. Next, I am going to introduce some definitions. A continuous time Markov process in Xis a set of probabilities {Pη:η∈X}in D[0,∞)indexed by Xwhich carries out the Markov property: Pη(ηs+.∈A|Fs) = Pηs(A)∀η∈X,A∈F, where Ftis the smallest σ−algebra that makes {πs}s≤tmeasurable in D[0,∞). A Markov process is said to be a Feller process if S(t)f∈C(X)∀f∈C(X). A set of linear operators {S(t);t≥0}in C(X)with the following properties a) S(0) = Ithe identity in C(X), III IV Capítulo 0. English summary b) the map [0,∞)→C(X)such that t7→S(t)fis tight continuous for all f∈C(X), c) S(t+s)f=S(t)S(s)f∀s,t≥0,f∈C(X), d) S(t)1=1 the unity function ∀t≥0, e) S(t)f≥0∀t≥0,f∈C(X)are not negative, is said to be a Markov semigroup. There is an usual theorem in Markov processes which says that there is an univocal relationship among Markov processes in Xand Markov semigroups in C(X). It’s proof is complicated and it needs some precise tools which are introduced in the main project. The proof can be consulted in bibliography. In the project, I am going to talk about ergodicity and invariant measures. We can think of an invarian measure as a measure that not changes in the time. Then, a Markov process is ergodic if its set of invariant measures, I, is a singleton. Markov generators A linear operator Ω:D(Ω)−→ C(X) is said to be a Markov generator if: (a) 1 ∈D(Ω),Ω1=0, (b) D(Ω)⊆C(X)dense, (c) f∈D(Ω),λ≥0,g:=f−λΩf⇒m´ ın ξ∈X f(ξ)≥m´ ın ξ∈X g(ξ), (d) (f,Ωf)is closed in C(X)×C(X), (e) Im(I−λΩ) = C(X)for all λ≥0. The importance of the Markov generators is given by Hille-Yosida Theorem. This result assures that there is bijection among Markov generators in C(X)and Markov semigroups in C(X). This is a strong and useful result because we can put up a Markov Generator with the description of a Markov process, and then we know that there is a unique Markov process according to this generator. On the other hand, it is very difficult to identify a Markov process according to its semigroup. Interacting particle systems Interacting particle systems consider the evolution of a set of particles which interact ones with others. The evolution of every single particle is not a Markov process because of the interactions. However, the evolution of the global set is, in fact, a Markov process. For this reason, the objective of interacting systems is to study the behaviour of the set of particles. Sistemas Interactivos: modelo del votante V It is important to realise that this kind of problems are easily understood. Although, it is very difficult to create tools to develop the mathematical problem. In addition, only the asymptotic behaviour of the systems can be descibed. The set of particles is often really big; for example, the number of ions in a magnetic solid. Thus, the mathematical models are infinite. Incentives This kind of models appeared in the 1970’s because there were some problems in Physics involving macroscopic processes which needed a mathematical model. The first model was probably the Ising model, which models the ferromagnetism. Firstly, all the models considered only two states for every particle. This kind of interacting sytems are called spins systems. Aferwards, in the 1980’s, appeared the systems with more than two states, which are considerably far more complicated. A spin system is a continuous time Markov process with usually uncontable states space where each particle has values in W={0,1}and with some properties that differences it from other Markov processes. Note that spins systems are different from other interacting systems since in the firsts there is only one stochastic component, but not in the seconds, where there are two. For that reason, spin systems cannot be studied as a particular case of general interacting particle systems. In the following, I am going to talk about spin systems. Let S=Zd,d∈Nbe a set of particles. Then, as each particle takes a value in W={0,1}, the set of states of a spin process in Sis X={0,1}S. Every element of Xis called configuration and it is often representd by ηor ζ. In this way, a configuration is a map η:S−→ W x7→ η(x) that joins every particle xwith the value that takes in the configuration η. An important role in the systems is played by the relationships among the particles. Relationships and particles are represented together as a graph in S. For each x, the set of particles that interact with it is called the neighbourhood of x, and it is usually defined as follows: N(x) = {y∈S:ky−xk1=1}. Autor: Jorge Velilla Gambó VI Capítulo 0. English summary Construction of spin systems and transition rates We assume that only one particle flips at every tansition. Then, the transition rates are defined as the parameter of the exponential time when a particle in Sflips, c(.,.):x∈S,η∈X7−→ c(x,η)∈R+≡[0,+∞) It is important to supose that the rates are not negative, uniformly bounded, continuous in Xand satisfying sup x∈S∑ u∈S sup η∈X|c(x,η)−c(x,ηu)|<∞ where ηu(v) = η(v)for v6=u 1−η(v)for v=u is the the configuration which takes the same values of ηin every v6=u, and the other in u. With this hypothesis, we can build a Markov generator according to the transition rates and thanks to Hille-Yosida theorem, the spin system is well defined as a Markov process. Tools The two basic tools for working on spin systems are Coupling and Duality. Coupling consists on constructing two or more stochastic processes in the same probability space, whic have a non trivial relationship. Duality is not as generally used as Coupling. Houwever, when one can use it, it is very useful. It consists on defining a new stochastic process ζtin Y={Afinite : A⊆S∪{∞}}joined with the main process ηtby a function H, Eη[H(ηt,ζ)] = Eζ[H(η,ζt)] ∀η∈X,∀ζ∈Y,t≥0. Note that if ηtis a spin system, then the dual process ζtis a Marcov chain. The more useful functions are H1(η,A) =    ∏ x∈A∩S [1−η(x)] if ∞/∈A −∏ x∈A∩S [1−η(x)] if ∞∈A H2(η,A) =    ∏ x∈A∩S [2η(x)−1]if ∞/∈A −∏ x∈A∩S [2η(x)−1]if ∞∈A, which produce the named coalescence and anhiquilation dual processes, respectively. Coalescence duality is going to play an important role in the study of the voter model. Sistemas Interactivos: modelo del votante VII Voter model The voter model is a particular kind of interacting particle system where every element of Sis an individual connected with others. Each connection means that there exists a relationship among both individuals. Supose that there is a political question and every individual has its own opinion. The opinions can change according to the neighbourhood of every individual. Simple voter model The simple voter model is the spin system corresponding to the voter model when there are only two different opinions. Then, X={0,1}S. The transition rates of the simple voter model are often given by c(x,η) =      ∑ y∈N(x) 1 2dη(y)if η(x) = 0 ∑ y∈N(x) 1 2d(1−η(y)) if η(x) = 1 It means that the individual in xwaits an exponential time of parameter 1 and then flips its value: it takes the value of the neighbour y, chosen uniformly. Note that the waiting time has to be exponential due to the absence of memory. In other case, the process would not be a Markov process. Some important and intuitive properties of the rates and of the model are the following: - the configurations which correspond to the both consensus opinions are invariant, - we can change the role of zeros and ones without losing generality, - the process is attractive: the more neighbours of xwith different opinion than x, the more probability is there for xto change its value. - the rates are invariant under translations of S. Invariant measures Since both consensus measures are invariant, we know that the process is not going to be ergodic. The main question is wheter I={η≡0,η≡1}. An exhaustive study of this question can be found in [L]. I am going to consider the coalescence dual process, given by Pη(ηt(x)6=ηt(y) = P(η(Xt)6=η(Yt)) for all η∈X, where XteYtare simple random walks on Zdwith Xt=0=x,Yt=0=yand η(Xt),η(Yt)showing the position of the walks in t≥0. Autor: Jorge Velilla Gambó VIII Capítulo 0. English summary On the one hand, we are going to talk about coexistence if there exists a limit distribution with infinite zeros and infinite ones. On the other hand, the process is said to clusterized if it goes to one of the consensus configuration; in other words, if l´ ım t→∞P(ηt(x)6=ηt(y)) = 0. An important result sais that in the simple voter model on Zd,d∈N, i) if d=1 or 2, then I={η≡0,η≡1}. ii) if d≥3, then {η≡0,η≡1}⊂I. Other votel models In the project, voter model with unexpected changes and voter models with more than two opinions are presented but not studied. Threshold voter model The threshold voter model is a voter model in X={0,1}Zd,d∈N. Let T∈Nbe the threshold and N(x) = {y∈S:||y−x||1≤N}. Then the transition rates of the threshold votel model are c(x,η) = 1 if Card{y∈N(x):η(y)6=η(x)}≥T 0 in other case. That is: xchanges its value only if there are Tor more individuals in its neighbourhood with different opinion to it. One importatn theorem says that the threshold voter model clusterizes if and only if d=1 and N(x) = {x−T,...,x+T},T≥1. Special importance has the case T=1: xchanges its value if there is one (or more) individual in its neighbourhood with different opinion to it. Then: i) if N>1 then the process coexists for all d≥1 ii) if d>1 then the process coexists for all N≥1 or equivalently, the threshold voter model with T=1 clusterizes ⇔(N,d) = (1,1). Sistemas Interactivos: modelo del votante IX Simple random walks A I have mentioned, random walks are important in the study of the duality of the simple voter model because the dual model is a simple random walk. A simple random walk in S=Zd,d∈N, is a Markov chain that describes the position of a particle (or walker) in S. Each time the particle moves to a different position than the present one, which is chosen uniformly between the 2dadjoining sites. The family (Xt)t≥1of independent and identically distributed random variables with values in Zd, defined as follows P(Xt=e) = 1 2dif ||e||=1, t∈N 0 in other case, is called steps of the simple random walk. The family (St)t≥0of random variables S0=0 St=n ∑ k=1 Xk=Sn−1+Xnif t∈N is called position of the random walk in time t. Obviously, simple random walks are Markov chains due to the independence of the family (Xt)t≥1. The mentioned adjoining sites of every xare just the neighbourhood of x, as it is defined in the simple voter model, {y∈S:||y−x||1≤1}. Thus, we know the transition rates of the Markov chain, P(Sn+1=y|Sn=x) = 1 2dfor all x∈S,y=x+eand ||e||=1 0 in other case. A state x∈Sis said to be recurrent if the chain is going to be there infinitely often with probability 1. We know that being recurrent is a common property in all the states that comunicate, and in a simple random walk, every state comunicates with all the others (there is a positive probability of going from a state to every other state in a finite number of steps). Then, a simple random walk is a recurrent Markov chain if and only if S=Zor Z2. This is probably the most important result of the chapter. Its importance resides in the dual problem and the clustering and coalescence theorem, which is proved using this result. Applications of the voter model Some current studies about voter models have checked the effectiveness of voter model modeling not only votings, but also other diverse processes, such as - marketing - social networks Autor: Jorge Velilla Gambó 2Capítulo 1. Procesos de Markov y sistemas interactivos continuas por la derecha y con límites por la izquierda. Para cada s∈[0,∞)sea πs:D[0,∞)−→ X η.7−→ ηs Sea Fla σ−álgebra más pequeña en D[0,∞)que hace {πs}s∈[0,∞)medibles. Para cada t∈[0,∞) sea Ftla σ−álgebra más pequeña que hace medibles {πs}s≤ten D[0,∞). Definición 1.1.1. Un proceso de Markov en tiempo continuo en X es una colección de medidas de probabilidad (o probabilidades) {Pη:η∈X}en D[0,∞)indexadas por X con las siguientes propiedades: (a) Pη(ζ.∈D[0,∞):ζ0=η) = 1∀η∈X, (b) La aplicación X →[0,1]tal que η7→Pη(A), A ∈F, es medible para todo A, (c) Pη(ηs+.∈A|Fs) = Pηs(A)∀η∈X,A∈F(Propiedad de Markov). Sea C(X)el conjunto de funciones continuas de Xen X, que es un espacio de Banach con la norma del supremo ||f||:=supη∈X{|f(η)|},f∈C(X). Para cada Z∈D[0,∞), se define la esperanza Eη(Z) = ZD[0,∞) Z dPη si Z es Pη−integrable. Así, para cada f∈C(X), se define el operador lineal (S(t)f)(η) = Eη[f(ηt)],t∈[0,∞),η∈X. Definición 1.1.2. Un proceso de Markov {Pη;η∈X}se dice que es un proceso de Feller si S(t)f∈C(X)∀f∈C(X). Proposición 1.1.3. Sea {Pη;η∈X}un proceso de Feller en X. Entonces la colección de operadores lineales {S(t);t≥0}en C(X)cumple: (a) S(0) = I la función identidad en C(X), (b) La aplicación [0,∞)→C(X)tal que t 7→S(t)f es continua por la derecha para toda f ∈C(X), (c) S(t+s)f=S(t)S(s)f∀s,t≥0,f∈C(X), (d) S(t)1=1la función unidad, ∀t≥0, (e) S(t)f≥0∀t≥0,f∈C(X)no negativa. Sistemas Interactivos: modelo del votante 1.1. Introducción, propiedades características y notación 3 Demostración: Puede consultarse en [L]. Definición 1.1.4. Una familia {S(t);t≥0}de operadores lineales en C(X)cumpliendo las cinco condiciones de (1.1.3) se llama semigrupo de Markov. Notar que la aplicación t7→ S(t)fes uniformemente continua para cada f∈C(X)pues ||S(t+ ε)f−S(t)f||=||S(t)[S(ε)−I]f||≤||S(ε)f−f||. La importancia de los semigrupos de Markov se debe a que caracterizan biyectivamente los procesos de Markov. Teorema 1.1.5. Sea {S(t);t≥0}un semigrupo de Markov en C(X). Entonces existe un único proceso de Markov {Pη;η∈X}en X tal que S(t)f(η) = Eη[f(ηt)],∀f∈C(X),η∈X,t≥0. Demostración: La demostración de este resultado puede consultarse en libros clásicos de procesos de Markov, como [BG]. Por lo tanto, para construir un proceso de Feller basta encontrar el correspondiente semigrupo de Markov. Sea P={medidas de probabilidad en X}con la topología inducida por la convergencia débil: µn w −→µen P. Pes compacto con esta topología y así, si µ∈Py{Pη;η∈X}es un proceso de Markov en X, entonces el proceso de Markov con distribución inicial µes un proceso estocástico ηt;t≥0 con distribución Pµ:=ZX Pηµ(dη); como consecuencia, Eµ[f(ηt)] = RXS(t)f dµ,f∈C(X). Definición 1.1.6. Sea {S(t);t≥0}semigrupo de Markov en C(X). Si µ∈P, entonces µS(t)∈ P,t≥0, con ZX f d(µS(t)) = ZX S(t)f dµ,∀f∈C(X). En otras palabras, la probabilidad µS(t)se interpreta como la distribución en tiempo tdel proceso cuando la distribución inicial es µ. Definición 1.1.7. µ∈Pse dice invariante para el proceso de Markov con semigrupo {S(t);t≥0} si µS(t) = µ∀t≥0. El conjunto de medidas invariantes se denota I. Proposición 1.1.8. Propiedades de I: a) µ∈I⇔RXS(t)f dµ=RXf dµ, Autor: Jorge Velilla Gambó 4Capítulo 1. Procesos de Markov y sistemas interactivos b) I es compacto y convexo en P, c) Si ∃ν=l´ ım t→∞µS(t),µ∈P, entonces ν∈I, d) I 6=φ. Demostración: Puede consultarse en [L], páginas 10-11. La definición (1.1.7) está motivada por la búsqueda de resultados asintóticos de los procesos de Markov. En particular, como se mencionará más adelante, el comportamiento asintótico de los sistemas interactivos es muy importante, ya que el comportamiento transitorio es, en muchos casos, imposible o muy difícil de estudiar y menos importante desde el punto de vista del modelo. Sea µ∈Py consideremos el proceso de Markov ηt,t≥0 con distribución inicial µ. Entonces µ∈I⇔ {ηt+s,t≥0}y{ηt,t≥0}tienen la misma distribución ∀s≥0. Definición 1.1.9. Un proceso de Markov con semigrupo {S(t);t≥0}se dice ergódico si existe ν∈P tal que: i) I ={ν}, ii) l´ ım t→∞µS(t) = ν∀µ∈P. Es decir, un proceso de Markov es ergódico cuando, partiendo de cualquier distribución inicial, siempre se llega a la misma distribución pasado cierto tiempo. Generadores de Markov Definición 1.1.10. Un operador lineal con dominio D(Ω) Ω:D(Ω)−→ C(X) se dice que es un pregenerador de Markov si: (a) 1∈D(Ω),Ω1=0, (b) D(Ω)⊆C(X)denso, (c) f ∈D(Ω),λ≥0,g:=f−λΩf⇒m´ ın ξ∈X f(ξ)≥m´ ın ξ∈X g(ξ). Definición 1.1.11. Ω:C(X)→C(X)se dice cerrado si su grafo es cerrado en C(X)×C(X). La menor extensión cerrada de Ωse llama clausura de Ω, y se denota Ω Proposición 1.1.12. Sea Ωpregenerador de Markov. Entonces, existe Ωclausura de Ωque también es pregenerador de Markov. Sistemas Interactivos: modelo del votante 1.1. Introducción, propiedades características y notación 5 Demostración: Puede consultarse en [L], páginas 13-14. Proposición 1.1.13. Sea Ωun pregenerador de Markov cerrado. Entonces, Im(I−λΩ) = Rang(I− λΩ)⊆C(X)cerrado ∀λ≥0. Demostración: Puede consultarse en [L], página 14. Definición 1.1.14. Un generador de Markov es un pregenerador de Markov Ωcerrado que satisface Im(I−λΩ) = C(X) para todo λ>0suficientemente pequeño. En particular: Proposición 1.1.15. Un pregenerador de Markov acotado es un generador de Markov. En particular, si Ωpregenerador de Markov acotado, Im(I−λΩ) = C(X)∀λ≥0. Veamos ahora la utilidad de los generadores de Markov. Hasta ahora hemos visto que un proceso de Markov se puede definir a través del correspondiente semigrupo de Markov. Sin embargo no es necesariamente fácil y mucho menos intuitivo construir un semigrupo que corresponda a un proceso de Markov que modele un problema de interés. Sin embargo, no ocurre lo mismo con los generadores, ya que es posible identificar (y definir) el generador asociado con un modelo que nos interese. Es decir, se es capaz de asociar a muchos modelos el generador que les corresponde. Pues bien, el teorema de Hille-Yosida que se enuncia a continuación es un potente resultado que muestra la existencia de una biyección entre semigrupos y generadores de Markov, proporcionando además la forma explícita de pasar de unos a otros. Este resultado nos permitirá, a partir de este momento construir el generador y, consecuentemente, el proceso de Markov que corresponde a diversos modelos de sistemas de partículas interactivas, en particular el modelo del votante que es en el que centraremos nuestro interés. Teorema 1.1.16. (Hille - Yosida) Existe una correspondencia biyectiva entre los generadores de Markov en C(X)y los semigrupos de Markov en C(X)dada por: (a) D(Ω) = {f∈C(X):∃l´ ım t→0+ S(t)f−f t}, Ωf:=l´ ım t→0+ S(t)f−f t,f∈D(Ω)⊆C(X). (b) S(t)f=l´ ım n→∞(I−t nΩ)−nf,f∈C(X),t≥0. (c) f∈D(Ω)⇒S(t)f∈D(Ω),dS(t)f dt = (ΩS(t)) f= (S(t)Ω)f,t≥0 Autor: Jorge Velilla Gambó 6Capítulo 1. Procesos de Markov y sistemas interactivos (d) g∈C(X),λ≥0,g:=f−λ⇒f= ∞ Z 0 e−tS(λt)gdt. Como se acaba de mencionar, el teorema de Hille-Yosida se usa para construir procesos de Markov de la siguiente manera: una definición infinitesimal del problema se usa para construir un pregenerador Ωde Markov, lo que es relativamente fácil pues es sencillo verificar las hipótesis necesarias. Posteriormente, con las definiciones y proposiciones anteriores se obtiene el generador, lo que puede requerir de algunos tecnicismos que se escapan al objeto de este trabajo y pueden consultarse en [L], capítulos I, III. Una vez obtenido el generador, con ayuda del teorema anterior, tendremos el semigrupo y, por tanto, el proceso de Markov. 1.1.2. Sistemas interactivos. Definición y características Los sistemas de partículas interactivas consideran la evolución de un conjunto de partículas que interactúan unas con otras a lo largo del tiempo. En estos sistemas, la evolución individual de cada partícula no presenta interés pues no es markoviana debido a las interacciones, pero la evolución global del conjunto sí que cumple la propiedad de Markov, lo que no sólo añade interés al modelo sino que además permite un estudio detallado del mismo. Una de las características comunes de este tipo de procesos es, como se ha dejado ver antes, el contraste entre la facilidad de comprensión del problema, que es muy intuitivo, y la dificultad tanto de los resultados como de los desarrollos necesarios para obtenerlos, pues hace falta desarrollar técnicas específicas complejas. Esto se debe a que, por la naturaleza de los procesos, generalmente el comportamiento transitorio es extremadamente difícil de describir (incluso imposible en algunos casos). Por eso, buscaremos siempre resultados asintóticos y cualitativos de los sistemas. Por otra parte, es esencial entender que hay muy pocos resultados generales que puedan aplicarse a los sistemas interactivos en su conjunto. Generalmente se trabaja particularmente con cada modelo y se crean y desarrollan técnicas específicas para el mismo, que rara vez son aplicables a otros modelos. En cuanto al conjunto de partículas en sí, los sistemas interactivos estudian grandes cantidades de partículas. Es por esto que, aunque en la realidad ningún modelo sea infinito, los modelos se desarrollan en espacios infinitos. Esto se debe a que es más sencillo trabajar con sistemas infinitos que con sistemas con un número muy elevado de partículas (por ejemplo, la población estadounidense es del orden de 108, o el número de iones en un sólido magnético, que es muy superior). Por lo tanto, el modelo en un espacio infinito no sólo será más sencillo sino que se adaptará mejor a la realidad. Motivaciones para el estudio Durante la década de 1970 se empiezan a estudiar y a desarrollar este tipo de modelos de grandes masas de partículas con interacciones entre ellas debido a su capacidad para modelar procesos macroscópicos reales, que empezaban a ser importantes en física. Como ya se ha mencionado varias veces, en estos procesos es importante estudiar el desarrollo en el tiempo de un sistema con muchos Sistemas Interactivos: modelo del votante 1.1. Introducción, propiedades características y notación 7 individuos desde el punto de vista global. Primero surgieron los modelos de partículas con dos estados: el modelo de Ising para el ferromagnetismo [WL], el modelo de contacto [L] para modelar la difusión de enfermedades y el modelo del votante. A este tipo de modelos se les llama modelos de spin. Así pues, aparte del interés de estos modelos desde el punto de vista de la Teoría de la Probabilidad como procesos de Markov, el motivo de estudio de estos procesos fue su capacidad para modelar fenómenos reales. Posteriormente, a partir de la década de 1980, se desarrollan los procesos de partículas con más de dos estados [LL], cuyo interés es obviamente mayor pues modelan más variedad de procesos reales, como la genética de las poblaciones o el modelo de Potts, que es una generalización del modelo de Ising de gran aplicación en el reconocimiento de imágenes. Definición 1.1.17. Un sistema de partículas interactivas, o sistema interactivo, es un proceso de Markov en tiempo continuo y en el que cada partícula toma valores en un espacio W, con espacio de estados X generalmente no contable y con una serie de características específicas que lo diferencian de otros tipos de procesos de Markov en tiempo contínuo. Definición 1.1.18. Un proceso de spin es un sistema interactivo con W ={0,1}. Es decir, cada partícula puede tomar únicamente dos posibles valores, que por convenio se denotan 0 y 1. Nótese que un proceso de spin no puede estudiarse como una particularización de un sistema interactivo con espacio de estados W={0,1,...,n},n∈N. Esto se debe a que cuando hay dos posibles estados para cada partícula, los cambios están completamente determinados: una partícula que tiene un valor sólo puede cambiar al otro posible. Por el contrario, en los procesos con más de dos estados los cambios son estocásticos: hay una componente estocástica que no aparece en los procesos de spin debido a que una particula elige el valor al que cambia de acuerdo con alguna distribución de probabilidad. A partir de ahora, vamos a hablar de procesos de spin. Fijemos el espacio del proceso. Sean d=1,2,... y S=Z×...×Z=Zd el conjunto de puntos del plano con coordenadas enteras. Suponemos que en cada punto de Shay una y sólo una partícula. Cada partícula tiene un valor en el espacio de estados W={0,1}, que no hay que confundir con el espacio de estados del proceso. Se dirá que x∈Stoma el valor o está en el estado i∈W,i=0,1. Pero esto no es suficiente. Como se ha dicho, no interesa estudiar el comportamiento de las partículas individualmente, sino el del sistema en conjunto. Por ello, el sistema queda caracterizado por el valor que toman todas las partículas de S=Zd, o lo que es lo mismo, el proceso toma valores en el espacio X={0,1}Zd Autor: Jorge Velilla Gambó 8Capítulo 1. Procesos de Markov y sistemas interactivos denominado espacio de las configuraciones del sistema (o espacio de estados del proceso). A cada elemento de Xse le llama configuración del sistema. Así, una configuración es una función η:S−→ W x7→ η(x) que a cada partícula xle asigna el estado (0 ó 1 en nuestro caso) que toma en la configuración η. En los casos de procesos de spin en los que Ssea finito, como Wtambién lo es, Xserá finito y estos apenas tendrán interés ya que el comportamiento de los procesos de Markov con espacio de estados finito es suficientemente conocido. Sin embargo cuando Sno sea finito, Xno será contable, y es entonces cuando surgen los problemas más interesantes. Antes de definir el proceso, hay que notar que hasta ahora solamente se ha hablado de las partículas, pero una parte igual de importante en los sistemas son las interacciones entre las partículas. Estas interacciones pretenden modelar las interacciones en el mundo real. Obviamente dos personas, una sana y otra infectada en un proceso de contacto, no siempre interactúan; lo harán dependiendo de la relación que haya entre ellos. Por tanto, en los modelos interactivos no todas las partículas tienen interacciones con cada una de las restantes. Al conjunto de partículas con las que interactúa x∈Sse le llama conjunto de los vecinos de x,N(x)⊂S. Generalmente se trabaja con el conjunto de vecinos más cercanos, N(x) = {y∈S:ky−xk1=1}. Una vez definidos los espacios en los que vamos a trabajar, vamos a ver cómo se desarrollan teóricamente los modelos interactivos, que parecen tan intuitivos. 1.2. Construcción de los procesos de spin Como se ha dicho en (1.1.18), los procesos de spin son un caso particular de sistema interactivo: aquellos que están definidos en X={0,1}S, donde Ses el conjunto de partículas. Las interpretaciones de los valores 0 y 1 que puede tomar cada partícula son muchas y dependen del modelo; los modelos más famosos son el modelo de Ising para el ferromagnetismo (modela el valor de los spines de los átomos de un sólido de hierro sometido a una fuerza magnética), el modelo de contacto (modela el estado, sano o enfermo, de una población y la propagación de enfermedades) y el modelo del votante (modela la opinión, a favor o en contra, de una población acerca de una idea). Empecemos a describir el mecanismo de transición de las partículas. Para ello, es importante suponer que sólo una partícula puede cambiar su valor en Wen cada transición. Definición 1.2.1. Se llaman tasas de cambio a las funciones c(.,.):x∈S,η∈X7−→ c(x,η)∈R+≡[0,+∞) que representan el parámetro de tiempo exponencial que le cuesta a la partícula situada en x ∈S cambiar su valor al otro posible en W cuando la configuración global del sistema es η∈X. Sistemas Interactivos: modelo del votante 1.2. Construcción de los procesos de spin 9 Nota.- La distribución exponencial es una distribución de probabilidad absolutamente continua con un parámetro positivo, que se denota Exp(λ),λ>0. Su función de densidad es: f(x) = λe−λxpara x≥0 0 de otro modo , y su función de distribución: F(x) = P(X≤x) = 0 para x<0 1−e−λxpara x≥0 La característica fundamental de esta distribución es su falta de memoria: P(X>t+s|X>s) = P(X>t),t,s≥0, que es fundamental para que los procesos tengan la propiedad markoviana. Volviendo al problema de definir los procesos de spin, el proceso ηt,t≥0 con espacio de estados {0,1}definido sobre un conjunto Sde partículas satisface: Pη(ηt(x)6=η(x)) = c(x,η)t+o(t)(1.1) si t→0+, para cada x∈S,η∈X. La hipótesis de que sólo una partícula cambia en cada transición equivale a Pη(ηt(x)6=η(x),ηt(y)6=η(y)) = o(t)(1.2) cuando t→0+,x6=y∈S,η∈X. Nótese que las interacciones entre individuos quedan recogidas en la dependencia que tiene la función c(.,.)de η∈X. Para una descripción formal de los procesos de spin hace falta seguir los pasos marcados en las conclusiones del teorema (1.1.16). Supongamos que c(x,η)es no negativa, uniformemente acotada y continua en ηpara cada x∈S, y satisface sup x∈S∑ u∈S sup η∈X|c(x,η)−c(x,ηu)|<∞(1.3) donde ηu∈Xestá definido como ηu(v) = η(v)para v6=u 1−η(v)para v=u Notemos que ηuyηcoinciden en todos los puntos de Ssalvo en u. La hipótesis (1.3) implica que la clausura en C(X)del operador Ωdefinido en D(X) = {funciones en Xque sólo dependen de un número finito de coordenadas }como Ωf(η) = ∑ x∈S c(x,η)(f(ηx)−f(η)) (1.4) Autor: Jorge Velilla Gambó 10 Capítulo 1. Procesos de Markov y sistemas interactivos es el generador de Markov de un semigrupo S(t). La construcción de este pregenerador puede verse en [L], capítulo I, apartado 3.9, y se sale de los objetivos del trabajo. Por (1.1.5), existe un único proceso de Markov ηt,t≥0 en Xcorrespondiente al semigrupo S(t), y este es el proceso de spin cuyas tasas de cambio satisfacen (1,1) y (1.2). Recíprocamente, también es el único proceso de Feller en Xque satisface (1.1) y (1.2). 1.3. Herramientas básicas para el estudio 1.3.1. Coupling El coupling es una herramienta muy importante que se emplea en el estudio de los sistemas de partículas interactivas, pues resulta aplicable en muchas ocasiones. Un coupling es la construcción de dos o más procesos estocásticos en un espacio de probabilidades común, relacionados de manera no trivial. En particular, las distribuciones marginales deben coincidir con las distribuciones originales de los procesos que lo forman. El interés del coupling descansa en que, utilizándolo adecuadamente y eligiendo bien los procesos a comparar, muchas propiedades del proceso original se pueden obtener a partir del estudio del coupling. Así, si este se ha construido de manera que resulte más simple que el proceso original, se pueden obtener de forma más cómoda propiedades del último. Coupling para procesos de spin Sean c1(x,η),c2(x,η)tasas de cambio uniformemente acotadas y no negativas, cumpliendo sup x∈X∑ v∈S sup η∈X|ci(x,η)−ci(x,ηv)|<∞,i=1,2. Introducimos un coupling básico o coupling de Vasershtein. Sean ηtyζtlos procesos de spin correspondientes a las tasas c1yc2. Mientras ηt(x)6=ζt(x),t≥0,x∈S, los dos procesos se desarrollan independientemente el uno del otro. En el momento en que ηt(x0) = ζt(x0), los dos procesos evolucionaran juntos, con tasa de cambios c(x,η,ζ) = m´ ın{c1(x,η),c2(x,ζ)}. Como se ha mencionado, el coupling es una herramienta que sirve para demostrar algunas propiedades de los procesos de spin tales como: Proposición 1.3.1. Sean ηtyζtdos procesos de spin con tasas de cambio c1(.,.)y c2(.,.)yηt≥ζt, y el proceso con semigrupo S2(t)ergódico con 0medida invariante, entonces 0es medida invariante para el otro proceso. Otro tipo de Coupling se define como sigue. Sean ηt,ζt,ξttres procesos de spin y sean c(x,η) tasas de cambio cumpliendo las hipótesis (1.2), (1.3), se definen: c(c,ξ) = sup{|c(x,η)−c(x,ζ)|:|η(u)−ζ(u)|≤ξ(u)∀u∈S}si ξ(x) = 0 c(c,ξ) = ´ ınf{|c(x,η)+c(x,ζ)|:η(x)6=ζ(x),|η(u)−ζ(u)|≤ξ(u)∀u∈S}si ξ(x) = 1 Sistemas Interactivos: modelo del votante 1.3. Herramientas básicas para el estudio 11 que son contínuas en ξy satisfacen sup x,ξ c(x,η)≤2sup x,η c(x,η),|c(x,ξu)−c(x,ξ)|≤2sup η|c(x,ηu)−c(x,η)| para u6=x(luego son uniformemente contínuas y satisfacen la hipótesis (1.3)). Proposición 1.3.2. Sea ξtel proceso de spin con tasas c(.,.). Entonces: a) c(x,ξ) = 0si ξ=0, entonces ξ≡0es absorbente. b) c(.,.)es creciente en ξsi ξ(x) = 0y decreciente si ξ(x) = 1. c) Si el proceso correspondiente a c(.,.)es ergódico, el correspondiente a c(.,.)también lo es. 1.3.2. Dualidad Cuando es aplicable, la dualidad es una herramienta extremadamente útil. La relación de dualidad asocia un proceso de spin con otro proceso que llamaremos dual de manera que el proceso de interés pueda reformularse como un proceso envolviendo al dual. Si el proceso dual es sustancialmente más simple que el original o lo cambia a una formulación más simple, entonces se estudia este y después se reformulan los resultados en términos del proceso de spin inicial. Dado un proceso de spin definido en {0,1}S, el proceso dual, si existe, es un proceso de Markov en espacio de estados contable: una cadena de Markov. Definición 1.3.3. Sean ηtyζtdos procesos de Markov con espacios de estados X e Y respectivamente. Sea H(η,ζ)una función medible acotada en X ×Y. Los procesos son duales uno del otro con respecto a H si: Eη[H(ηt,ζ)] = Eζ[H(η,ζt)] ∀η∈X,∀ζ∈Y,t≥0. Es inmediato que la dualidad entre dos procesos constituye una relación reflexiva. Dualidad en los procesos de spin Tomemos Y={A:A⊆S∪{∞},Card(A)<∞}, que es contable. El proceso dual de un proceso de spin es una cadena de Markov en Y. La inclusión de {∞}garantiza la no negatividad de las tasas c(x,η). Las dos funciones Hmás útiles son: H1(η,A) =    ∏ x∈A∩S [1−η(x)] si ∞/∈A −∏ x∈A∩S [1−η(x)] si ∞∈A(1.5) H2(η,A) =    ∏ x∈A∩S [2η(x)−1]si ∞/∈A −∏ x∈A∩S [2η(x)−1]si ∞∈A(1.6) Autor: Jorge Velilla Gambó 18 Capítulo 2. Modelo del votante Para esto, vamos a trabajar con el proceso dual de coalescencia. Un estudio exhaustivo del modelo dual puede consultarse en [L], capítulo V, páginas 227 - 246. Consideremos el proceso dual con funcion (1.5), que resulta en el proceso con tasas (1.7) verificando las hipótesis (1.9). Relación de dualidad: Dos procesos estocásticos ηtyAt,t≥0 se dicen duales (uno del otro) si Pη(ηt(x) = 1 en x∈A) = PA(η(At)≡1)(2.4) donde η∈Xes una configuración, ηtla configuración a tiempo t≥0 partiendo de ηyA={x∈S: η(x) = 1}es el estado inicial del recorrido aleatorio simple Aten S, con tasas {p(x,y)}. En el apéndice de este capítulo se presentan los recorridos aleatorios simples y algunos resultados de los mismos, debido a que las demostraciones de algunos resultados importantes del modelo del votante simple están fuertemente relacionadas con este tipo de procesos estocásticos (a causa del papel que juega la dualidad). Tenemos, pues, un recorrido aleatorio simple Aten Zd, con tasas p(x,y)homogéneas: p(x,y) = p(0,x−y)para cada x,y∈Zd(la homogeneidad de las tasas del proceso dual viene de la homogeneidad en el tiempo de las tasas del modelo original). Nótese que el recorrido aleatorio es simple gracias a la elección de p(x,y)uniforme en (2.2). Entonces, la relación de dualidad dada en (2.4) es equivalente a Pη(ηt(x)6=ηt(y)) = P(η(Xt)6=η(Yt)) para toda η∈X,(2.5) donde XteYtson recorridos aleatorios simples en Zdcon Xt=0=x,Yt=0=yyη(Xt),η(Yt)indican las posiciones de los caminos en el tiempo t≥0. XteYtse comportan de la manera descrita en el capítulo primero, correspondiente al proceso dual de coalescencia. Estamos interesados en estudiar el comportamiento asintótico del modelo. Ya hemos mencionado que cuando se alcance el consenso, si es que se alcanza, el modelo permanecerá invariante. Nos preguntamos si es posible que el modelo, a la larga, mantenga una estructura de coexistencia de las dos opiniones en equilibrio. Definición 2.1.1. Diremos que hay coexistencia en un modelo del votante cuando hay una distribución límite con infinitas partículas tomando el valor 1 e infinitas tomando el valor 0. Además, se definen los clusters (o polos) del proceso como las componentes conexas de {x∈S : ηt(x) = 0}o de {x∈S : ηt(x) = 1}para t ≥0. Definición 2.1.2. Diremos que un modelo del votante se clusteriza (o se polariza) si para cualesquiera x,y∈S y para cualquier η∈X, se cumple: l´ ım t→∞P(ηt(x)6=ηt(y)) = 0. Sistemas Interactivos: modelo del votante 2.1. Modelo del votante simple 19 En otras palabras, el proceso se clusteriza cuando con el tiempo tiende a una de las dos configuraciones de consenso. Teorema 2.1.3. En el modelo del votante simple en Zd, d ∈N, se cumple que: i) si d =1ó2, entonces el proceso se clusteriza. ii) si d ≥3, entonces el proceso coexiste. Corolario 2.1.4. En el modelo del votante simple en Zd, d ∈N, se cumple que: i) si d =1ó2, entonces I ={η≡0,η≡1}. ii) si d ≥3, entonces {η≡0,η≡1} ⊂ I y el contenido es estricto, es decir, hay más medidas invariantes. Demostración: Inmediata por el Teorema 2.1.3 y las definiciones de modelo en coexistencia, 2.1.1, y modelo clusterizado, 2.1.2.  Demostración del teorema: Por la relación de dualidad (2.5), el estudio se reduce al proceso dual de coalescencia. Xt−Ytes un recorrido aleatorio simple, luego una cadena de Markov. Aplicando el Teorema de Polyá (2.2.8 del apéndice), tenemos que Xt−Ytes recurrente ⇐⇒d=1,2 de donde se sigue que P(x,y)(η(Xt)6=η(Yt)) t→∞ −−→0,∀x,y∈Zd,η∈X,d=1,2; y por consiguiente, Pη(ηt(x)6=ηt(y)) t→∞ −−→0,∀x,y∈Zd,η∈X,d=1,2. Como consecuencia, el proceso se clusteriza por definición e I={η≡0,η≡1}. Sin embargo, si d≥3, entonces P(x,y)(η(Xt)6=η(Yt)) no tiende a 0 cuando t→∞∀x,y∈Zd, luego el proceso no se clusteriza y necesariamente hay más configuraciones asintóticas invariantes: {η≡0,η≡1}⊂Iy el contenido es estricto.  Conclusión: En los modelos del votante simple que resultan de considerar poblaciones en el plano, que son los más habituales, el consenso es la única posibilidad a largo plazo. Esto nos podría hacer pensar que el modelo no se corresponde con la realidad. Sin embargo, el consenso es un comportamiento asintótico, y no se puede considerar que ninguna votación se desarrolle durante un periodo de tiempo lo suficientemente largo como para que se considere que el tiempo es ”infinito”. La aparición y desaparición de partidos políticos y la renovación de ideas de los mismos también influyen, pues una opinión no Autor: Jorge Velilla Gambó 20 Capítulo 2. Modelo del votante tiene por qué corresponder siempre al mismo partido. En la última sección del capítulo se mencionará cómo el modelo del votante puede adaptarse para modelar una votación real. Así mismo, se incluye una simulación en OCTAVE de diez mil etapas del modelo del votante simple en un cuadrado de Z2. Figura 2.1: Configuración en la primera etapa de un modelo del votante simple en un cuadrado de 1600 individuos de Z2. Figura 2.2: Configuración al final de la simulación del mismo modelo. Sistemas Interactivos: modelo del votante 2.2. Otros modelos del votante 21 2.2. Otros modelos del votante 2.2.1. Modelo del votante simple con cambios espontáneos En este tipo de modelo se considera el mismo espacio Xque en el modelo del votante simple. La diferencia es que se da la posibilidad de que un individuo cambie espontáneamente su opinión a la contraria, independientemente de sus vecinos y de las interacciones con los mismos. Las tasas de cambio de este modelo son: c(x,η) =    δ+∑ y∈S p(x,y)η(y)si η(x) = 0 δ+∑ y∈S p(x,y)(1−η(y)) si η(x) = 1,(2.6) con δ≥0 y p(x,y)definidos como en (2.2). Es decir, una partícula cambia su valor al otro posible por el mecanismo descrito en la sección 2.1 y, además, también lo hace tras tiempos exponenciales de parámetro δ, independientemente de los valores de sus vecinos (como antes, el tiempo es exponencial debido a la falta de memoria de esta distribución, para que el proceso sea de Markov). Así pues, sería posible, por ejemplo, el cambio Figura 2.3: transición de η≡0 a η(0) = 1,η(x) = 0∀x6=0. Es inmediato que las configuraciones de consenso en este modelo no son invariantes. El estudio de las medidas invariantes se ha realizado en el caso de Sfinito por Moran, P.A.P (1958)(Random processes in genetics, Proceedings of the Cambridge Philosophical Society, 54, pp. 60-71) y en el caso de Sinfinito por Gravnosky y Madras (1995)(The noisy voter model, Stochastic processes and their applications, 55, pp. 23-43). 2.2.2. Modelos del votante con opción múltiple Sea M∈N. Supongamos que ahora cada individuo de Stiene M≥2 opiniones, o lo que es lo mismo, W={1, ... , M}. Entonces, estamos ante un sistema de partículas interactivas en el espacio X={1, ... , M}S, que no es un sistema de spin. Autor: Jorge Velilla Gambó 22 Capítulo 2. Modelo del votante En estos procesos en los que el espacio Westá formado por más de dos elementos, como ya se mencionó en el capítulo 1, es necesario un estudio más complejo debido a la existencia de dos condiciones estocásticas: 1) un individuo puede cambiar su valor a cualquiera de los otros M−1 valores: hay que determinar cómo se elige este valor, 2) hay que determinar el mecanismo de cambio a ese valor. Esto se traduce en la existencia de Mtasas de cambio, que se escriben: ck(x,η) = ∑ y∈S pk(x,y)1{η(y)=k},η∈X,x∈S,k∈W siendo 1{.}la función indicadora de {.}. Los pesos pk(x,.)son una distribución de probabilidades para cada kyx. El mecanismo es el siguiente: la partícula situada en x, tras un tiempo exponencial de parámetro r=Card(N(x)), elige una tasa de cambio y de acuerdo con ella, elige un vecino y toma su opinión. El estudio de este modelo ha sido realizado por Sawyer (1976)(Results for the stepping stone model for migration in population genetics, The Annals of Probability, 4, pp. 699-728) y por Cox y Griffeath (1987)(Recent results for the steppings stone model, in: H.Kesten, ed., Percolation Theory and Ergodic Theory of infinite particle systems (Springer, Nueva York) pp. 73-83). Modelo del votante con opción múltiple y cambios espontáneos Si en el modelo anterior añadimos la posibilidad de que, independientemente de su entorno, una partícula pueda cambiar espontáneamente su valor por el valor k∈Wtras un tiempo exponencial de parámetro δk, entonces ck(x,η) = δk+∑ y∈S pk(x,y)1{η(y)=k},η∈X,x∈Syk∈W. Este modelo ha sido estudiado por Donnelly (1986)(Stochastic Spatial Processes in Lecture Notes in Mathematics, 1212 (Springer-Verlag, Heidelberg), pp. 94-105) cuando Ses finito y por Lopez Lorente (1998) [LL] cuando Sgeneral. También se ha estudiado el caso en que el espacio W= (0,1)es continuo por Bramson (1996)(Spatial models for species area curves, The Annals of Probability, 24, pp. 1727-1751), donde tiene especial interés el proceso dual. Este modelo es importante en el estudio del genoma. 2.2.3. Modelo del votante de tipo umbral El modelo del votante de tipo umbral es un modelo del votante en X={0,1}Zd,d∈N. En general, supongamos que el conjunto de vecinos de x=0, N(0), es la intersección de Zdcon un conjunto compacto, conexo y no vacío de tal manera que N(0)es finito y simétrico. Siempre asumiremos que los vectores canónicos de Zdestán en N(0). Para cada x∈S, se define N(x) = x+N(0). Sistemas Interactivos: modelo del votante 2.2. Otros modelos del votante 23 Sea T∈N. El modelo del votante de tipo umbral, con umbral T, y vecindad N(0)de x=0, es el proceso de spin con tasas c(x,η) = 1 si Card({y∈N(x):η(y)6=η(x)})≥T 0 en otro caso. (2.7) Esto es: x∈Scambia su valor por el contrario cuando está rodeado de To más vecinos que opinan lo contrario a él, o no lo cambia si está rodeado por menos de T. Generalmente, N(0)se elige de manera intuitiva: N(0) = {y∈S:||y||1≤N} para N∈N, de manera que N(x) = {y∈S:||y−x||1≤N}para cada x∈S. Comportamiento asintótico La intuición nos dice que si el umbral Tes pequeño, hay más facilidad para que ocurran cambios y el proceso coexistirá; mientras que si Tes grande, habrá menos cambios y la coexistencia será improbable. Se tienen los siguientes resultados de carácter general: 1) T=|N|−1 0yd=1⇒el proceso se clusteriza. 2) T=θ|N|con θ≤1 4y|N|suficientemente grande en función de d⇒el proceso coexiste. Teorema 2.2.1. d=1,N(0) = {−T,...,T},T≥1⇒el proceso se clusteriza. Demostración (idea): La demostración detallada puede consultarse en [L]. Veamos una idea de la misma. Se construyen dos sucesiones de variables aleatorias (Un)y(Vn),n≥1 tales que - 0 =V0<U1<V1<U2< ..., -(Vk+1−Uk)k≥0son variables aleatorias independientes e idénticamente distribuidas con esperanza finita, -(Vk−Uk)k≥1son variables aleatorias independientes e idénticamente distribuidas con esperanza no finita, -Vk+1−UkyVk−Ukson independientes para todo k. Si definimos A={ηt(.)constantes en N(0)}, para t∈ ∞ [ k=1 [Uk,Vk], se comprueba que P(A)→1, luego Pη(ηt(1)6=ηt(0)) t→∞ −−→0. Este modelo es extremadamente dificil de estudiar cuando d>1 ya que la dualidad no funciona y hay que trabajar con herramientas de coupling. Autor: Jorge Velilla Gambó 24 Capítulo 2. Modelo del votante Caso T=1 Este caso tiene interés especial ya que es el único en el que se sabe con exactitud cómo se comporta el modelo. Las tasas (2.7) pueden escribirse: c(x,η) = 1 si existe y∈N(x)tal que η(y)6=η(x) 0 en otro caso. (2.8) donde N(x) = {y∈S:||y−x||1≤N}determina el número de vecinos de xen función de Ny de d. Por el teorema anterior 2.2.1, si d=N=1, entonces el proceso se clusteriza. Además, se tiene: Teorema 2.2.2. Dado un modelo del votante con umbral T =1, se tiene que: i) Si N >1el proceso coexiste para todo d ≥1. ii) Si d >1el proceso coexiste para todo N ≥1. Demostración: Este resultado se prueba realizando un Coupling entre este proceso y el proceso de contacto con umbral. Puede consultarse en [LT]. Corolario 2.2.3. El modelo del votante con umbral T =1se clusteriza ⇔(N,d) = (1,1). Sistemas Interactivos: modelo del votante 2.3. Aplicaciones de modelos del votante a diversos campos 25 2.3. Aplicaciones de modelos del votante a diversos campos Una de las características del modelo de votante es su versatilidad para incluir diversos modelos que aparecen en situaciones, en principio, muy distantes de los sistemas de partículas interactivas. Revisaremos aquí, a modo de ilustración, algunos de estos modelos. Redes sociales y marketing Quizá uno de los primeros intentos de modelar las redes sociales como sistemas de partículas interactivas puede encontrarse en un par de artículos de Liggett, uno de los pioneros del estudio de los sistemas de partículas interactivas: Bonacich y Lliggett, (2003) (Asymptotics of a matrix valued Markov chain arising in sociology. Stochastic Process. Apl., 104, 155-171) y Liggett y Rolles (2004) (An infinite stochastic model of social network formation, Stochastic Process. Apl., 113, 65-80). Si bien en el primero de estos trabajos los autores consideran un modelo finito, en el segundo ya proponen un modelo infinito que se adecúa a los modelos que hemos considerado. Las redes sociales son consideradas como un medio fundamental para promocionar diferentes cuestiones, desde la extensión de opiniones en uno u otro sentido hasta la difusión y marketing de un nuevo producto. Una red social es una red o grafo en la que los nodos representan individuos y los arcos conexiones entre individuos. Si se consigue que individuos influyentes manifiesten su predilección por un producto o su apoyo a una determinada posición es posible que el producto sea inmediatamente ”comprado” por otros muchos individuos, o la opinión se convierta en una tendencia generalizada. Extensiones inmediatas de este comportamiento son, por ejemplo, el caso en que se requiere un número mínimo de individuos influyentes para que la opinión sea adquirida por otros miembros de la comunidad, es decir, se necesita un umbral mínimo de individuos con una opinión. En este contexto, el modelo del votante porporciona una potente herramienta matemática para modelar este tipo de situaciones. En el contexto descrito anteriormente, la primera situación corresponderá a un modelo del votante clásico y la segunda a un modelo del votante con umbral. En el contexto del marketing en redes sociales, este modelo ha sido recientemente analizado por Even-Dar y Shapira (2011) (Information Processing Letters, 111, 184-187) en el contexto del problema del conjunto de máxima propagación. Este problema puede establecerse en los siguientes términos: supongamos que tenemos un grafo que representa, por ejemplo, una red social. Podemos ”implantar” una opinión en una serie de individuos, pero eso tiene un coste económico y disponemos de un presupuesto limitado. ¿Cómo debemos invertir el presupuesto de manera que en un tiempo t≥0 maximicemos el conjunto de individuos que tienen la opinión? En otras palabras: ¿en quién debemos invertir al inicio para maximizar el conjunto de individuos a los que queremos ”llegar”? El modelo de votante nos permite obtener conclusiones sobre la complejidad algorítmica de este problema y el tiempo necesario para alcanzar un consenso. Recordemos que el modelo del votante clásico tiene dos medidas invariantes que corresponden a los dos estados (si hay dos opiniones) de consenso, todos los individuos tienen la opinión 1 o ninguno la tiene. Modelos de votante con evolución en individuos y en arcos: coevolución. Si analizamos una red como un conjunto de nodos y arcos que los relacionan, una pregunta que surge de manera natural en este tipo de modelos cuando se analiza el comportamiento de poblaciones es si los individuos condicionan su opinión a la de sus vecinos o si la relación de vecindad se establece Autor: Jorge Velilla Gambó 26 Capítulo 2. Modelo del votante en función de las opiniones. Este tipo de modelo ha sido analizado por diversos autores recientemente. Por ejemplo, Holam y Newman (2006) (Physical Review Letters E 74, 056108) consideran un conjunto de Nvértices y Marcos. En cada vértice xhay un individuo con una de Kposibles opiniones, η(x). La proporción de individuos por opinión, N/Mse asume que permanece acotada cuando aumenta el número de individuos. En cada instante del proceso, se elige un individuo aleatoriamente. Si su grado (en el grafo) es cero no sucede anda, pero si su grado es positivo, con probabilidad 1−pel individuo x toma la opinión de y, uno de sus vecinos seleccionado aleatoriamente. Por otra parte, con probabilidad p, se selecciona uno de sus arcos y se corta, creando un nuevo arco que una el individuo situado en el otro extremo de ese arco con un individuo elegido aleatoriamente entre los que tiene la misma opinión que x. El proceso continua hasta que no hay arcos que conecten individuos con distintas opiniones. Notemos que si p=0, se obtiene el modelo de votante clásico. Por el contrario, si p=1 el proceso termina con la descomposición del grafo en Kcomponentes aisladas formadas cada una de ellas por individuos con la misma opinión. Holme y Newman han mostrado mediante simulaciones que existe un valor crítico pctal que si p>pclas opiniones acaban teniendo un pequeño número de seguidores y si p<pcaparece una comunidad ”gigante” con una misma opinión. Recientemente Durret (2012) (Proc. Natl. Acad. Sci. USA, 109, 3682) y Shi, Mucha y Durrett (2013) (Phys. rev. E 88, 062818) han considerado variantes de este modelo. En ambos artículos, se consideran modelos con solo dos opiniones, y además en el segundo también se consideran modelos multiopinión en los que las posibles reconexiones de arcos (ruptura y conexión a otro individuo) se realizan de forma completamente aleatoria. Otras extensiones Otras extensiones del modelo de votante incluyen el modelo de votante-anti votante (Gantert, N.; Löwe, M. y Steif, J.E: (2005), The voter model with anti-voter bonds, Ann. I. H. Poincaré, PR41, 767780) en el que los individuos pueden tomar la opinión de uno de sus vecinos o la contraria: procesos de spin. El estudio de la existencia de distribuciones estacionarias para este modelo se realiza explotando la dualidad existente entre el modelo y el comportamiento de recorridos aleatorios (coalescentes) que evolucionan sobre el grafo en el que está definido el modelo. Otro modelo de interés en el estudio de la evolución de poblaciones es el modelo del votante rebelde, introducido por Sturm y Swart (2008) (Voter models with heterozygosity selection, Ann. Appl. Probab. 18, 59-99), y que es un modelo en el que a las opciones minoritarias se les otorga una ventaja; el que podríamos denominar modelo de votante no exponencial introducido por Takaguchi, T. y Masuda, N. (2011) (Voter model with non-Poissonian interevent intervals, Phys. Rev. E 84, 036115 ) basado en la idea de que si se desean modelar redes sociales, la hipótesis exponencial no es realística; o el modelo de votante con bloque central inicial de Sampaio-Filho, C.I.N. y Moreira, F.G.B. (2011) (Block voter model: Phase diagram) en el que se estudia el efecto del tamaño de un bloque central de individuos con la misma opinión. Desde el punto de vista de las redes sociales podemos mencionar la reciente propuesta de un modelo que intenta recoger el comportamiento global de dichas redes y donde, junto a otros sistemas de partículas interactivas, el modelo de votante juega un papel relevante, Aldoux, D. (2013) (Interacting particle systems as stochastic social dynamics, Bernoulli, 19, 1087-1500). Sistemas Interactivos: modelo del votante 2.3. Aplicaciones de modelos del votante a diversos campos 27 Capacidad del modelo del votante para modelar votaciones Durante las tres últimas décadas se han desarrollado multitud de trabajos estudiando los diferentes modelos del votante y sus comportamientos a largo plazo. Sin embargo, no se había estudiado la capacidad real de modelar del modelo. Recientemente se ha analizado también la adecuación del modelo del votante a situaciones reales estudiando su comportamiento sobre una situación concreta, más específicamente sobre las elecciones presidenciales americanas: Fernández-Gracia, J.; Suchecki, K.; Ramasco, J.J.; San Miguel, M. y Eguíluz, V.M. (2014) (Is the Voter Model a model for voters?, http://arxiv.org/abs/1309.1131v1 ). En una línea también muy aplicada se ha analizado el uso de diversos modelos de votante para obtener consensos vía encuestas o reglas de mayoría: Cruise, J. y Ganesh, A (2013) (Probabilistic consensus via polling and majority rules, http://arxiv.org/abs/1311.4805v1) y la relación entre el modelo del votante y el coloreado de grafos: Chung, F. y Tsiatas , A. (2014) (Hypergraph coloring games and voter models, Internet Mathematics, DOI:10.1080/15427951.2013.833676 ). Autor: Jorge Velilla Gambó