Deterministic and heuristic criteria for optimized Markov chain aggregation

Abstract This paper addresses Markov chain aggregation, a method that reduces state space complexity while preserving dynamical properties. We present a comprehensive framework to find optimal aggregations that balance minimizing the number of states with maintaining similarity to the original chain. We propose three interconnected algorithms: (1) an exhaustive algorithm that identifies optimal partitions, (2) a deterministic improvement that restricts the search space to partitions with $$n - 1$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>n</mml:mi> <mml:mo>-</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:math> elements, and (3) a heuristic algorithm that uses Mean First Passage Time (MFPT) to further reduce the partition search space. Our evaluation framework applies the Kullback–Leibler (KL) divergence rate as the primary metric to quantify similarity between original and reduced chains. We analyze the time complexity and show that our comprehensive BESTA algorithm operates at $$\mathcal {O}(N^3(1 + Z))$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:msup> <mml:mi>N</mml:mi> <mml:mn>3</mml:mn> </mml:msup> <mml:mrow> <mml:mo>(</mml:mo> <mml:mn>1</mml:mn> <mml:mo>+</mml:mo> <mml:mi>Z</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> , where the stopping condition determines Z . Our experiments show that this approach outperforms existing techniques, significantly reducing computation time and maintaining controlled error bounds by using a parameterized stopping criterion. This method performs particularly well with large-scale Markov chains, where traditional exhaustive methods become computationally infeasible.