Assigning Stationary Distributions to Sparse Stochastic Matrices
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929666585001984 |
|---|---|
| author | Gillis, Nicolas Van Dooren, Paul |
| author_facet | Gillis, Nicolas Van Dooren, Paul |
| contents | The target stationary distribution problem (TSDP) is the following: given an irreducible stochastic matrix $G$ and a target stationary distribution $\hat μ$, construct a minimum norm perturbation, $Δ$, such that $\hat G = G+Δ$ is also stochastic and has the prescribed target stationary distribution, $\hat μ$. In this paper, we revisit the TSDP under a constraint on the support of $Δ$, that is, on the set of non-zero entries of $Δ$. This is particularly meaningful in practice since one cannot typically modify all entries of $G$. We first show how to construct a feasible solution $\hat G$ that has essentially the same support as the matrix $G$. Then we show how to compute globally optimal and sparse solutions using the component-wise $\ell_1$ norm and linear optimization. We propose an efficient implementation that relies on a column-generation approach which allows us to solve sparse problems of size up to $10^5 \times 10^5$ in a few minutes. We illustrate the proposed algorithms with several numerical experiments. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2312_16011 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Assigning Stationary Distributions to Sparse Stochastic Matrices Gillis, Nicolas Van Dooren, Paul Numerical Analysis Optimization and Control Probability Computation The target stationary distribution problem (TSDP) is the following: given an irreducible stochastic matrix $G$ and a target stationary distribution $\hat μ$, construct a minimum norm perturbation, $Δ$, such that $\hat G = G+Δ$ is also stochastic and has the prescribed target stationary distribution, $\hat μ$. In this paper, we revisit the TSDP under a constraint on the support of $Δ$, that is, on the set of non-zero entries of $Δ$. This is particularly meaningful in practice since one cannot typically modify all entries of $G$. We first show how to construct a feasible solution $\hat G$ that has essentially the same support as the matrix $G$. Then we show how to compute globally optimal and sparse solutions using the component-wise $\ell_1$ norm and linear optimization. We propose an efficient implementation that relies on a column-generation approach which allows us to solve sparse problems of size up to $10^5 \times 10^5$ in a few minutes. We illustrate the proposed algorithms with several numerical experiments. |
| title | Assigning Stationary Distributions to Sparse Stochastic Matrices |
| topic | Numerical Analysis Optimization and Control Probability Computation |
| url | https://arxiv.org/abs/2312.16011 |