Ziehen mit Zurücklegen mit großen Zahlen

12.06.2024, 20:12

IfindU

Ziehen mit Zurücklegen mit großen Zahlen

Hallo zusammen,

es ist laaange her, dass ich einen Thread im Forum eröffnet habe.

Ich habe folgende Situation:
Meine SSD Festplatte besitzt 1TB Speicher, konfiguriert mit einer Blockgröße von 512KB.
D.h. die Festplatte besteht aus 2 000 000 dieser disjunkten, unterscheidbaren Blöcke. Die Reihenfolge der Blöcke ist im folgenden nicht relevant, auch wenn der Computer diese natürlich für verschiedene Zwecke verwendet.

Beim Schreiben/Ändern von Dateien werden immer ganze Blöcke geschrieben, d.h. die kleinste Einheit die mich hier interessiert.
Der Computer ändert nun "zufällig" jeden Tag 2000 der Blöcke, wobei alle Blöcke sind gleichwahrscheinlich modifiziert werden (1/2 000 000).

Wie finde ich wie viele "eindeutige" Blöcke nach 7 Tagen (im Schnitt im Sinne des Erwartungswertes) modifiziert wurden, und sei es nur approximativ.

Beispiel:
Wenn ich jeden Tag Blöcke 1 bis 2000 "ziehe", dann habe ich am Ende die Blöcke $\begin{eqnarray*} \{ 1, 2, \ldots, 2 000\} \end{eqnarray*}$ modifiziert. Die Kardinalität wäre 2000.

Wenn ich jeden Tag neue Blöcke ziehe, könnte ich zu Tag $\begin{eqnarray*} k \end{eqnarray*}$ die Blöcke $\begin{eqnarray*} k \cdot 2000+ \{ 1, 2, \ldots, 2 000\} \end{eqnarray*}$ haben (mit $\begin{eqnarray*} a + M = \{a+m | m \in M\} \end{eqnarray*}$ ) und nach 7 Tagen dann $\begin{eqnarray*} \{ 1, 2, \ldots, 14000 \} \end{eqnarray*}$ .

Wären das die einzigen beiden Möglichkeiten, und beide gleichwahrscheinlich, so wäre mein Erwartungswert $\begin{eqnarray*} \frac 1 2 (2000 + 14000) = 7000 \end{eqnarray*}$ .

Nun gibt es leider viel mehr Kombinationen.

Meine Ideen:

Offensichtlich sind es höchstens $\begin{eqnarray*} 7 \cdot 2000 \end{eqnarray*}$ ,

Ich wollte Kombatorik mit Zurücklegen benutzen. Allerdings werden hier täglich Gruppen von Blöcken zufällig genommen. Würde man hier modellieren, dass man jeden Tag 2000 Blöcke ohne Zurücklegen zieht, oder die Potenzmenge von $\begin{eqnarray*} \{ 1, 2, \ldots, 2 000 000\} \end{eqnarray*}$ nehmen und darin ziehen?

Zudem, sobald ich das habe: Wie finde ich raus was die durchschnittliche geänderte Blockgröße ist.

Vielen Dank für Schubser in die richtige Richtung smile

13.06.2024, 21:10

IfindU

Auf diesen Beitrag antworten »

RE: Ziehen mit Zurücklegen mit großen Zahlen
Annahme: Wenn ich $\begin{eqnarray*} N \end{eqnarray*}$ Blöcke habe, nummeriert von $\begin{eqnarray*} 1 \end{eqnarray*}$ bis $\begin{eqnarray*} N \end{eqnarray*}$ , und $\begin{eqnarray*} K \end{eqnarray*}$ viele zufällig ziehe, dann sind etwa $\begin{eqnarray*} \frac {N-L+1} N K \end{eqnarray*}$ der Blöcke echt größer als $\begin{eqnarray*} L \end{eqnarray*}$ .

Damit könnte ich versuchen:

Ich habe $\begin{eqnarray*} N \end{eqnarray*}$ Blöcke und ziehe jeden Tag $\begin{eqnarray*} K \end{eqnarray*}$ Blöcke ohne zurücklegen.

D.h. am ersten Tag habe ich K disjunkte Blöcke gezogen/geändert. OBdA es sind (nach Umnummerierung) die Blöcke $\begin{eqnarray*} \{ 1, \ldots, K\} \end{eqnarray*}$ . Jetzt ziehe ich wieder und etwa $\begin{eqnarray*} \frac {N-L+1} N K \end{eqnarray*}$ der Blöcke der größer als $\begin{eqnarray*} K \end{eqnarray*}$ .

D.h. ich erwarte am Tag 2 insgesamt $\begin{eqnarray*} K + \frac {N-K+1} N K \end{eqnarray*}$ Blöcke zu haben.

