Matrixtheorie

04/12/2009 - 22:56 von christian.palmes | Report spam
Hallo,

ich bin im Rahmen eines stochastischen Problems auf folgende Frage
gestoßen:

Seien A,B,C doppelt stochastische Matrizen, genauer:

A,B,C elem R^(nxn) und alle Eintràge sind nichtnegativ und die Zeilen
und Spaltensummen ergeben immer eins.

Für B gilt noch zusàtzlich:

B ist symmetrisch und es existiert ein r>0, so dass B_ii = r, für alle
i und B_ij = r oder 0 für alle i,j, d.h.
B kann nur die Werte r und 0 annehmen, und auf der Diagonalen wird
immer der Wert 1 angenommen.

Es geht um folgendes Problem:

Gilt die Ungleichung

\sum_{i=1..n} | (CBA)_1i - 1/n | <= \sum_{i=1..n} |(CA)_1i - 1/n| ?

(Falls A,B,C kommutieren, ist die Aussage leicht zu zeigen)

Der stochastische Hintergrund:

Wir haben eine endliche, inhomogene Markovkette. Genauer betrachten
wir nur die ersten 4 Glieder dieser Kette: Wir starten in der
Identitàt (1) und haben dann die Übergangsmatrizen A,B,C, die doppelt
stochastisch sind, d.h. die Gleichverteilung als stationàre Verteilung
besitzen. Die Frage ist nun, ob die Kette "weniger gut durchmischt
ist", wenn man den Übergang B weglàßt.
(CBA)_1i ist gerade die Wahrscheinlichkeit nach den drei Übergàngen,
d.h. im 4. Glied, im Zustand i zu sein.


Vielen Dank,

Gruß Christian
 

Lesen sie die antworten

#1 christian.palmes
05/12/2009 - 18:44 | Warnen spam
Hi,


ok, ich gebe zu, dass es vielleicht nicht sonderlich viel Spaß macht,
über meine Aufgabenstellung nachzudenken. Daher hier mein Problem ohne
mathematischen Formalismus:

Das besonders erstaunlich finde ich übrigens, dass die Aussage
anschaulich vollkommen klar ist, man aber irgendwie beweistechnisch
keinen Zugriff bekommt. Also:

Gegeben ein Kartenspiel mit n Karten und eine natürliche Zahl 1 <= m
<= n. Diese Karten denken wir uns am besten von 1,..,n
durchnummeriert. Zu Beginn liegen sie in sortierter Reihenfolge, d.h.
hier 1,2,..,n.

Jetzt definiere ich einen Mischschritt wie folgt:

Es werden m Karten rein zufàllig aus dem Kartendeck herausgezogen und
in _derselben Reihenfolge_, d.h. ihre relative Anordnung àndert sich
nicht, wieder oben auf das Deck heraufgelegt. Das ganze mache ich
jetzt k mal, d.h. ich mische k mal nach diesem Verfahren. Die k
Mischschritte sind natürlich unabhàngig voneinader.

Nun mache ich dasselbe nocheinmal (zu beginn wieder ein vorsortiertes
Kartendeck) nur mit einem Unterschied:

Bevor ich die m Karten wieder oben drauf lege, mische ich diese
nochmal kràftig, d.h. die relative Reihenfolge der m Karten beim
Zurücklegen muss _nicht_ eingehalten werden.

Intuitiv durchmischt zweite Variante klar schneller als die Erste.
Aber wie kann man das formal zeigen? Die Anordnungen des Kartendecks
sind natürlich Elemente der symmetrischen Gruppe S_n. Sei \pi \in
\S_n, dann meine ich mit \pi(2) = 7 z.B., dass an Position 2 Karte 7
liegt. U bezeichne die Gleichverteilung auf S_n.

Q^k sei die Verteilung nach k Mischschritten erster Variante (d.h. mit
Beibehaltung relativer Ordnung beim zurücklegen)
P^k sei die Verteilung nach k Mischschritten zweiter Variante.

Ich will nun zeigen:

||Q^k - U|| => ||P^k - U|| für alle k >= 1 (*)

Mit || .. || meine ich den Variationsabstand zwischen zwei
Wahrscheinlichkeitsmaßen, d.h.

||V - U|| = 1/2 * \sum_\pi |V(pi) - U(pi)|, wobei V irgendein
Wahrscheinlichkeitsmaß auf S_n ist und natürlich U(pi) = 1/n! gilt.


Das vorherige Posting ist natürlich nicht àquivalent zu dieser
Bedinung. Stimmt aber die Ungleichung darin, so ist das hinreichend,
dass auch obige Ungleichung stimmt.

Das ist keine Übungsaufgabe oder so, deshalb weiß ich genau genommen
nicht, ob (*) überhaupt stimmt. Aber ich finde, das ist anschaulich
schon mehr als offensichtlich! oder?

Gruß Christian

Ähnliche fragen