• View
• Edit
• History
• Print

Lecture

Des articles autour des probabilités sur les structures discrètes (pas forcément que) qu'on pourrait se présenter les uns aux autres ? Mardi matin par ex ?

1. Fang Chen, Laslo Lovasz and Igor Pak, Lifting Markov Chains to Speed up Mixing, Proc. STOC'99 (proposé par thomas)
   • Résumé : Le Lifting d'une Markov chain est une technique consistant à séparer chaque état en plusieurs états, et ça peut parfois diminuer le temps de mélange (racine carrée) et simplifier l'étude de la chaîne. Ce papier utilise les "multiflots" (dont Alexandra est maintenant experte) pour montrer un résultat général et un exemple.
2. Olle Haggstrom, Propp–Wilson with read-once randomness, chap. 12 du livre Finite Markov Chains and Algorithmic Applications (proposé par thomas)
   • Résumé : Le couplage arrière c'est bien, mais il faut garder en mémoire les bits aléatoires (sauf à tricher en utilisant le germe du générateur aléatoire). Mais on peut faire du couplage avant en étant malin !
3. Cyril Nicaud. A Probabilistic Analysis of the Reduction Ratio in the Suffix-Array IS-Algorithm (proposé par Julien)
   • Résumé : Une étude asymptotique des facteurs LMS de mots aléatoires sous différentes distributions (uniforme, source sans mémoire et markovienne). Cette étude permet d'étudier le comportement moyen de l'algorithme IS, un des plus efficace pour calculer la table des suffixes d'un mot.
4. Eric Rémila Tiling a Polygon with Two Kinds of Rectangles (proposé par Alexandra)
   • Résumé : Etend les résultats de Thurston sur les pavages par dominos au cas de pavages par deux rectangles : fonction de hauteur, flip, connexité, algorithme pour paver.
5. Ravi Kannan et Santosh Vempala : Sampling Lattice Points (proposé par Thierry)
   • Résumé : si un polytope est suffisamment gras, le nombre de points entiers est à peu près son volume et on peut échantillonner les points entiers. Les énoncés sont mal quantifiés donc faudra gratter pour comprendre leur vrai sens (par exemple leurs énoncés sont du genre "pour tout Polytope tel calcul est en temps polynomial", oui, ben moi pour tout polytope je te le fais en temps constant).
6. Mark Huber, A bounding chain for Swendsen-Wang (proposé par thomas)
   • Résumé : The greatest drawback of Monte Carlo Markov chain methods is lack of knowledge of the mixing time of the chain. The use of bounding chains solves this difficulty for some chains by giving theoretical and experimental upper bounds on the mixing time. Moreover, when used with methodologies such as coupling from the past, bounding chains allow the user to take samples drawn exactly from the stationary distribution without knowledge of the mixing time. Here we present a bounding chain for the Swendsen-Wang process. The Swendsen-Wang bounding chain allow us to efficiently obtain exact samples from the ferromagnetic Q-state Potts model for certain classes of graphs. Also, by analyzing this bounding chain, we will show that Swendsen-Wang is rapidly mixing over a slightly larger range of parameters than was known previously.
7. Basile de Loynes ''Random walks on graphs induced by aperiodic tilings
   • Résumé : In this paper, simple random walks on a class of graphs induced by quasi-periodic tilings of the Euclidean space R^d are investigated. Roughly speaking, these graphs are obtained by considering a d-dimensional slice of the Cayley graph of Z^N. The quasi-periodicity of the underlying tilings implies that these graphs are not space homogeneous (roughly speaking, there is no transitive group action). In this context, we prove that the asymptotic entropy of the simple random walk is zero and characterize the type (recurrent or transient) of the simple random walk. These results are similar to the classical context of random walks on the integer lattice. In this sense, it suggests that a varying local curvature does not modify the global behavior of the simple random walk as long as the graph remains roughly globally flat.
8. Jarkko Kari et Michal Szabados, An Algebraic Geometric Approach to Nivat's Conjecture
   • Résumé : The Kari-Culik tilings are formed from a set of 13 Wang tiles that tile the plane only aperiodically. They are the smallest known set of Wang tiles to do so and are not as well understood as other examples of aperiodic Wang tiles. We show that the Z2 action by translation on a certain subset of the Kari-Culik tilings, namely those whose rows can be interpreted as Sturmian sequences (rotation sequences), is minimal. We give a characterization of this space as a skew product as well as explicit bounds on the waiting time between occurrences of m×n configurations.