Klassische Information

Um Quanteninformation und ihre Funktionsweise zu beschreiben, beginnen wir mit einem Überblick über klassische Information. Es mag sich natürlich anfühlen zu fragen, warum in einem Kurs über Quanteninformation so viel Aufmerksamkeit auf klassische Information verwendet wird – doch dafür gibt es gute Gründe.

Zum einen sind die mathematischen Beschreibungen von Quanten- und klassischer Information trotz einiger spektakulärer Unterschiede einander tatsächlich sehr ähnlich. Klassische Information dient beim Studium der Quanteninformation außerdem als vertrauter Bezugspunkt sowie als Quelle für Analogien, die überraschend weit tragen. Häufig stellen Menschen Fragen zur Quanteninformation, die natürliche klassische Entsprechungen haben – und oft haben diese Fragen einfache Antworten, die sowohl Klarheit als auch Einsicht in die ursprünglichen Fragen zur Quanteninformation bieten. Tatsächlich ist es nicht übertrieben zu behaupten, dass man Quanteninformation nicht wirklich verstehen kann, ohne klassische Information zu verstehen.

Einige Lesende sind mit dem in diesem Abschnitt behandelten Material möglicherweise bereits vertraut, andere nicht – die Ausführungen richten sich jedoch an beide Gruppen. Neben der Hervorhebung der Aspekte klassischer Information, die für eine Einführung in die Quanteninformation am relevantesten sind, führt dieser Abschnitt die Dirac-Notation ein, die häufig zur Beschreibung von Vektoren und Matrizen in der Quanteninformation und -berechnung verwendet wird. Dabei ist die Dirac-Notation nicht spezifisch für die Quanteninformation; sie lässt sich ebenso gut im Kontext klassischer Information sowie in vielen anderen Situationen verwenden, in denen Vektoren und Matrizen auftreten.

Klassische Zustände und Wahrscheinlichkeitsvektoren

Angenommen, wir haben ein System, das Information speichert. Genauer gesagt nehmen wir an, dass dieses System zu jedem Zeitpunkt einen von endlich vielen klassischen Zuständen einnehmen kann. Der Begriff klassischer Zustand ist dabei intuitiv zu verstehen: als eine Konfiguration, die eindeutig erkannt und beschrieben werden kann.

Das archetypische Beispiel, auf das wir immer wieder zurückkommen werden, ist das Bit – ein System, dessen klassische Zustände $0$ und $1$ sind. Weitere Beispiele sind ein normaler sechsseitiger Würfel, dessen klassische Zustände $1,$ $2,$ $3,$ $4,$ $5,$ und $6$ sind (dargestellt durch die entsprechende Anzahl von Punkten auf der oben liegenden Seite); eine Nukleobase in einem DNA-Strang, deren klassische Zustände A, C, G und T sind; sowie der Schalter eines Elektrolüfters, dessen klassische Zustände üblicherweise hoch, mittel, niedrig und aus sind. Mathematisch gesehen sind die klassischen Zustände eines Systems der eigentliche Ausgangspunkt: Wir definieren ein Bit als ein System mit den klassischen Zuständen $0$ und $1,$ und entsprechend für Systeme mit anderen Zustandsmengen.

Der Einfachheit halber nennen wir das betrachtete System $\mathsf{X}$ und verwenden das Symbol $\Sigma$ für die Menge seiner klassischen Zustände. Zusätzlich zur bereits erwähnten Endlichkeit von $\Sigma$ setzen wir natürlich voraus, dass $\Sigma$ nicht leer ist – denn es wäre sinnlos, ein physikalisches System ohne Zustände anzunehmen. Obwohl es durchaus sinnvoll ist, physikalische Systeme mit unendlich vielen klassischen Zuständen zu betrachten, werden wir diese Möglichkeit hier außer Acht lassen, da sie zwar interessant, für diesen Kurs aber nicht relevant ist. Aus diesen Gründen und der Einfachheit halber werden wir den Begriff klassische Zustandsmenge von nun an für jede endliche und nicht leere Menge verwenden.

