On the Entropy Rate of a Random Walk on t-Designs

Document Type : Original Scientific Paper


‎Department of Pure Mathematics, ‎Faculty of Mathematical Sciences, University of Kashan, Kashan‎, ‎I‎. ‎R‎. ‎Iran


In this paper, a random walk on  t-designs are considered. We assign a weight to each block and walk randomly on the vertices with a probability proportional to the weight of blocks. This stochastic process is a Markov chain. We obtain a stationary distribution for this process and compute its entropy rate. It is seen that, when the blocks have the same weight, the uniform distribution on the vertices is a stationary distribution and the entropy rate depends only on the number of vertices.


[1] T. Beth, D. Jungnickel and H. Lenz, Design Theory, Volume I, 2nd edition, Cambridge University Press, Cambridge, 1999.
[2] T. M. Cover and J. A. Thomas, Elements of Information Theory, 2nd edition, John Wiley & Sons, Inc., New Jersey, 2006.
[3] R. Li and W. Heidrich, Hierarchical and view-invariant light field segmentation by maximizing entropy rate on 4D ray graphs, ACM Trans. Graph. 38 (6) (2019) Article 167.
[4] J. H. van Lint and R. M. Wilson, A Course in Combinatorics, 2nd edition, Cambridge University Press, Cambridge, 2001.
[5] H. Ni and X. Niu, Agglomerative oversegmentation using dual similarity and enropy rate, Pattern Recogn. 93 (2019) 324-336.
[6] N. Privault, Understanding Markov Chains: Examples and Applications, 2nd edition, Springer, Singapore, 2018.
[7] S. M. Ross, Stochastic Processes, 2nd edition, John Wiley & Sons, Inc., New York, 1996.
[8] R. J. H. Ross, C. Strandkvist and W. Fontana, Compressibility of random walker trajectories on growing networks, Phys. Lett. A 383 (17) (2019) 2028−2032.