Der Geburtsort Andrei Andrejewitsch Markows ist Ryasan, ein Verwaltungszentrum einer Region, die etwa 200 km südöstlich von Moskau liegt. Sein Vater, Andrei Ggrigoriewitsch Markow, arbeitet bei der staatlichen Forstverwaltung. Als ihm eine Stelle als Gutsverwalter in St. Petersburg angeboten wird, zieht er mit seiner jungen Familie in die Hauptstadt Russlands.

In seinen ersten Lebensjahren leidet Andrei unter erheblichen gesundheitlichen Problemen; bis zum Alter von 10 Jahren kann er nur mithilfe von Krücken gehen.

Bereits während seiner Schulzeit fällt der Junge durch seine außergewöhnliche Begabung im Fach Mathematik auf. Im Alter von 17 Jahren verfasst er einen Beitrag über die Lösung von linearen Differentialgleichungen, die er zwei Mathematik-Professoren der Universität, Alexander Nikolajewitsch Korkin und Igor Iwanowitsch Zolotarjow, vorlegt. Zwar ist das von Andrei dargestellte Verfahren nicht neu, aber die Untersuchung ist als selbstständige Leistung bemerkenswert, und von da an darf der Schüler an den Samstag-Seminaren Korkins teilnehmen, die dieser regelmäßig seinen Studenten anbietet.