Hier einige Beispiele:

1. Wenn $\mathsf{X}$ ein Bit ist, dann $\Sigma = \{0,1\}.$ Diese Menge nennt man das binäre Alphabet.
2. Wenn $\mathsf{X}$ ein sechsseitiger Würfel ist, dann $\Sigma = \{1,2,3,4,5,6\}.$
3. Wenn $\mathsf{X}$ ein Lüfterschalter ist, dann $\Sigma = \{\mathrm{high}, \mathrm{medium}, \mathrm{low}, \mathrm{off}\}.$

Wenn wir $\mathsf{X}$ als Träger von Information betrachten, können den verschiedenen klassischen Zuständen von $\mathsf{X}$ bestimmte Bedeutungen zugewiesen werden, die zu unterschiedlichen Ergebnissen oder Konsequenzen führen. In solchen Fällen kann es ausreichen zu beschreiben, dass $\mathsf{X}$ schlicht einen seiner möglichen klassischen Zustände einnimmt. Wenn $\mathsf{X}$ zum Beispiel ein Lüfterschalter ist, könnten wir mit Sicherheit wissen, dass er auf hoch gestellt ist, und ihn dann auf mittel umschalten.

In der Informationsverarbeitung ist unser Wissen jedoch häufig unvollständig. Eine Möglichkeit, unser Wissen über den klassischen Zustand eines Systems $\mathsf{X}$ darzustellen, besteht darin, seinen verschiedenen möglichen klassischen Zuständen Wahrscheinlichkeiten zuzuordnen, was wir als probabilistischen Zustand bezeichnen.

Angenommen, $\mathsf{X}$ ist ein Bit. Basierend auf dem, was wir über die Vergangenheit von $\mathsf{X}$ wissen oder erwarten, könnten wir glauben, dass $\mathsf{X}$ mit Wahrscheinlichkeit $3/4$ im klassischen Zustand $0$ und mit Wahrscheinlichkeit $1/4$ im Zustand $1$ ist. Diese Überzeugungen lassen sich wie folgt darstellen:

$$\operatorname{Pr}(\mathsf{X}=0) = \frac{3}{4} \quad\text{und}\quad \operatorname{Pr}(\mathsf{X}=1) = \frac{1}{4}.$$

Eine kompaktere Darstellung dieses probabilistischen Zustands ist ein Spaltenvektor.

$$\begin{pmatrix} \frac{3}{4}\\[2mm] \frac{1}{4} \end{pmatrix}$$

Die Wahrscheinlichkeit, dass das Bit $0$ ist, steht oben im Vektor, und die Wahrscheinlichkeit, dass es $1$ ist, steht unten, da dies die übliche Reihenfolge der Menge $\{0,1\}$ ist.

Allgemein lässt sich ein probabilistischer Zustand eines Systems mit beliebiger klassischer Zustandsmenge auf dieselbe Weise als Wahrscheinlichkeitsvektor darstellen. Die Wahrscheinlichkeiten können in beliebiger Reihenfolge angeordnet werden, wobei es meist eine natürliche oder vorgegebene Reihenfolge gibt. Genauer gesagt kann jeder probabilistische Zustand durch einen Spaltenvektor mit zwei Eigenschaften dargestellt werden:

1. Alle Einträge des Vektors sind nichtnegative reelle Zahlen.
2. Die Summe der Einträge ist gleich $1.$

Umgekehrt kann jeder Spaltenvektor, der diese beiden Eigenschaften erfüllt, als Darstellung eines probabilistischen Zustands aufgefasst werden. Von nun an bezeichnen wir Vektoren dieser Form als Wahrscheinlichkeitsvektoren.

Neben der Kompaktheit dieser Notation hat die Identifikation probabilistischer Zustände mit Spaltenvektoren den Vorteil, dass Operationen auf probabilistischen Zuständen durch Matrix-Vektor-Multiplikation dargestellt werden können, wie wir gleich besprechen werden.

