Preordered semirings completed for better comparison of large powers
Asymptotic completions of preordered semirings
Information Theory
Summary
The paper studies mathematical structures called preordered semirings, which help compare how elements grow when raised to high powers. The authors introduce a way to complete these structures so that sequences behaving like powers, even if not exact powers, can be treated similarly to true power sequences. This completion helps extend known methods for comparing these elements to more general cases. They give examples in areas like tensors and graphs, and show a practical use in statistical hypothesis testing.
What this means in practice
- •For statistical data analysts: Determine precise error rates for hypothesis testing involving complex Markov models using the paper’s strong converse exponent result.
- •For graph algorithm developers: Use the completion of preordered semirings to analyze asymptotic behavior of graph operations beyond simple powers.
Authors
Péter Vrana
Abstract
The study of preordered semirings is motivated by applications in computer science, graph theory, and information theory, and provides tools for understanding the asymptotic preorder, which compares large powers of a pair of elements. This paper studies sequences which behave approximately as sequences of powers, but are not necessarily equivalent to geometric sequences. Our main result is that preordered semirings admit completions where such sequences, that we call approximately geometric, become equivalent to geometric sequences, and that existing characterizations of the asymptotic preorder extend to the completion. We provide several classes of examples of approximately geometric sequences in the semiring of tensors, and in the semiring of graphs. As a concrete application, we determine the strong converse exponent for binary hypothesis testing with composite Markov hypotheses.