Mit 18 Jahren kann Andrei Markow endlich die Universität besuchen. Außer den Vorlesungen von Korkin und Zolotarjow hört er auch die des Institutsleiters Pafnuti Lwowitsch Tschebyschow, dessen Anregungen für eigene, selbstständige Untersuchungen von Markow gerne aufgenommen werden. Nach vier Jahren legt er sein Examen ab, nachdem er im Jahr zuvor bereits mit einer Arbeit zum Thema Über die Lösung von Differentialgleichungen mithilfe von Kettenbrüchen mit Anwendung auf \( (1 + x^2)\cdot y' = n \cdot (1 + y^2)\ \) eine Goldmedaille der Fakultät gewonnen hat.

1880 wird er mit einer Arbeit zur Zahlentheorie promoviert. Obwohl dieser Beitrag zeitnah ins Französische übersetzt und in den Mathematischen Annalen veröffentlicht wird, vergehen 30 Jahre, bis westeuropäische Mathematiker damit beginnen, sich mit den darin enthaltenen tiefsinnigen Entdeckungen auseinanderzusetzen.

Nach seiner Promotion übernimmt Markow als Privatdozent Analysis-Vorlesungen an der Universität; parallel dazu arbeitet er an seiner Habilitationsschrift.

1883 heiratet er seine Jugendliebe Maria Ivanova Valvatyeva. Sie ist die Tochter des Gutsbesitzers, dessen Ländereien von Markows Vater verwaltet werden; er hat sie in Mathematik unterrichtet und ihr bereits in frühen Jahren einen Heiratsantrag gemacht. Allerdings widersetzt sich deren Mutter der "nicht standesgemäßen" Heirat. Erst als die Ernennung zum Hochschul-Professor bevorsteht, willigt sie ein. Aus der Ehe geht nur ein Kind hervor; der Sohn (mit denselben Vornamen wie der Vater) wird später Professor für mathematische Logik an der Moskauer Universität.

1886 wird Markow zum außerordentlichen Professor an der St. Petersburger Universität ernannt, gleichzeitig als Kandidat der Russischen Akademie der Wissenschaften nominiert (ab 1896 Mitglied als Nachfolger Tschebyschows). Eine ordentliche Professur hat er nur in der Zeit zwischen 1896 und 1905 inne; er setzt aber seine Lehrtätigkeit auch noch viele Jahre nach seiner offiziellen Emeritierung fort.

Markows Veröffentlichungen zeigen sein vielseitiges Interesse. Insbesondere untersucht er, unter welchen möglichst allgemeinen Bedingungen das Gesetz der Großen Zahlen beziehungsweise der Zentrale Grenzwertsatz gelten, und setzt so – zusammen mit Alexander Michailowitsch Ljapunow – die Arbeit des hochverehrten Lehrers Tschebyschow fort. Markows Wahrscheinlichkeitsrechnung erscheint in vier Sprachen mit insgesamt 29 Auflagen, seine Methode der kleinsten Quadrate wird neunmal aufgelegt.

Um die Jahrhundertwende entwickelt sich eine heftige Auseinandersetzung mit seinem Moskauer Kollegen Pawel Alexejewitsch Nekrassow, der ursprünglich Theologie studiert hatte und seine orthodoxen religiös-philosophischen Ansichten auf die Wahrscheinlichkeitsrechnung anwendet. Nekrassow sieht Parallelen zwischen dem freien Willen eines Menschen und unabhängigen Ereignissen in der Wahrscheinlichkeitstheorie. Nach dessen Überzeugung ist das Gesetz des Großen Zahlen nur bei unabhängigen Zufallsvariablen anwendbar; die Stabilisierung von relativen Häufigkeiten beispielsweise in der Kriminalstatistik beweise, dass die zugrundeliegenden Entscheidungen aus freiem Willen und unabhängig voneinander getroffen wurden.

Markow hingegen (der 1901 aus der Kirche austritt, als die orthodoxe Kirche Lew Nikolajewitsch Tolstoi exkommuniziert) geht davon aus, dass das Gesetz der Großen Zahlen unter gewissen Bedingungen auch für abhängige Variablen gilt. Mit der von ihm entwickelten Theorie der stochastischen Prozesse – später ihm zu Ehren als Markow-Ketten bezeichnet – erschließt er ein neues Teilgebiet der Wahrscheinlichkeitsrechnung: Im Unterschied zu den bisher üblicherweise betrachteten Zufallsexperimenten, denen bestimmte, feste Wahrscheinlichkeiten zugrundeliegen, interessiert er sich für Prozesse, bei denen die Wahrscheinlichkeit für das Eintreten eines bestimmten Ereignisses davon abhängt, welches Ereignis zuletzt eingetreten ist. Diese Zufallsprozesse lassen sich mithilfe von Übergangswahrscheinlichkeiten beschreiben, also den Wahrscheinlichkeiten, mit denen der Wechsel von einem vorherigen "Zustand" zum aktuellen "Zustand" eintritt, und hiermit schließt man dann auf zukünftige "Zustände".

Schrittweise gelingt ihm auch der allgemeine Beweis, dass es bei langen Prozessen zu einer Stabilisierung der relativen Häufigkeiten für die einzelnen Zustände kommt. – Als Beispiel eines solchen Prozesses untersucht Markow die Abfolge von Konsonanten und Vokalen in einem berühmten literarischen Werk: Er wertet die ersten 20 000 Buchstaben (also ohne Satzzeichen und Leerstellen) von Alexander Sergejewitsch Puschkins Versroman Eugen Onegin (veröffentlicht 1833) aus; der Textauszug enthält 43,2 % Vokale und 56,8 % Konsonanten. Dann gliedert er die Zeichen in 200 Blöcke mit jeweils 10 Zeilen und 10 Spalten und bestimmt für jede Zeile und Spalte die Anzahl der Konsonanten und Vokale, außerdem Mittelwert und Streuung dieser Häufigkeitsverteilung. Weiter zählt er die Paare aufeinanderfolgender Buchstaben aus: In 19,1 % der Paare folgen zwei Konsonanten aufeinander, in 5,5 % zwei Vokale. Wenn der Puschkin'sche Text dem Prinzip der Unabhängigkeit unterliegen würde, dann müsste der Produktsatz für Wahrscheinlichkeiten anwendbar sein; es zeigt sich aber, dass zum Beispiel der Anteil von Vokal-Vokal-Paaren nicht \(0,432^2 \approx 0{,}187\), sondern nur etwa ein Drittel davon beträgt. Markow untersucht auch aufeinanderfolgende Tripel von Buchstaben sowie den Text eines anderen russischen Schriftstellers.

Markows Veröffentlichungen finden zunächst wenig Beachtung; heute spielen Modellierungen mithilfe von Markow-Ketten eine große Rolle in zahlreichen Wissenschaften. Die von Markow geschaffenen mathematischen Grundlagen werden später von Andrei Nikolajewitsch Kolmogorow zu einer allgemeinen Theorie weiterentwickelt.

Im Jahr 1902 wird der Schriftsteller Maxim Gorki (eigentlich: Alexei Maximowitsch Peschkow) als Mitglied in die Russische Akademie der Wissenschaften gewählt; allerdings wird die Wahl des Linksaktivisten auf Geheiß des Zaren annulliert. Markow protestiert heftig gegen diesen Eingriff des Herrschers in die Entscheidung der Institution, und als er im darauf folgenden Jahr wegen seiner besonderen Verdienste um die russische Wissenschaft vom Zaren geehrt werden soll, lehnt er diese Ehrung als Zeichen seines Protests ab.

1907 löst Zar Nikolaus II die Volksvertretung, die Duma, auf, da – nach einer freien Wahl – linke Gruppierungen eine Mehrheit errungen haben. Daraufhin erklärt Markow öffentlich seinen Austritt aus der Akademie. Dieser Schritt hat aber keine Konsequenzen. Als 1913 die Romanows mit großem Pomp die 300-jährige Herrschaft ihrer Dynastie auf dem Zarenthron feiern, setzt Markow ein anderes Jubiläum dagegen: Er feiert 200 Jahre Gesetz der großen Zahlen, in Erinnerung an die 1713 posthum veröffentliche Ars Conjectandi von Jakob Bernoulli.

Nach Ausbruch der russischen Revolution übernimmt er – ohne Bezahlung – im Auftrag der Akademie der Wissenschaften eine Tätigkeit als Mathematiklehrer in der Provinz. Nach der Rückkehr in das (umbenannte) Petrograd verschlechtert sich sein gesundheitlicher Zustand, und, obwohl er kaum in der Lage ist, sich aufrecht zu halten, nimmt er vorübergehend seine Vorlesungen über Wahrscheinlichkeitsrechnung an der Universität wieder auf, erliegt aber wenige Monate später seinem Leiden.