Das Muster fortgesetzt: Habe ich an Tag $\begin{eqnarray*} n \end{eqnarray*}$ dann $\begin{eqnarray*} K_n \end{eqnarray*}$ Blöcke, ewarte ich etwa $\begin{eqnarray*} K_n + \frac {N-K_n+1} N K \end{eqnarray*}$ Blöcke am nächsten Tag. Natürlich nur solange $\begin{eqnarray*} n, K \end{eqnarray*}$ relativ klein und $\begin{eqnarray*} N \end{eqnarray*}$ relativ groß ist.

Was ist eure Einschätzung zu der Approximation? smile

13.06.2024, 22:07

HAL 9000

Auf diesen Beitrag antworten »

Eigentlich nicht so schwer:

Wir haben insgesamt $\begin{eqnarray*} N \end{eqnarray*}$ Blöcke, von denen an $\begin{eqnarray*} n \end{eqnarray*}$ Tagen jeweils genau $\begin{eqnarray*} K \end{eqnarray*}$ Blöcke zufällig ausgewählt werden. Nun kennzeichne $\begin{eqnarray*} X_i \end{eqnarray*}$ die Indikatorvariable, dass Block $\begin{eqnarray*} i \end{eqnarray*}$ an mindestens einem Tag ausgewählt wurde. Dann gilt

$\begin{eqnarray*} E(X_i) = P(X_i=1) = 1-P(X_i=0) = 1-\left(1-\frac{K}{N}\right)^n \end{eqnarray*}$

Für die Gesamtzahl $\begin{eqnarray*} Y=\sum_{i=1}^N X_i \end{eqnarray*}$ an geänderten Blöcken gilt entsprechend

$\begin{eqnarray*} E(Y) = N\left(1-\left(1-\frac{K}{N}\right)^n\right) \end{eqnarray*}$ .

$\begin{eqnarray*} N=2000000,K=2000,n=7 \end{eqnarray*}$ ergibt ca. $\begin{eqnarray*} E(Y) \approx 13958 \end{eqnarray*}$ . Die $\begin{eqnarray*} X_i \end{eqnarray*}$ sind nicht unabhängig, aber das ist beim Erwartungswert der Summe egal.

Auch die Varianz $\begin{eqnarray*} V(Y) \end{eqnarray*}$ kann man mit dieser Methode noch ganz gut berechnen.

13.06.2024, 22:54

IfindU

Auf diesen Beitrag antworten »

Sehr elegant, vielen dank dir HAL! Freude

Dein Ansatz ermöglicht (im Gegensatz zu meinem) es auch sehr leicht auf andere Verteilungen als Gleichverteilung anzuwenden. Der Erwartungswert ist dann etwas komplizierter, aber bei den Dichten an die ich denke (z.B. 10% der Blöcke werden 3x mal so häufig modifizert wie die weiteren 90%, wie es je nach Anwendung durchaus der Fall ist) kein echtes Problem. Danke!

13.06.2024, 23:21

HAL 9000

Auf diesen Beitrag antworten »

Zur Berechnung von $\begin{eqnarray*} V(Y) = E\left(Y^2\right) - \left(E\left(Y\right)\right)^2 \end{eqnarray*}$ : Für $\begin{eqnarray*} i\neq j \end{eqnarray*}$ gilt

$\begin{eqnarray*} E\left(X_iX_j\right) = P\left(X_i=1,X_j=1\right) = 1-P\left(X_i=0\right)-P\left(X_j=0\right)+P\left(X_i=0,X_j=0\right) = 1-2\left(1-\frac{K}{N}\right)^n + \left(1-\frac{K}{N-1}\right)^n\left(1-\frac{K}{N}\right)^n \end{eqnarray*}$

und damit dann

$\begin{eqnarray*} E(Y^2) = N(N-1) \left(1-2\left(1-\frac{K}{N}\right)^n + \left(1-\frac{K}{N-1}\right)^n\left(1-\frac{K}{N}\right)^n \right) +N\left(1-\left(1-\frac{K}{N}\right)^n\right) \end{eqnarray*}$

sowie etwas vereinfacht

$\begin{eqnarray*} \sigma^2 = V(Y) = N\left(1-\frac{K}{N}\right)^n \left[ 1 + (N-1)\left(1-\frac{K}{N-1}\right)^n - N\left(1-\frac{K}{N}\right)^n\right] \end{eqnarray*}$ .

Im Beispiel $\begin{eqnarray*} N=2000000,K=2000,n=7 \end{eqnarray*}$ oben ergibt das $\begin{eqnarray*} \sigma\approx 6.45 \end{eqnarray*}$ .

---------------------------------------------------------------------------------------------------------------

