# Optimal bounds for bit-sizes of stationary distributions in finite Markov chains

@article{Skomra2021OptimalBF, title={Optimal bounds for bit-sizes of stationary distributions in finite Markov chains}, author={Mateusz Skomra}, journal={ArXiv}, year={2021}, volume={abs/2109.04976} }

An irreducible stochastic matrix with rational entries has a stationary distribution given by a vector of rational numbers. We give an upper bound on the lowest common denominator of the entries of this vector. Bounds of this kind are used to study the complexity of algorithms for solving stochastic mean payoff games. They are usually derived using the Hadamard inequality, but this leads to suboptimal results. We replace the Hadamard inequality with the Markov chain tree formula in order to… Expand

#### References

SHOWING 1-10 OF 33 REFERENCES

On discounted approximations of undiscounted stochastic games and Markov decision processes with limited randomness

- Mathematics, Computer Science
- Oper. Res. Lett.
- 2013

Abstract It is shown that the discount factor needed to solve an undiscounted mean payoff stochastic game to optimality is exponentially close to 1, even in one-player games with a single random node… Expand

The Complexity of Mean Payoff Games on Graphs

- Computer Science, Mathematics
- Theor. Comput. Sci.
- 1995

A pseudo-polynomial-time algorithm for the solution of mean payoff games on graphs, a family of perfect information games introduced by Ehrenfeucht and Mycielski and considered by Gurvich, Karzanov and Khachiyan, is described. Expand

A Graph Theoretic Formula for the Steady State Distribution of Finite Markov Processes

- Mathematics
- 1975

This paper presents a formula which expresses the solution to the steady-state equations of a finite irreducible Markov process in terms of subgraphs of the transition diagram of the process. The… Expand

The Complexity of Solving Stochastic Games on Graphs

- Mathematics, Computer Science
- ISAAC
- 2009

A linear time algorithm is exhibited that given a simple stochastic game and the values of all positions of that game, computes a pair of optimal strategies. Expand

Ergodicity conditions for zero-sum games

- Mathematics
- 2014

A basic question for zero-sum repeated games consists in determining whether the mean payoff per time unit is independent of the initial state. In the special case of "zero-player" games, i.e., of… Expand

Simulated annealing algorithms and Markov chains with rare transitions

- Mathematics
- 1999

In these notes, written for a D.E.A. course at University Paris XI during the first term of 1995, we prove the essentials about stochastic optimisation algorithms based on Markov chains with rare… Expand

A Pseudo-Polynomial Algorithm for Mean Payoff Stochastic Games with Perfect Information and a Few Random Positions

- Computer Science, Mathematics
- ICALP
- 2013

It is shown that BWR-games with a constant number of random nodes can be solved in pseudo-polynomial time, that is, for any such game with a few random nodes |VR|=O(1), a saddle point in pure stationary strategies can be found in time polynomial in |VW|+|VB|. Expand

Tree formulas, mean first passage times and Kemeny’s constant of a Markov chain

- Mathematics
- Bernoulli
- 2018

In this paper, we aim to provide probabilistic and combinatorial insights into tree formulas for the Green function and hitting probabilities of Markov chains on a finite state space. These tree… Expand

Finding Optimal Strategies of Almost Acyclic Simple Stochastic Games

- Computer Science, Mathematics
- TAMC
- 2014

This work gives some fixed-parameter tractable or polynomial algorithms in terms of different parameters such as the number of cycles or the size of the minimal feedback vertex set for turned-based stochastic games with reachability objectives. Expand

Simple Stochastic Games, Parity Games, Mean Payoff Games and Discounted Payoff Games Are All LP-Type Problems

- Mathematics, Computer Science
- Algorithmica
- 2007

It is shown that a Simple Stochastic Game (SSG) can be formulated as an LP-type problem, and the first strongly subexponential solution for SSGs is obtained (a stronglySubexponential algorithm has only been known for binary SSGs [L]). Expand