Hilfe bei Beweis zur Varianzreduktion

curry-king

Hallo zusammen,

gegeben sind disjunkte Mengen von ganzen Zahlen. Durch den Austausch zweier Zahlen zwischen zwei dieser disjunkten Mengen soll die Varianz in beiden Mengen bestenfalls verringert werden.
Ich wähle also die erste Menge $M_{1}$ zufällig. Die zweite Menge $M_{2}$ wähle ich so, daß die Differenz des Mittels zwischen erster und zweiter minimal unter allen anderen Mengen ist.
Der Austausch der Zahlen erfolgt ähnlich. Ich schiebe diejenige Zahl aus der zweiten in die erste Menge, die zum Mittel der ersten die geringste Abweichung aufweist. Analog wird eine Zahl aus der ersten in die zweite Menge verschoben.

Falls dieses Verfahren die Varianz reduziert möchte ich dafür einen Beweis formulieren. Darin bin ich jetzt aber kein Spezialist.

Als erstes bestimme ich $i$ und $j$ so, dass $\left|\mu^{i}_{pre}-\mu^{j}_{pre}\right|$ minimal ist, wobei die $\mu_{pre}$ s die Mittelwerte der Mengen vor dem Tausch sind.

Als nächstes bestimme ich $k$ und $l$ so, dass für die Zahlen $m_{k} \in M_{1}$ und $m_{l} \in M_{2}$ gilt: $min\left|(\mu^{i}_{pre}-m_{l})\right|$ und $min\left|(\mu^{j}_{pre}-m_{k})\right|$ . Diese werden dann ausgetauscht.
Das führt dann nur zu einer Varianzreduktion in einer Menge, falls die Abweichung der entfernten Zahl größer war als die der neu hinzugefügten.
Ist das richtig? Wie kann ich das formal ausdrücken?

Danke für jede Hilfe!

Michael E.

Ich verstehe den Kontext noch nicht ganz. Machst du nur eine Iteration oder solange, bis du keine lokale Verbesserung mehr mit deinem Algorithmus findest? Soll die Wahl von M₂ optimal sein? Soll nur getauscht werden, wenn das Tauschen in beiden Mengen zu einer Verbesserung führt? Was machst du, wenn in der einen Menge die Varianz verkleinert und in der anderen Menge die Varianz vergrößert wird?

curry-king

Michael E. schrieb:

Machst du nur eine Iteration oder solange, bis du keine lokale Verbesserung mehr mit deinem Algorithmus findest?

Ich mache eine feste Anzahl von Iterationen, zwischendurch soll abgebrochen werden, falls die Varianz wieder steigt.

Michael E. schrieb:

Soll die Wahl von M₂ optimal sein?

Ja.

Michael E. schrieb:

Soll nur getauscht werden, wenn das Tauschen in beiden Mengen zu einer Verbesserung führt?

Nein, es soll immer getauscht werden. Das die Verbesserung in beiden Mengen eintritt wäre der beste Fall. Diesen möchte ich formal beweisen.
Es reicht schon sicherzustellen, das diese Methode u. U. eine Varianzreduktion bewirkt. Aber wie gesagt möchte ich das formalisieren.

Michael E. schrieb:

Was machst du, wenn in der einen Menge die Varianz verkleinert und in der anderen Menge die Varianz vergrößert wird?

Dann schau ich, ob sich die Summe der beiden Varianzen von vorher auf nachher vergrößert haben. In diesem Fall kann man dann vielleicht abbrechen.