**Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?**

Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.

Publication# The probability of intransitivity in dice and close elections

Résumé

We study the phenomenon of intransitivity in models of dice and voting. First, we follow a recent thread of research for n-sided dice with pairwise ordering induced by the probability, relative to 1/2, that a throw from one die is higher than the other. We build on a recent result of Polymath showing that three dice with i.i.d. faces drawn from the uniform distribution on {1,…,n} and conditioned on the average of faces equal to (n+1)/2 are intransitive with asymptotic probability 1/4. We show that if dice faces are drawn from a non-uniform continuous mean zero distribution conditioned on the average of faces equal to 0, then three dice are transitive with high probability. We also extend our results to stationary Gaussian dice, whose faces, for example, can be the fractional Brownian increments with Hurst index H∈(0,1). Second, we pose an analogous model in the context of Condorcet voting. We consider n voters who rank k alternatives independently and uniformly at random. The winner between each two alternatives is decided by a majority vote based on the preferences. We show that in this model, if all pairwise elections are close to tied, then the asymptotic probability of obtaining any tournament on the k alternatives is equal to 2−k(k−1)/2, which markedly differs from known results in the model without conditioning. We also explore the Condorcet voting model where methods other than simple majority are used for pairwise elections. We investigate some natural definitions of “close to tied” for general functions and exhibit an example where the distribution over tournaments is not uniform under those definitions.

Official source

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Concepts associés

Chargement

Publications associées

Chargement

Publications associées (8)

Chargement

Chargement

Chargement

Concepts associés (19)

Probabilité

vignette|Quatre dés à six faces de quatre couleurs différentes. Les six faces possibles sont visibles.
Le terme probabilité possède plusieurs sens : venu historiquement du latin probabilitas, il désig

Définition

Une définition est une proposition qui met en équivalence un élément définissant et un élément étant défini.
Une définition a pour but de clarifier, d'expliquer. Elle détermine les limites ou « un

Dé

vignette|redresse=1|Deux dés à jouer ordinaires.
vignette|redresse=1|Dé à japonais, présentant un trou plus grand que les autres et peint en rouge pour la face .
Un dé est un objet, généralement de

Olfactometer experiments are used to determine the effect of odours on the behaviour of organisms such as insects or nematodes, and typically result in data comprising many groups of small counts, overdispersed relative to the multinomial distribution. Overdispersion reflects a lack of independence or heterogeneity among individuals and can lead to statistics having larger variances than expected and possible losses of efficiency. In this thesis, some distributions which consist of generalisations of the multinomial distribution have been developed. These models are based on non-homogeneous Markov chain theory, take the overdispersion into account, and potentially provide a physical interpretation of the overdispersion seen in olfactometer data. Some inference aspects are considered, including comparison of the asymptotic relative efficiencies of three different sampling schemes. The fact that the empirical distributions well approximate the corresponding asymptotic distributions is checked. Observable differences in parameter estimates between data generated under different hypotheses are also studied. Finally, different models intended to shed light on various aspects of the data and/or the experiment procedure, are applied to three real olfactometer datasets.

3-D geological models are built with data collected in the field such as boreholes, geophysical measurements, pilot shafts or geological mapping. Unfortunately, these data are always limited in number. It implies that geological information is sparse and subsurface models are thus always built of both subjective interpretation and mathematical interpolation/extrapolation techniques. These models are therefore uncertain and this uncertainty is rarely pointed out in a geological prognosis. Our study proposes to bring a new methodology for the evaluation of geological uncertainties related to 3-D subsurface models and to test its potential use. The methodology we propose is based on the 3-D subsurface model, which is here considered as the most probable prediction (notion of best guess). The various geological interfaces that compose the subsurface model are handled individually as Gaussian random fields. At each location of an interface, the random function Z(u) describing the position of this interface is composed of a deterministic part m(u) which represents the expected position, and a random part σ(u)ε(u) which describes fluctuations around the predicted position. Then, a model of spatial variability (a variogram function γ(h)) is proposed in order to condition the random field according to available observations. Several structural constraints, such as the shape of folds and the thickness of layers can also be accounted for in this model. At this point, we are able to estimate the local variance all over the study area by the application of the kriging technique. Finally, the variability is converted into three-dimensional information by calculating probabilities, this describes the occurrence of the various rock masses that are present in the study area. The probabilities are calculated according to intersection rules that govern the stratigraphic sequence of the subsurface model, and they allow us to build a probabilistic model of subsurface structures in the form of a three-dimensional probability field. All of this has been incorporated in a computer program.

This work is a study of three interacting particle systems that are modified versions of the contact process. The contact process is a spin system defined on a graph and is commonly taken as a model for the spread of an infection in a population; transmission of the infection happens by proximity (contact). The first two models we consider – the grass-bushes-trees model and the multitype contact process – are models for competition between species in Ecology. The third model – annealed approximation to boolean networks – approximately describes the transmission of information among genes in a cell. We consider the grass-bushes-trees model on the set of integers, ℤ. Each point of ℤ is a region of space. In the continuous-time dynamics, at each instant each region can be either empty (state 0) or occupied by an individual of one of two existing species (states 1 and 2). Occupants of both species die at rate 1, leaving their regions empty, and send descendents to neighboring regions at rate λ. An individuals of type 1 may be born on a region previously occupied by an individual of type 2, but the converse is forbidden. We take the "heaviside" initial configuration in which all sites to the left of the origin are occupied by type 1 individuals and all sites to the right of the origin are occupied by type 2 individuals. If the birth of new individuals is allowed to occur at sites that are not adjacent to the parent, and if the rate λ is supercritical for the usual contact process on ℤ, we see the formation of an interface region in which both types coexist. Addressing a conjecture of Cox and Durrett (1995), we prove that the size of this region is stochastically tight. The multitype contact process on ℤ is a process identical to the grass-bushes-trees model in every respect except that no births can occur at previously occupied sites; in particular, the model is symmetric for both species. We again start the process from the heaviside configuration and prove that the size of the interface region is tight. In addition, we prove that the position of the interface, when properly rescaled, converges to Brownian motion. Finally, we give necessary and sufficient conditions on the initial configuration so that one of the two species becomes extinct with probability one and also so that both species are present at all times with positive probability. Lastly, we consider a model proposed by Derrida and Pomeau (1986) and recently studied by Chatterjee and Durrett (2009); it is defined as an approximation to S. Kauffman's boolean networks (1969). The model starts with the choice of a random directed graph on n vertices; each node has r input nodes pointing at it. A discrete time threshold contact process is then considered on this graph: at each instant, each site has probability q of choosing to receive input; if it does, and if at least one of its inputs were occupied by a 1 at the previous instant, then it is labeled with a 1; in all other cases, it is labeled with a 0. r and q are kept fixed and n is taken to infinity. Improving a result of Chatterjee and Durrett, we show that if qr > 1, then the time of persistence of the dynamics is exponential in n.