Messung probabilistischer Zustände

Als Nächstes betrachten wir, was passiert, wenn wir ein System messen, das sich in einem probabilistischen Zustand befindet. In diesem Zusammenhang bedeutet das Messen eines Systems lediglich, dass wir es betrachten und den klassischen Zustand, in dem es sich befindet, eindeutig erkennen. Intuitiv gesprochen können wir einen probabilistischen Zustand nicht „sehen"; wenn wir hinschauen, sehen wir einfach einen der möglichen klassischen Zustände.

Durch das Messen eines Systems können wir auch unser Wissen darüber verändern, sodass sich der probabilistische Zustand, den wir ihm zuweisen, ändern kann. Wenn wir erkennen, dass $\mathsf{X}$ im klassischen Zustand $a\in\Sigma$ ist, wird der neue Wahrscheinlichkeitsvektor, der unser Wissen über den Zustand von $\mathsf{X}$ darstellt, zum Vektor mit einer $1$ im Eintrag, der $a$ entspricht, und $0$ für alle anderen Einträge. Dieser Vektor zeigt an, dass $\mathsf{X}$ mit Sicherheit im klassischen Zustand $a$ ist – was wir wissen, nachdem wir ihn soeben erkannt haben. Wir bezeichnen diesen Vektor mit $\vert a\rangle,$ gelesen als „Ket $a$", aus einem Grund, der gleich erklärt wird. Vektoren dieser Art nennt man auch Standardbasisvektoren.

Wenn das betrachtete System beispielsweise ein Bit ist, sind die Standardbasisvektoren:

$$\vert 0\rangle = \begin{pmatrix}1\\[1mm] 0\end{pmatrix} \quad\text{und}\quad \vert 1\rangle = \begin{pmatrix}0\\[1mm] 1\end{pmatrix}.$$

Jeder zweidimensionale Spaltenvektor lässt sich als Linearkombination dieser beiden Vektoren ausdrücken. Zum Beispiel:

$$\begin{pmatrix} \frac{3}{4}\\[2mm] \frac{1}{4} \end{pmatrix} = \frac{3}{4}\,\vert 0\rangle + \frac{1}{4}\,\vert 1\rangle.$$

Diese Tatsache lässt sich auf beliebige klassische Zustandsmengen verallgemeinern: Jeder Spaltenvektor kann als Linearkombination von Standardbasisvektoren geschrieben werden. Sehr oft drücken wir Vektoren genau auf diese Weise aus.

Kommen wir zurück zur Änderung eines probabilistischen Zustands bei einer Messung und zur Verbindung mit unserem Alltagserleben. Angenommen, wir werfen eine faire Münze, bedecken sie aber, bevor wir hinschauen. Dann würden wir sagen, dass ihr probabilistischer Zustand

$$\begin{pmatrix} \frac{1}{2}\\[2mm] \frac{1}{2} \end{pmatrix} = \frac{1}{2}\,\vert\text{Kopf}\rangle + \frac{1}{2}\,\vert\text{Zahl}\rangle.$$

ist. Dabei ist die klassische Zustandsmenge unserer Münze $\{\text{Kopf},\text{Zahl}\}.$ Wir ordnen diese Zustände: Kopf zuerst, Zahl zweite.

$$\vert\text{Kopf}\rangle = \begin{pmatrix}1\\[1mm] 0\end{pmatrix} \quad\text{und}\quad \vert\text{Zahl}\rangle = \begin{pmatrix}0\\[1mm] 1\end{pmatrix}$$

Wenn wir die Münze aufdecken und hinschauen, sehen wir einen der beiden klassischen Zustände: Kopf oder Zahl. Nehmen wir an, das Ergebnis wäre Zahl, dann würden wir unsere Beschreibung des probabilistischen Zustands der Münze natürlich so aktualisieren, dass er $|\text{Zahl}\rangle$ wird. Würden wir die Münze dann wieder bedecken, aufdecken und erneut hinschauen, wäre der klassische Zustand immer noch Zahl – was mit dem probabilistischen Zustand $|\text{Zahl}\rangle$ übereinstimmt.

