If the nodes of a graph are considered to be identical barrels -- featuring different water levels - and the edges to be (locked) water-filled pipes in between the barrels, one might consider the optimization problem of how much the water level in a fixed barrel can be raised with no pumps available, i.e. by opening and closing the locks in an elaborate succession. This problem originated from the analysis of an opinion formation process and proved to be not only sufficiently intricate in order to be of independent interest, but also algorithmically complex. We deal with both finite and infinite graphs as well as deterministic and random initial water levels and find that the infinite line graph, due to its leanness, behaves much more like a finite graph in this respect.
The Great Filter interpretation of Fermi's great silence asserts that Npq is not a very large number, where N is the number of potentially life-supporting planets in the observable universe, p is the probability that a randomly chosen such planet develops intelligent life to the level of present-day human civilization, and q is the conditional probability that it then goes on to develop a technological supercivilization visible all over the observable universe. Evidence suggests that N is huge, which implies that pq is very small. Hanson (1998) and Bostrom (2008) have argued that the discovery of extraterrestrial life would point towards p not being small and therefore a very small q, which can be seen as bad news for humanity's prospects of colonizing the universe. Here we investigate whether a Bayesian analysis supports their argument, and the answer turns out to depend critically on the choice of prior distribution.
This is a reply to Santer et al., which in turn is a comment on the Johansson et al. paper below.
A key uncertainty in projecting future climate change is the magnitude of equilibrium climate sensitivity (ECS), that is, the eventual increase in global annual average surface temperature in response to a doubling of atmospheric CO2 concentration. The lower bound of the likely range for ECS given in the IPCC Fifth Assessment Report (AR5; refs 1, 2) was revised downwards to 1.5 °C, from 2 °C in its previous report3, mainly as an effect of considering observations over the warming hiatus the period of slowdown of global average temperature increase since the early 2000s. Here we analyse how estimates of ECS change as observations accumulate over time and estimate the contribution of potential causes to the hiatus. We find that including observations over the hiatus reduces the most likely value for ECS from 2.8 °C to 2.5 °C, but that the lower bound of the 90% range remains stable around 2 °C. We also find that the hiatus is primarily attributable to El Nino/Southern Oscillation-related variability and reduced solar forcing.
We present a multi-domain computational model for symbolic reasoning that was designed with the aim of matching human performance. The computational model is able to reason by deduction, induction, and abduction. It begins with an arbitrary theory in a given domain and gradually extends this theory as new regularities are learned from positive and negative examples. At the core of the computational model is a cognitive model with bounded cognitive resources. The combinatorial explosion problem, which frequently arises in inductive learning, is tackled by searching for solutions inside this cognitive model only. By way of example, we show that the computational model can learn elements of two different domains, namely arithmetic and English grammar.
In this paper we review, and elaborate on, the literature on a regression artifact related to Lord's paradox in a continuous setting. Specifically, the question is whether a continuous property of individuals predicts improvement from training between a pretest and a posttest. If the pretest score is included as a covariate, regression to the mean will lead to biased results if two critical conditions are satisfied: (1) the property is correlated with pretest scores and (2) pretest scores include random errors. We discuss how these conditions apply to the analysis in a published experimental study, the authors of which concluded that linearity of children's estimations of numerical magnitudes predicts arithmetic learning from a training program. However, the two critical conditions were clearly met in that study. In a reanalysis we find that the bias in the method can fully account for the effect found in the original study. In other words, data are consistent with the null hypothesis that numerical magnitude estimations are unrelated to arithmetic learning.
The so-called Deffuant model describes a pattern for social interaction, in which two neighboring individuals randomly meet and share their opinions on a certain topic, if their discrepancy is not beyond a given threshold R. The major focus of the analyses, both theoretical and based on simulations, lies on whether these single interactions lead to a global consensus in the long run or not. First, we generalize a result of Lanchier for the Deffuant model on Z, determining the critical value for R at which a phase transition of the long term behaviour takes place, to other distributions of the initial opinions than uniform on [0; 1]. Then we shed light on the situations where the underlying line graph Z is replaced by higherdimensional lattices Zd; d \ge 2, or the infinite cluster of supercritical i.i.d. bond percolation on the latter.
Science can be described as a systematic attempt to extract reliable information about the world. The cognitive capacities of homo sapiens come with various biases, such as our tendencies (a) to detect patterns in what is actually just noise, and (b) to be overly confident in our conclusions. Thus, the scientific method needs to involve safeguards against drawing incorrect conclusions due to such biases. A crucial part of the necessary toolbox is the theory of statistical inference.
There exists a large and well-developed (but of course incomplete) body of such theory, which, however, researchers across practically all of the empirical sciences do not have sufficient access to. The lack of statistical knowledge therefore forms a serious bottleneck in the quest for reliable scientific advances. As has been observed by several authors in recent years, statistical malpractice is widespread across a broad spectrum of disciplines, including (but not limited to) medicine, cognitive sciences, Earth sciences and social sciences.
Here I will first try to describe the overall situation and provide some concrete examples, and then move on to discuss the more difficult issue of what can and needs to be done.
Flip a coin repeatedly, and stop whenever you want. Your payoff is the proportion of heads, and you wish to maximize this payoff in expectation. This so-called Chow-Robbins game is amenable to computer analysis, but while simple-minded number crunching can show that it is best to continue in a given position, establishing rigorously that stopping is optimal seems at first sight to require "backward induction from infinity". We establish a simple upper bound on the expected payoff in a given position, allowing efficient and rigorous computer analysis of positions early in the game. In particular we confirm that with 5 heads and 3 tails, stopping is optimal.
We provide nonunimodular counterexamples to two properties that are well-known for automorphism invariant percolation on unimodular transitive graphs. The first property is that the number of encounter points in an infinite cluster is a.s. $0$ or $\infty$. The second property is that speed of random walk on an infinite cluster is a.s. well-defined.
We present the transparent neural networks, a graph-based computational model that was designed with the aim of facilitating human understanding. We also give an algorithm for developing such networks automatically by interacting with the environment. This is done by adding and removing structures for spatial and temporal memory. Thus we automatically obtain a monolithic computational model which integrates concept formation with deductive, inductive and abductive reasoning.
Place a water glass at each integer point, the one at the origin being full and all others empty, and consider averaging procedures where we repeatedly pick a pair of adjacent glasses and pool their contents, leaving the two glasses with equal amounts but with the total amount unchanged. Some simple results are derived for what kinds of configurations of water levels are obtainable via such procedures. These are applied in the analysis of the so-called Deffuant model for social interaction, where individuals have opinions represented by numbers between $0$ and $1$, and whenever two individuals interact they take a step towards equalizing their opinion, unless their opinions differ beyond a fixed amount $\theta$ in which case they make no adjustment. In particular, we reprove and sharpen the recent result of Lanchier which identifies the critical value $\theta_c$ for consensus formation in the Deffuant model on $\Z$ to be $\frac{1}{2}$.
Let each point of a homogeneous Poisson process in R^d independently be equipped with a random number of stubs (half-edges) according to a given probability distribution mu on the positive integers. We consider translation-invariant schemes for perfectly matching the stubs to obtain a simple graph with degree distribution mu. Leaving aside degenerate cases, we prove that for any mu there exist schemes that give only finite components as well as schemes that give infinite components. For a particular matching scheme that is a natural extension of Gale-Shapley stable marriage, we give sufficient conditions on mu for the absence and presence of infinite components.
For biased random walk on the infinite cluster in supercritical i.i.d.\ percolation on $\Z^2$, where the bias of the walk is quantified by a parameter $\beta$ greater than $1$, it has been conjectured (and partly proved) that there exists a critical value $\beta_c$ greater than $1$ such that the walk has positive speed when $\beta$ is less than $\beta_c$ and speed zero when $\beta$ is greater than $\beta_c$. In this paper, biased random walk on the infinite cluster of a certain translation invariant percolation process on $\Z^2$ is considered. The example is shown to exhibit the opposite behavior to what is expected for i.i.d.persolation, in the sense that it has a critical value $\beta_c$ such that, for $\beta$ less than $\beta_c$, the random walk has speed zero, while, for $\beta$ greater than $\beta_c$, the speed is positive. Hence the monotonicity in $\beta$ that is part of the conjecture for i.i.d.\ percolation cannot be extended to general translation invariant percolation processes.
Conditioning i.i.d.\ bond percolation with retention parameter $p$ on a one-dimensional periodic lattice on the event of having a bi-infinite path from $-\infty$ to $\infty$ is shown to make sense, and the resulting model exhibits a Markovian structure that facilitates its analysis. Stochastic monotonicity in $p$ turns out to fail in general for this model, but a weaker monotonicity property does hold: the average edge density is increasing in $p$.
We consider random walk with a nonzero bias to the right, on the infinite cluster in the following percolation model: take i.i.d.\ bond percolation with retention parameter $p$ on the so-called infinite ladder, and condition on the event of having a bi-infinite path from $-\infty$ to $\infty$. The random walk is shown to be transient, and to have an asymptotic speed to the right which strictly positive or zero depending on whether the bias is below or above a certain critical value which we compute explicitly.
Some examples of translation invariant site percolation processes on the $\Z^2$ lattice are constructed, the most far-reaching example being one that satisfies uniform finite energy (meaning that the probability that a site is open given the status of all others is bounded away from $0$ and $1$) and exhibits a.s. the coexistence of an infinite open cluster and an infinite closed cluster.
For an order statistic $(X_{1:n}, \ldots, X_{n:n})$ of a collection of independent but not necessarily identically distributed random variables, and any $i \in \{1, \ldots, n\}$, the conditional distribution of $(X_{i+1:n}, \ldots, X_{n:n})$ given $X_{i:n}>s$ is shown to be stochastically increasing in $s$. This answers a question of Hu and Xie.
The critical value for Bernoulli percolation on the $\Z^d$ lattice in any dimension $d$ is shown to be a computable number in the sense of the Church--Turing thesis.
The two-type Richardson model describes the growth of two competing infections on $\mathbb{Z}^d$ and the main question is whether both infection types can simultaneously grow to occupy infinite parts of $\mathbb{Z}^d$. For bounded initial configurations, this has been thoroughly studied. In this paper, an unbounded initial configuration consisting of points $x=(x_1,\ldots,x_d)$ in the hyperplane $\mathcal{H}=\{x\in\mathbb{Z}^d: x_1=0\}$ are considered. It is shown that, starting from a configuration where all points in $\mathcal{H}\backslash\{\0\}$ are type 1 infected and the origin $\0$ is type 2 infected, there is a positive probability for the type 2 infection to grow unboundedly if and only if it has a strictly larger intensity than the type 1 infection. If instead the initial type 1 infection is restricted to the negative $x_1$-axis, it is shown that the type 2 infection at the origin can grow unboundedly also when the infection types have the same intensity.
We discuss the volume fraction of a model of non-overlapping convex grains. It is obtained from thinning a Poisson process where each point has a weight and is the centre of a grain, by removing any grain that is overlapped by one of larger or equal weight. In the limit as the intensity of the Poisson process tends to infinity, the model can be identified with the intact grains in the dead leaves model if the weights are independent of the grain sizes. In this case we can show that the volume fraction is at most $1/2^d$ for $d=1$ or $2$ if the shape is fixed, but the size and the orientation are random. The upper bound is achieved for centrally symmetric sets of the same size and orientation. For general $d$ we can show the upper bound, $1/2^d$, for spherical grains with two-point radius distribution. If dependence between weight and size is allowed, it is possible to achieve a volume fraction arbitrarily close to one.
Another look is taken at the model assumptions involved in William Dembski's (2002) use of the NFL theorems from optimization theory to disprove the Darwinian theory of evolution by natural selection, and his argument is shown to lack any relevance whatsoever to evolutionary biology.
I have two versions of this paper:
Shortly upon publication of the latter version, a manuscript entitled "Active information in evolutionary search" by William Dembski and Robert Marks (available via Dembski's homepage) appeared on the web, with a response to my argument. This triggered me to elaborate my point a bit further:
Consider the one-dimensional contact process. About ten years ago, N. Konno stated the conjecture that, for all positive integres $n,m$, the upper invariant measure has the following property: Conditioned on the event that $O$ is infacted, the events {All sites $-n, ... , -1$ are healthy} and {All sites $1, ..., m$ are healthy} are negatively correlated. We prove (a stronger version of) this conjecture, and explain that in some sense it is a dual version of the planar case of one of our results in [2].
In the two-type Richardson model on a graph $\cG=(\cV,\cE)$, each vertex is at a given time in state $0$, $1$ or $2$. A $0$ flips to a $1$ (resp.\ $2$) at rate $\lambda_1$ ($\lambda_2$) times the number of neighboring $1$'s ($2$'s), while $1$'s and $2$'s never flip. When $\cG$ is infinite, the main question is whether, starting from a single $1$ and a single $2$, with positive probability we will see both types of infection reach infinitely many sites. This has previously been studied on the $d$-dimensional cubic lattice $\Z^d$, $d\geq 2$, where the conjecture (on which a good deal of progress has been made) is that such coexistence has positive probability if and only if $\lambda_1=\lambda_2$. In the present paper examples are given of other graphs where the set of points in the parameter space which admit such coexistence has a more surprising form. In particular, there exist graphs exhibiting coexistence at some value of $\frac{\lambda_1}{\lambda_2} \neq 1$ and non-coexistence when this ratio is brought closer to $1$.
In a recent paper by two of the authors, the concepts of upwards and downwards $\epsilon$-movability were introduced, mainly as a technical tool for studying dynamical percolation of interacting particle systems. In this paper, we further explore these concepts which can be seen as refinements or quantifications of stochastic domination, and we relate them to previously studied concepts such as uniform insertion tolerance and extractability.
Consider ordinary bond percolation on a finite or countably infinite graph. Let $s$, $t$, $a$ and $b$ be vertices. An earlier paper (van den Berg and Kahn, 2001) proved the (nonintuitive) result that, conditioned on the event that there is no open path from $s$ to $t$, the two events ``there is an open path from $x$ to $a$'' and ``there is an open path from $s$ to $b$'' are positively correlated. In the present paper we further investigate and generalize the theorem of which this result was a consequence. This leads to a result saying, informally, that, with the above conditioning, the open cluster of $s$ is conditionally positively (self-) associated and that it is conditionally negatively correlated with the open cluster of $t$. We also present analogues of some of our results for (a) random-cluster measures, and (b) directed percolation and contact processes, and observe that the latter lead to improvements of some results in a paper by Belitsky, Ferrari, Konno and Liggett (1997).
Consider an election between two candidates in which the voters' choices are random and independent and the probability of a voter choosing the first candidate is $p>1/2$. Condorcet's Jury Theorem which he derived from the weak law of large numbers asserts that if the number of voters tends to infinity then the probability that the first candidate will be elected tends to one. The notion of influence of a voter or its voting power is relevant for extensions of the weak law of large numbers for voting rules which are more general than simple majority. In this paper we point out two different ways to extend the classical notions of voting power and influences to arbitrary probability distributions. The extension relevant to us is the ``effect'' of a voter, which is a weighted version of the correlation between the voter's vote and the election's outcomes. We prove an extension of the weak law of large numbers to weighted majority games when all individual effects are small and show that this result does not apply to any voting rule which is not based on weighted majority.
See also this addendum, Probab. Th. Relat. Fields 135 (2006), p 470.
Let $X_0, X_1, \ldots$ be a geometrically ergodic Markov chain with state space $\cX$ and stationary distribution $\pi$. It is known that if $h: \cX \rightarrow \R$ satisfies $\pi(|h|^{2 + \eps})< \infty$ for some $\eps >0$, then the normalized sums of the $h(X_i)$'s obey a central limit theorem. Here we show, by means of a counterexample, that the condition $\pi(|h|^{2 + \eps})< \infty$ cannot be weakened to only assuming a finite second moment, i.e., $\pi(h^2)< \infty$.
We consider a stochastic model, describing the growth of two competing infections on $\mathbb{R}^d$. The growth takes place by way of spherical outbursts in the infected region, an outburst in the type 1 (2) infected region causing all previously uninfected points within a stochastic distance from the outburst location to be type 1 (2) infected. The main result is that, if the infection types have the same intensity, then there is a strictly positive probability that both infection types grow unboundedly.
We study Gibbs properties of the fuzzy Potts model in the mean field case (i.e.\ on a complete graph) and on trees. For the mean field case, a complete characterization of the set of temperatures for which non-Gibbsianness happens is given. The results for trees are somewhat less explicit, but we do show for general trees that non-Gibbsianness of the fuzzy Potts model happens exactly for those temperatures where the underlying Potts model has multiple Gibbs measures.
The two-type Richardson model describes the growth of two competing infections on $\mathbb{Z}^d$. At time 0 two disjoint finite sets $\xi_1,\xi_2\subset \mathbb{Z}^d$ are infected with type 1 and type 2 infection respectively. An uninfected site then becomes type 1 (2) infected at a rate proportional to the number of type 1 (2) infected nearest neighbors and once infected it remains so forever. The main result in this paper is, loosely speaking, that the choice of the initial sets $\xi_1$ and $\xi_2$ is irrelevant in deciding whether the event of mutual unbounded growth for the two infection types has positive probability or not.
A stochastic model, describing the growth of two competing infections on R^d, is introduced. The growth is driven by outbursts in the infected region, an outburst in the type 1 (2) infected region transmitting the type 1 (2) infection to the previously infected ball with stochastic radius around the outburst point. The main result is that with the growth rate for one of the infection types fixed, mutual unbounded growth has probability zero for all but at most countably many values of the other infection rate. This is a continuum analogue of a result of HÃ¤ggstrÃ¶m and Pemantle. We also extend a shape theorem of Deijfen for the corresponding model with just one type of infection.
The main prupose of this note is to make the discussion and results in the paper Sannolikhetsteori på tvåvåningsgrafer (see below) available in English. We discuss various stochastic models (random walk, percolation, the Ising and random-cluster models) on so-called bunkbed graphs, i.e., on any graph that is obtained as a Cartesian product of the complete graphs on two vertices and another graph. A new correlation inequality for the Ising model on bunkbed graphs is presented.
We prove uniqueness of the infinite rigid component for standard bond percolation on periodic lattices in $d$-dimensional Euclidean space for arbitrary $d$, and more generally when the lattice is a quasi-transitive and amenable graph. Our approach to uniqueness of the infinite rigid component improves earlier ones, that were confined to planar settings.
We discuss various stochastic models (random walk, percolation, Ising model) on graphs that are obtained as Cartesian products of another graph and $K_2$. In particular, a new correlation inequality for the Ising model on such graphs is obtained. (In Swedish.)
The fuzzy Potts model is obtained by looking at the Potts model with a pair of glasses that prevents distinguishing between some of the spin values. We show that the fuzzy Potts model on $\Z^d$ ($d\geq 2$) is Gibbsian at high temperatures and non-Gibbsian at low temperatures.
We consider Glauber dynamics at zero temperature for the ferromagnetic Ising model on the usual random graph model on $N$ vertices, with on average $\gamma$ edges incident to each vertex, in the limit as $N\rightarrow \infty$. Based on numerical simulations, Svenson \cite{S} reported that the dynamics fails to reach a global energy minimum for a range of values of $\gamma$. The present paper provides a mathematically rigorous proof that this failure to find the global minimum in fact happens for {\em all} $\gamma>0$. A lower bound on the residual energy is also given.
For each $d\geq 2$, we give examples of $d$-dimensional periodic lattices on which the hard-core and Widom--Rowlinson models exhibit a phase transition which is monotonic, in the sense that there exists a critical value $\lambda_c$ for the activity parameter $\lambda$, such that there is a unique Gibbs measure (resp.\ multiple Gibbs measures) whenever $\lambda$ is less than $\lambda_c$ (resp. $\lambda$ greater than $\lambda_c$). This contrasts with earlier examples of such lattices, where the phase transition failed to be monotonic. The case of the cubic lattice $\Z^d$ remains an open problem.
Consider a sequence of i.i.d.\ random variables, where each variable is refreshed (i.e., replaced by an independent variable with the same law) independently, according to a Poisson clock. At any fixed time $t$, the resulting sequence has the same law as at time $0$, but there can be exceptional random times at which certain almost sure properties of the time $0$ sequence are violated. We prove that there are no such exceptional times for the law of large numbers and the law of the iterated logarithm, so these laws are {\em dynamically stable}. However, there are times at which run lengths are exceptionally long, i.e., run tests are {\em dynamically sensitive}. We obtain a multifractal analysis of exceptional times for run lengths and for prediction. In particular, starting from an i.i.d.\ sequence of unbiased random bits, the random set of times $t$ where $\alpha \log_2(n)$ bits among the first $n$ bits can be predicted from their predecessors, has Hausdorff dimension $1-\alpha$ a.s. Finally, we consider simple random walk in the lattice $\Z^d$, and prove that transience is dynamically stable for $d \ge 5$, and dynamically sensitive for $d=3,4$. Moreover, for $d=3,4$, the nonempty random set of exceptional times $t$ where the walk is recurrent, has Hausdorff dimension $(4-d)/2$ a.s.
The random-cluster model is a dependent percolation model that has applications in the study of Ising and Potts models. In this paper, several new results are obtained for the random-cluster model on nonamenable graphs with cluster parameter $q\geq 1$. Among these, the main ones are the absence of percolation for the free random-cluster measure at the critical value, and examples of planar regular graphs with regular dual where $\pc^\f (q) > \pu^\w (q)$ for $q$ large enough. The latter follows from considerations of isoperimetric constants, and we give the first nontrivial explicit calculations of such constants. Such considerations are also used to prove non-robust phase transition for the Potts model on nonamenable regular graphs.
An explicit coupling construction of random-cluster measures is presented. As one of the applications of the construction, the Potts model on amenable Cayley graphs is shown to exhibit at every temperature the mixing property known as Bernoullicity.
We construct a coupling of two distinct Gibbs measures for Markov random fields with the same specifications, such that the existence of an infinite path of disagreements between the two configurations has probability $0$. This shows that the independence assumption in the disagreement percolation method for proving Gibbsian uniqueness, cannot be dropped without being replaced by other conditions. A similar counterexample is given for couplings of Markov chains.
For bond percolation on the two-dimensional triangular lattice with arbitrary retention parameter $p\in [0,1]$, we show that the number of infinite rigid components is a.s.\ at most one. This proves a conjecture by Holroyd. Further results, concerning simultaneous uniqueness, and continuity (in $p$) of the probability that a given edge is in an infinite rigid component, are also obtained.
We prove uniqueness of the infinite entangled component for bond percolation on the three-dimensional cubic lattice above the entanglement critical probability. This improves earlier results by Grimmett and Holroyd.
Some results concerning infinite clusters in automorphism invariant percolation on a regular tree, are recalled from a 1997 paper by the same author. New simple proofs, using the mass-transport method, are presented.
Consider i.i.d. percolation with retention parameter $p$ on an infinite graph $G$. There is a well known critical parameter $p_c \in [0,1]$ for the existence of infinite open clusters. Recently, it has been shown that when $G$ is quasi-transitive, there is another critical value $p_u \in [p_c,1]$ such that the number of infinite clusters is a.s. $\infty$ for $p\in(p_c,p_u)$, and there is a unique infinite cluster for $p>p_u$. We prove a simultaneous version of this result in the canonical coupling of the percolation processes for all $p\in[0,1]$; in particular, a.s. simultaneous uniqueness holds for all $p>p_u$. Simultaneously for all $p\in(p_c, p_u)$, we also prove that each infinite cluster has uncountably many ends. For $p > p_c$ we prove that all infinite clusters are robustly indistinguishable. Under the additional assumption that $G$ is unimodular, we prove that a.s. for all $p_1$ less than $p_2$ in $(p_c,p_u)$, every infinite cluster at level $p_2$ contains infinitely many infinite clusters at level $p_1$. We also show that any product $G$ of $d$ infinite connected graphs of bounded degree satisfies $p_u(G) \leq p_c(\Z^d)$.