Editing Markov chain (section)

===Information theory===
Markov chains are used throughout information processing. [[Claude Shannon]]'s famous 1948 paper ''[[A Mathematical Theory of Communication]]'', which in a single step created the field of [[information theory]], opens by introducing the concept of [[information entropy|entropy]] by modeling texts in a natural language (such as English) as generated by an ergodic Markov process, where each letter may depend statistically on previous letters.<ref>{{ Citation | last = Thomsen | first = Samuel W. | date = 2009 | title = Some evidence concerning the genesis of Shannon's information theory | journal = Studies in History and Philosophy of Science | volume = 40 | issue = 1 | pages = 81–91 | doi = 10.1016/j.shpsa.2008.12.011 | bibcode = 2009SHPSA..40...81T }}  </ref> Such idealized models can capture many of the statistical regularities of systems. Even without describing the full structure of the system perfectly, such signal models can make possible very effective [[data compression]] through [[entropy encoding]] techniques such as [[arithmetic coding]]. They also allow effective [[state estimation]] and [[pattern recognition]]. Markov chains also play an important role in [[reinforcement learning]].

Markov chains are also the basis for hidden Markov models, which are an important tool in such diverse fields as telephone networks (which use the [[Viterbi algorithm]] for error correction), speech recognition and [[bioinformatics]] (such as in rearrangements detection<ref name="rearrang">{{cite journal|last=Pratas|first=D|author2=Silva, R|author3= Pinho, A|author4= Ferreira, P|title=An alignment-free method to find and visualise rearrangements between pairs of DNA sequences|journal=Scientific Reports|date=May 18, 2015|volume=5|number=10203|pmid=25984837|doi=10.1038/srep10203|page=10203|pmc=4434998|bibcode=2015NatSR...510203P}}</ref>).

The [[Lempel–Ziv–Markov chain algorithm|LZMA]] lossless data compression algorithm combines Markov chains with [[LZ77 and LZ78|Lempel-Ziv compression]] to achieve very high compression ratios.