Das mag trivial erscheinen, und in gewissem Sinne ist es das auch. Quantensysteme verhalten sich jedoch auf eine völlig analoge Weise, obwohl ihre Messeigenschaften häufig als seltsam oder ungewöhnlich empfunden werden. Indem wir die entsprechenden Eigenschaften klassischer Systeme aufzeigen, wird das Verhalten von Quanteninformation weniger befremdlich.

Eine letzte Anmerkung zu Messungen probabilistischer Zustände: Probabilistische Zustände beschreiben Wissen oder Überzeugungen, nicht notwendigerweise eine tatsächliche Realität, und das Messen verändert nur unser Wissen, nicht das System selbst. Der Zustand einer Münze, nachdem sie geworfen wurde, aber bevor wir hinschauen, ist entweder Kopf oder Zahl – wir wissen es nur nicht, bis wir nachsehen. Wenn wir sehen, dass der klassische Zustand Zahl ist, würden wir den Vektor, der unser Wissen beschreibt, natürlich zu $|\text{Zahl}\rangle$ aktualisieren – aber für jemanden, der die Münze beim Aufdecken nicht gesehen hat, bleibt der probabilistische Zustand unverändert. Das ist kein Problem; verschiedene Personen können unterschiedliches Wissen oder unterschiedliche Überzeugungen über ein bestimmtes System haben und es daher durch verschiedene Wahrscheinlichkeitsvektoren beschreiben.

Klassische Operationen

Im letzten Teil dieser kurzen Einführung in klassische Information betrachten wir die Arten von Operationen, die auf einem klassischen System durchgeführt werden können.

Deterministische Operationen

Zunächst gibt es deterministische Operationen, bei denen jeder klassische Zustand $a\in\Sigma$ in $f(a)$ für eine Funktion $f$ der Form $f:\Sigma\rightarrow\Sigma$ überführt wird.

Wenn zum Beispiel $\Sigma = \{0,1\},$ gibt es vier solche Funktionen $f_1,$ $f_2,$ $f_3,$ und $f_4,$ die sich durch Wertetabellen wie folgt darstellen lassen:

$$\begin{array}{c|c} a & f_1(a)\\ \hline 0 & 0\\ 1 & 0 \end{array} \qquad \begin{array}{c|c} a & f_2(a)\\ \hline 0 & 0\\ 1 & 1 \end{array} \qquad \begin{array}{c|c} a & f_3(a)\\ \hline 0 & 1\\ 1 & 0 \end{array} \qquad \begin{array}{c|c} a & f_4(a)\\ \hline 0 & 1\\ 1 & 1 \end{array}$$

Die erste und die letzte dieser Funktionen sind konstant: $f_1(a) = 0$ und $f_4(a) = 1$ für alle $a\in\Sigma.$ Die mittleren beiden sind nicht konstant, sondern balanciert: jeder der beiden Ausgabewerte tritt gleich oft auf (hier einmal), wenn wir über alle möglichen Eingaben iterieren. Die Funktion $f_2$ ist die Identitätsfunktion: $f_2(a) = a$ für jedes $a\in\Sigma.$ Und $f_3$ ist die Funktion $f_3(0) = 1$ und $f_3(1) = 0,$ die besser als NICHT-Funktion (NOT) bekannt ist.

Die Wirkungen deterministischer Operationen auf probabilistische Zustände lassen sich durch Matrix-Vektor-Multiplikation darstellen. Konkret ist die Matrix $M,$ die eine gegebene Funktion $f:\Sigma\rightarrow\Sigma$ darstellt, diejenige, die

$$M \vert a \rangle = \vert f(a)\rangle$$

für jedes $a\in\Sigma$ erfüllt. Eine solche Matrix existiert stets und ist durch diese Bedingung eindeutig bestimmt. Matrizen, die deterministische Operationen darstellen, haben in jeder Spalte genau eine $1$ und $0$ für alle anderen Einträge.