Es lässt sich sogar die exakte Verteilung von $\begin{eqnarray*} Y \end{eqnarray*}$ bestimmen, aber - man ahnt es schon - mit Siebformel:

$\begin{eqnarray*} P(Y=m) = \frac{\binom{N}{m}}{\binom{N}{K}^n}\cdot \sum_{i=0}^{m-K} (-1)^i \cdot \binom{m}{i}\cdot \binom{m-i}{K}^n \end{eqnarray*}$

Da stecken bereits bei $\begin{eqnarray*} N=2\,000\,000,K=2\,000,n=7 \end{eqnarray*}$ hübsch große Zahlen drin. Augenzwinkern

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:

13984 : 2.5131207707192088e-06
13983 : 6.231976273919987e-06
13982 : 1.4592330611450443e-05
13981 : 3.236327377226452e-05
13980 : 6.81732255724941e-05
13979 : 0.00013674011312865637
13978 : 0.0002617487566588366
13977 : 0.00047915733702712444
13976 : 0.0008404235649580518
13975 : 0.0014148144714057312
13974 : 0.00228969363983599
13973 : 0.003567588776362441
13972 : 0.0053590507169622974
13971 : 0.007770892555046146
13970 : 0.010890318994589266
13969 : 0.014766574705080089
13968 : 0.019392801284584607
13967 : 0.024691487645633857
13966 : 0.030506955640191565
13965 : 0.03660759769578925
13964 : 0.042699127152176136
13963 : 0.048448172161378714
13962 : 0.05351355098452334
13961 : 0.05758096929352457
13960 : 0.06039606129719383
13959 : 0.06179085692280468
13958 : 0.061699862604491305
13957 : 0.060163738291311754
13956 : 0.05732063635158223
13955 : 0.053387199611322274
13954 : 0.04863262785195843
13953 : 0.043349897514306526
13952 : 0.03782812300167139
13951 : 0.032329308652860586
13950 : 0.027071595963541435
13949 : 0.022219836693331146
13948 : 0.017883166586323666
13947 : 0.014118389876259395
13946 : 0.010937491670909122
13945 : 0.008317466642734856
13944 : 0.00621081726402819
13943 : 0.004555429045570804
13942 : 0.003282965772051459
13941 : 0.0023253539484940572
13940 : 0.0016192809058666888
13939 : 0.0011088846773084947
13938 : 0.0007469617296513308
13937 : 0.0004950751044035037
13936 : 0.00032293418283811664
13935 : 0.00020736391081458235
13934 : 0.0001311086524989851
13933 : 8.164098908578993e-05
13932 : 5.0079574987334254e-05
13931 : 3.0267908169310096e-05
13930 : 1.802871598560801e-05
13929 : 1.0585135813358868e-05
13928 : 6.127219974862367e-06
13927 : 3.4974352703165493e-06
13926 : 1.968958530057738e-06
13925 : 1.0934613345695758e-06

Gelistet sind nur jene $\begin{eqnarray*} m \end{eqnarray*}$ mit $\begin{eqnarray*} P(Y=m) \geq 10^{-6} \end{eqnarray*}$ .

14.06.2024, 14:20

IfindU

Auf diesen Beitrag antworten »

Verteilung also was man erwarten würde, da $\begin{eqnarray*} K = 2000 \ll 2000000 = N \end{eqnarray*}$ . Damit ist die Wahrscheinlichkeit dass man stehts verschiedene Blöcke wählt und nicht die "Handvoll" zuvor gezogenen, sehr groß und die meisten/wahrscheinlichsten Werte liegen nahe an das Maximum $\begin{eqnarray*} 14000 \end{eqnarray*}$ dran.

Noch einmal vielen Dank dir smile

14.06.2024, 15:06

HAL 9000

Auf diesen Beitrag antworten »

Die Anwendung der obigen Wkt-Formel kann die Numerik ganz schön ins Schwitzen bringen: Zum einen sprengen $\begin{eqnarray*} \binom{2\,000\,000}{2\,000} > 10^{6866} \end{eqnarray*}$ sowie weitere Binomialkoeffizienten den Zahlbereich von double. Zum anderen neigt die alternierende Summe im Siebformelterm sehr gern zu Auslöschungen, da man dort oft zwar betragsmäßig riesige Partialsummen, aber am Ende doch eine kleine Gesamtsumme hat.

Ich hab beides vermieden, indem ich solange wie möglich exakt mit den beliebig genauen Python-Integerzahlen gerechnet habe, und der in Floating-Point gewandelte Quotient dieser Zahlen war ja am Ende dann wieder im "normalen" Bereich. Augenzwinkern

Neue Frage »

Antworten »

Ziehen mit Zurücklegen mit großen Zahlen

Verwandte Themen