Rate of Escape of Random Walks on Regular Languages and Free Products by Amalgamation of Finite Groups

Abstract : We consider random walks on the set of all words over a finite alphabet such that in each step only the last two letters of the current word may be modified and only one letter may be adjoined or deleted. We assume that the transition probabilities depend only on the last two letters of the current word. Furthermore, we consider also the special case of random walks on free products by amalgamation of finite groups which arise in a natural way from random walks on the single factors. The aim of this paper is to compute several equivalent formulas for the rate of escape with respect to natural length functions for these random walks using different techniques.
Type de document :
Communication dans un congrès
Roesler, Uwe. Fifth Colloquium on Mathematics and Computer Science, 2008, Kiel, Germany. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AI, Fifth Colloquium on Mathematics and Computer Science, pp.405-420, 2008, DMTCS Proceedings
Liste complète des métadonnées

Littérature citée [25 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01194658
Contributeur : Coordination Episciences Iam <>
Soumis le : lundi 7 septembre 2015 - 12:50:41
Dernière modification le : mercredi 10 mai 2017 - 17:41:16
Document(s) archivé(s) le : mardi 8 décembre 2015 - 12:46:56

Fichier

dmAI0127.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : hal-01194658, version 1

Collections

Citation

Lorenz A. Gilch. Rate of Escape of Random Walks on Regular Languages and Free Products by Amalgamation of Finite Groups. Roesler, Uwe. Fifth Colloquium on Mathematics and Computer Science, 2008, Kiel, Germany. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AI, Fifth Colloquium on Mathematics and Computer Science, pp.405-420, 2008, DMTCS Proceedings. 〈hal-01194658〉

Partager

Métriques

Consultations de la notice

56

Téléchargements de fichiers

161