Die Matrizen $M_1,\ldots,M_4,$ die den Funktionen $f_1,\ldots,f_4$ entsprechen, sind wie folgt:

$$M_1 = \begin{pmatrix} 1 & 1\\ 0 & 0 \end{pmatrix}, \hspace{4mm} M_2 = \begin{pmatrix} 1 & 0\\ 0 & 1 \end{pmatrix}, \hspace{4mm} M_3 = \begin{pmatrix} 0 & 1\\ 1 & 0 \end{pmatrix}, \hspace{4mm} M_4 = \begin{pmatrix} 0 & 0\\ 1 & 1 \end{pmatrix}.$$

Hier ist eine kurze Überprüfung, die zeigt, dass die erste Matrix korrekt ist. Die anderen drei lassen sich analog überprüfen.

$$\begin{aligned} M_1 \vert 0\rangle & = \begin{pmatrix} 1 & 1\\ 0 & 0 \end{pmatrix} \begin{pmatrix} 1\\ 0 \end{pmatrix} = \begin{pmatrix} 1\\ 0 \end{pmatrix} = \vert 0\rangle = \vert f_1(0)\rangle \\[4mm] M_1 \vert 1\rangle & = \begin{pmatrix} 1 & 1\\ 0 & 0 \end{pmatrix} \begin{pmatrix} 0\\ 1 \end{pmatrix} = \begin{pmatrix} 1\\ 0 \end{pmatrix} = \vert 0\rangle = \vert f_1(1)\rangle \end{aligned}$$

Eine praktische Möglichkeit, Matrizen dieser und anderer Formen darzustellen, nutzt eine analoge Notation für Zeilenvektoren zu der zuvor diskutierten für Spaltenvektoren: Wir bezeichnen mit $\langle a \vert$ den Zeilenvektor mit einer $1$ im Eintrag, der $a$ entspricht, und null für alle anderen Einträge, für jedes $a\in\Sigma.$ Dieser Vektor wird als „Bra $a$" gelesen.

Wenn zum Beispiel $\Sigma = \{0,1\},$ dann gilt:

$$\langle 0 \vert = \begin{pmatrix} 1 & 0 \end{pmatrix} \quad\text{und}\quad \langle 1 \vert = \begin{pmatrix} 0 & 1 \end{pmatrix}.$$

Für eine beliebige klassische Zustandsmenge $\Sigma$ können wir Zeilen- und Spaltenvektoren als Matrizen betrachten und die Matrixmultiplikation $\vert b\rangle \langle a\vert$ durchführen. Wir erhalten eine quadratische Matrix mit einer $1$ im Eintrag, der dem Paar $(b,a)$ entspricht (die Zeile entspricht dem klassischen Zustand $b$ und die Spalte dem klassischen Zustand $a$), und $0$ für alle anderen Einträge. Zum Beispiel:

$$\vert 0 \rangle \langle 1 \vert = \begin{pmatrix} 1\\ 0 \end{pmatrix} \begin{pmatrix} 0 & 1 \end{pmatrix} = \begin{pmatrix} 0 & 1 \\ 0 & 0 \end{pmatrix}.$$

Mit dieser Notation lässt sich die Matrix $M,$ die einer gegebenen Funktion $f:\Sigma\rightarrow\Sigma$ entspricht, wie folgt ausdrücken:

$$M = \sum_{a\in\Sigma} \vert f(a) \rangle \langle a \vert.$$

Betrachten wir beispielsweise die Funktion $f_4$ von oben, für die $\Sigma = \{0,1\}.$ Wir erhalten die Matrix:

$$M_4 = \vert f_4(0) \rangle \langle 0 \vert + \vert f_4(1) \rangle \langle 1 \vert = \vert 1\rangle \langle 0\vert + \vert 1\rangle \langle 1\vert = \begin{pmatrix} 0 & 0\\ 1 & 0 \end{pmatrix} + \begin{pmatrix} 0 & 0\\ 0 & 1 \end{pmatrix} = \begin{pmatrix} 0 & 0\\ 1 & 1 \end{pmatrix}.$$

