Best Ergodic Averages via Optimal Graph Filters in Reversible Markov Chains
Fuente:
arXiv
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866912942845329408 |
|---|---|
| author | Saldi, Naci |
| author_facet | Saldi, Naci |
| contents | In this paper, we address the problem of finding the best ergodic or Birkhoff averages in the mean ergodic theorem to ensure rapid convergence to a desired value, using graph filters. Our approach begins by representing a function on the state space as a graph signal, where the (directed) graph is formed by the transition probabilities of a reversible Markov chain. We introduce a concept of graph variation, enabling the definition of the graph Fourier transform for graph signals on this directed graph. Viewing the iteration in the mean ergodic theorem as a graph filter, we recognize its non-optimality and propose three optimization problems aimed at determining optimal graph filters. These optimization problems yield the Bernstein, Chebyshev, and Legendre filters. Numerical testing reveals that while the Bernstein filter performs slightly better than the traditional ergodic average, the Chebyshev and Legendre filters significantly outperform the ergodic average, demonstrating rapid convergence to the desired value. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_18995 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Best Ergodic Averages via Optimal Graph Filters in Reversible Markov Chains Saldi, Naci Systems and Control Probability In this paper, we address the problem of finding the best ergodic or Birkhoff averages in the mean ergodic theorem to ensure rapid convergence to a desired value, using graph filters. Our approach begins by representing a function on the state space as a graph signal, where the (directed) graph is formed by the transition probabilities of a reversible Markov chain. We introduce a concept of graph variation, enabling the definition of the graph Fourier transform for graph signals on this directed graph. Viewing the iteration in the mean ergodic theorem as a graph filter, we recognize its non-optimality and propose three optimization problems aimed at determining optimal graph filters. These optimization problems yield the Bernstein, Chebyshev, and Legendre filters. Numerical testing reveals that while the Bernstein filter performs slightly better than the traditional ergodic average, the Chebyshev and Legendre filters significantly outperform the ergodic average, demonstrating rapid convergence to the desired value. |
| title | Best Ergodic Averages via Optimal Graph Filters in Reversible Markov Chains |
| topic | Systems and Control Probability |
| url | https://arxiv.org/abs/2405.18995 |