Asymptotic entropy of random walks on regular languages over a finite alphabet

被引：2
|
作者：
Gilch, Lorenz A. [1 ]
机构：
[1] Graz Univ Technol, A-8010 Graz, Austria
来源：
ELECTRONIC JOURNAL OF PROBABILITY | 2016年 / 21卷
关键词：
random walks; regular languages; entropy; analytic; CONTEXT-FREE PAIRS; HYPERBOLIC GROUPS; MARKOV-CHAINS; ANALYTICITY; ENDS;
D O I：
10.1214/16-EJP4180
中图分类号：
O21 [概率论与数理统计]; C8 [统计学];
学科分类号：
020208 ; 070103 ; 0714 ;
摘要：
We prove existence of asymptotic entropy of random walks on regular languages over a finite alphabet and we give formulas for it. Furthermore, we show that the entropy varies real-analytically in terms of probability measures of constant support, which describe the random walk. This setting applies, in particular, to random walks on virtually free groups.
引用
收藏
页数：42
相关论文
共 50 条
  • [1] Asymptotic Entropy of Random Walks on Free Products
    Gilch, Lorenz A.
    ELECTRONIC JOURNAL OF PROBABILITY, 2011, 16 : 73 - 102
  • [2] Sharp lower bounds for the asymptotic entropy of symmetric random walks
    Gouezel, Sebastien
    Matheus, Frederic
    Maucourant, Francois
    GROUPS GEOMETRY AND DYNAMICS, 2015, 9 (03) : 711 - 735
  • [3] Asymptotic entropy of the ranges of random walks on discrete groups
    Chen, Xinxing
    Xie, Jiansheng
    Zhao, Minzhi
    SCIENCE CHINA-MATHEMATICS, 2020, 63 (06) : 1153 - 1168
  • [4] Asymptotic entropy of the ranges of random walks on discrete groups
    Xinxing Chen
    Jiansheng Xie
    Minzhi Zhao
    Science China(Mathematics), 2020, 63 (06) : 1153 - 1168
  • [5] Asymptotic entropy of the ranges of random walks on discrete groups
    Xinxing Chen
    Jiansheng Xie
    Minzhi Zhao
    Science China Mathematics, 2020, 63 : 1153 - 1168
  • [6] DIFFERENTIATING THE ENTROPY OF RANDOM WALKS ON HYPERBOLIC GROUPS
    Mathieu, P.
    ANNALS OF PROBABILITY, 2015, 43 (01) : 166 - 187
  • [7] State complexity of permutation on finite languages over a binary alphabet
    Cho, Da-Jung
    Goc, Daniel
    Han, Yo-Sub
    Ko, Sang-Ki
    Palioudakis, Alexandros
    Salomaa, Kai
    THEORETICAL COMPUTER SCIENCE, 2017, 682 : 67 - 78
  • [8] On the entropy of regular languages
    Ceccherini-Silberstein, T
    Machi, A
    Scarabotti, F
    THEORETICAL COMPUTER SCIENCE, 2003, 307 (01) : 93 - 102
  • [9] Entropy of regular timed languages
    Asarin, Eugene
    Basset, Nicolas
    Degorre, Aldric
    INFORMATION AND COMPUTATION, 2015, 241 : 142 - 176
  • [10] MULTIPLE RANDOM WALKS IN RANDOM REGULAR GRAPHS
    Cooper, Colin
    Frieze, Alan
    Radzik, Tomasz
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2009, 23 (04) : 1738 - 1761
12345