Der Grund, warum das funktioniert, ist folgender. Wenn wir Vektoren wieder als Matrizen betrachten und diesmal die Multiplikation $\langle a \vert \vert b \rangle$ durchführen, erhalten wir eine $1\times 1$-Matrix, die wir als Skalar (also eine Zahl) auffassen können. Der Übersichtlichkeit halber schreiben wir dieses Produkt als $\langle a \vert b\rangle$ statt $\langle a \vert \vert b \rangle.$ Dieses Produkt erfüllt die folgende einfache Formel:

$$\langle a \vert b \rangle = \begin{cases} 1 & a = b\\[1mm] 0 & a \neq b. \end{cases}$$

Mit dieser Beobachtung und der Tatsache, dass die Matrixmultiplikation assoziativ und linear ist, ergibt sich:

$$M \vert b \rangle = \Biggl( \sum_{a\in\Sigma} \vert f(a) \rangle \langle a \vert \Biggr) \vert b\rangle = \sum_{a\in\Sigma} \vert f(a) \rangle \langle a \vert b \rangle = \vert f(b)\rangle,$$

für jedes $b\in\Sigma,$ was genau das ist, was wir von der Matrix $M$ verlangen.

Wie wir in einer späteren Lektion ausführlicher besprechen werden, kann $\langle a \vert b \rangle$ auch als inneres Produkt der Vektoren $\vert a\rangle$ und $\vert b\rangle$ aufgefasst werden. Innere Produkte sind in der Quanteninformation von entscheidender Bedeutung, aber wir vertagen ihre Diskussion, bis wir sie brauchen.

An dieser Stelle dürfte klar sein, warum die Begriffe „Bra" und „Ket" so heißen: Setzt man ein „Bra" $\langle a\vert$ mit einem „Ket" $\vert b\rangle$ zusammen, erhält man ein „Bracket" (Klammer) $\langle a \vert b\rangle.$ Diese Notation und Terminologie geht auf Paul Dirac zurück und wird daher als Dirac-Notation bezeichnet.

Probabilistische Operationen und stochastische Matrizen

Neben deterministischen Operationen gibt es probabilistische Operationen.

Betrachten wir dazu folgende Operation auf einem Bit. Wenn der klassische Zustand des Bits $0$ ist, bleibt er unverändert; ist der klassische Zustand $1,$ wird er mit Wahrscheinlichkeit $1/2$ zu $0$ und mit Wahrscheinlichkeit $1/2$ zu $1$ umgekehrt. Diese Operation wird durch die Matrix

$$\begin{pmatrix} 1 & \frac{1}{2}\\[1mm] 0 & \frac{1}{2} \end{pmatrix}$$

dargestellt. Man kann überprüfen, dass diese Matrix das Richtige tut, indem man die beiden Standardbasisvektoren mit ihr multipliziert.

Für eine beliebige klassische Zustandsmenge lassen sich alle probabilistischen Operationen mathematisch als diejenigen beschreiben, die durch stochastische Matrizen dargestellt werden – also Matrizen mit diesen zwei Eigenschaften:

1. Alle Einträge sind nichtnegative reelle Zahlen.
2. Die Einträge jeder Spalte summieren sich zu $1.$

Äquivalent dazu sind stochastische Matrizen Matrizen, deren Spalten allesamt Wahrscheinlichkeitsvektoren bilden.

Probabilistische Operationen lassen sich intuitiv als Operationen verstehen, bei denen Zufälligkeit irgendwie genutzt oder eingeführt wird – genau wie im obigen Beispiel. Bei der stochastischen Matrixdarstellung einer probabilistischen Operation kann jede Spalte als Vektordarstellung des probabilistischen Zustands angesehen werden, der erzeugt wird, wenn der klassische Zustand als Eingabe der entsprechenden Spalte entspricht.

