Aggregation of markov chains: An analysis of deterministic annealing based methods

Research output: Contribution to journalConference article

Abstract

We develop a method for aggregating large Markov chains into smaller representative Markov chains, where Markov chains are viewed as weighted directed graphs, and similar nodes (and edges) are aggregated using a deterministic annealing approach. The notions of representativeness of the aggregated graphs and similarity between nodes in graphs are based on a newly proposed metric that quantifies connectivity in the underlying graph. Namely, we develop notions of distance between subchains in Markov chains, and provide easily verifiable conditions that determine if a given Markov chain is nearly decomposable, that is, conditions for which the deterministic annealing approach can be used to identify subchains with high probability. We show that the aggregated Markov chain preserves certain dynamics of the original chain. In particular we provide explicit bounds on the ℓ1 norm of the error between the aggregated stationary distribution of the original Markov chain and the stationary distribution of the aggregated Markov chain, which extends on longstanding foundational results (Simon and Ando, 1961).

Original languageEnglish (US)
Article number7040423
Pages (from-to)6591-6596
Number of pages6
JournalProceedings of the IEEE Conference on Decision and Control
Volume2015-February
Issue numberFebruary
DOIs
StatePublished - Jan 1 2014
Event2014 53rd IEEE Annual Conference on Decision and Control, CDC 2014 - Los Angeles, United States
Duration: Dec 15 2014Dec 17 2014

Fingerprint

Annealing
Markov processes
Markov chain
Aggregation
Agglomeration
Stationary Distribution
Graph in graph theory
Explicit Bounds
Directed graphs
Weighted Graph
Vertex of a graph
Decomposable
Directed Graph
Connectivity
Quantify
Norm
Metric

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Modeling and Simulation
  • Control and Optimization

Cite this

Aggregation of markov chains : An analysis of deterministic annealing based methods. / Xu, Yunwen; Beck, Carolyn L; Salapaka, Srinivasa M.

In: Proceedings of the IEEE Conference on Decision and Control, Vol. 2015-February, No. February, 7040423, 01.01.2014, p. 6591-6596.

Research output: Contribution to journalConference article

@article{2857812e6dd74378afcb2571408275e0,
title = "Aggregation of markov chains: An analysis of deterministic annealing based methods",
abstract = "We develop a method for aggregating large Markov chains into smaller representative Markov chains, where Markov chains are viewed as weighted directed graphs, and similar nodes (and edges) are aggregated using a deterministic annealing approach. The notions of representativeness of the aggregated graphs and similarity between nodes in graphs are based on a newly proposed metric that quantifies connectivity in the underlying graph. Namely, we develop notions of distance between subchains in Markov chains, and provide easily verifiable conditions that determine if a given Markov chain is nearly decomposable, that is, conditions for which the deterministic annealing approach can be used to identify subchains with high probability. We show that the aggregated Markov chain preserves certain dynamics of the original chain. In particular we provide explicit bounds on the ℓ1 norm of the error between the aggregated stationary distribution of the original Markov chain and the stationary distribution of the aggregated Markov chain, which extends on longstanding foundational results (Simon and Ando, 1961).",
author = "Yunwen Xu and Beck, {Carolyn L} and Salapaka, {Srinivasa M}",
year = "2014",
month = "1",
day = "1",
doi = "10.1109/CDC.2014.7040423",
language = "English (US)",
volume = "2015-February",
pages = "6591--6596",
journal = "Proceedings of the IEEE Conference on Decision and Control",
issn = "0191-2216",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
number = "February",

}

TY - JOUR

T1 - Aggregation of markov chains

T2 - An analysis of deterministic annealing based methods

AU - Xu, Yunwen

AU - Beck, Carolyn L

AU - Salapaka, Srinivasa M

PY - 2014/1/1

Y1 - 2014/1/1

N2 - We develop a method for aggregating large Markov chains into smaller representative Markov chains, where Markov chains are viewed as weighted directed graphs, and similar nodes (and edges) are aggregated using a deterministic annealing approach. The notions of representativeness of the aggregated graphs and similarity between nodes in graphs are based on a newly proposed metric that quantifies connectivity in the underlying graph. Namely, we develop notions of distance between subchains in Markov chains, and provide easily verifiable conditions that determine if a given Markov chain is nearly decomposable, that is, conditions for which the deterministic annealing approach can be used to identify subchains with high probability. We show that the aggregated Markov chain preserves certain dynamics of the original chain. In particular we provide explicit bounds on the ℓ1 norm of the error between the aggregated stationary distribution of the original Markov chain and the stationary distribution of the aggregated Markov chain, which extends on longstanding foundational results (Simon and Ando, 1961).

AB - We develop a method for aggregating large Markov chains into smaller representative Markov chains, where Markov chains are viewed as weighted directed graphs, and similar nodes (and edges) are aggregated using a deterministic annealing approach. The notions of representativeness of the aggregated graphs and similarity between nodes in graphs are based on a newly proposed metric that quantifies connectivity in the underlying graph. Namely, we develop notions of distance between subchains in Markov chains, and provide easily verifiable conditions that determine if a given Markov chain is nearly decomposable, that is, conditions for which the deterministic annealing approach can be used to identify subchains with high probability. We show that the aggregated Markov chain preserves certain dynamics of the original chain. In particular we provide explicit bounds on the ℓ1 norm of the error between the aggregated stationary distribution of the original Markov chain and the stationary distribution of the aggregated Markov chain, which extends on longstanding foundational results (Simon and Ando, 1961).

UR - http://www.scopus.com/inward/record.url?scp=84988214329&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84988214329&partnerID=8YFLogxK

U2 - 10.1109/CDC.2014.7040423

DO - 10.1109/CDC.2014.7040423

M3 - Conference article

AN - SCOPUS:84988214329

VL - 2015-February

SP - 6591

EP - 6596

JO - Proceedings of the IEEE Conference on Decision and Control

JF - Proceedings of the IEEE Conference on Decision and Control

SN - 0191-2216

IS - February

M1 - 7040423

ER -