Stochastische Matrizen lassen sich auch als genau diejenigen Matrizen charakterisieren, die Wahrscheinlichkeitsvektoren stets auf Wahrscheinlichkeitsvektoren abbilden. Das heißt: Stochastische Matrizen bilden Wahrscheinlichkeitsvektoren immer auf Wahrscheinlichkeitsvektoren ab, und jede Matrix, die das tut, muss stochastisch sein.

Schließlich lassen sich probabilistische Operationen auch als zufällige Auswahl von deterministischen Operationen auffassen. Die Operation im obigen Beispiel kann zum Beispiel als Anwendung entweder der Identitätsfunktion oder der konstanten 0-Funktion, jeweils mit Wahrscheinlichkeit $1/2,$ betrachtet werden. Das stimmt mit der Gleichung

$$\begin{pmatrix} 1 & \frac{1}{2}\\[1mm] 0 & \frac{1}{2} \end{pmatrix} = \frac{1}{2} \begin{pmatrix} 1 & 0\\[1mm] 0 & 1 \end{pmatrix} + \frac{1}{2} \begin{pmatrix} 1 & 1\\[1mm] 0 & 0 \end{pmatrix}$$

überein. Eine solche Zerlegung ist stets möglich, für eine beliebige klassische Zustandsmenge und jede stochastische Matrix, deren Zeilen und Spalten mit dieser Zustandsmenge indiziert sind.

Kompositionen probabilistischer Operationen

Angenommen, $\mathsf{X}$ ist ein System mit der klassischen Zustandsmenge $\Sigma,$ und $M_1,\ldots,M_n$ sind stochastische Matrizen, die probabilistische Operationen auf dem System $\mathsf{X}$ darstellen.

Wenn die erste Operation $M_1$ auf den durch einen Wahrscheinlichkeitsvektor $u$ dargestellten probabilistischen Zustand angewendet wird, ergibt sich der neue probabilistische Zustand als der Vektor $M_1 u.$ Wenn wir dann die zweite probabilistische Operation $M_2$ auf diesen neuen Wahrscheinlichkeitsvektor anwenden, erhalten wir den Wahrscheinlichkeitsvektor

$$M_2 (M_1 u) = (M_2 M_1) u.$$

Die Gleichheit folgt aus der Tatsache, dass die Matrixmultiplikation (die die Matrix-Vektor-Multiplikation als Spezialfall einschließt) eine assoziative Operation ist. Die probabilistische Operation, die durch die Komposition der ersten und zweiten probabilistischen Operation entsteht (wobei zuerst $M_1$ und dann $M_2$ angewendet wird), wird also durch die Matrix $M_2 M_1$ dargestellt, die notwendigerweise stochastisch ist.

Allgemeiner gilt: Die Komposition der durch die Matrizen $M_1,\ldots,M_n$ dargestellten probabilistischen Operationen in dieser Reihenfolge – d. h. $M_1$ wird zuerst angewendet, $M_2$ als zweites und so weiter, mit $M_n$ als letzter Operation – wird durch das Matrizenprodukt

$$M_n \,\cdots\, M_1$$

dargestellt.

Die Reihenfolge ist dabei wichtig: Obwohl die Matrixmultiplikation assoziativ ist, ist sie keine kommutative Operation. Wenn zum Beispiel

$$M_1 = \begin{pmatrix} 1 & 1\\[1mm] 0 & 0 \end{pmatrix} \quad\text{und}\quad M_2 = \begin{pmatrix} 0 & 1\\[1mm] 1 & 0 \end{pmatrix},$$

dann gilt:

$$M_2 M_1 = \begin{pmatrix} 0 & 0 \\[1mm] 1 & 1 \end{pmatrix} \quad\text{und}\quad M_1 M_2 = \begin{pmatrix} 1 & 1\\[1mm] 0 & 0 \end{pmatrix}.$$

Das heißt, die Reihenfolge, in der probabilistische Operationen komponiert werden, ist entscheidend; eine Änderung der Reihenfolge kann die resultierende Operation verändern.