Universität Ulm
Abteilung Stochastik

A. Frey
J. Wiedmann
Stochastik f. Informatiker
Übungsblatt 6
25.11.1997

Abgabe: 02.12.97

____________________________________________________________________________________________
Aufgabe 1: (Kombinatorik)
Beim Hashing handelt es sich darum, Teilmengen eines Universums mit Hilfe geeigneter Tafeln (sog. Hashtafeln) abzuspeichern oder auch auf derartig gespeicherte Mengen zurückzugreifen. Bei “rein zufälligem” Ablegen von k Daten in einem Feld der Länge n können dabei Mehrfachbelegungen desselben Speicherplatzes vorkommen (Kollisionen) (k n).
i) 	Sei  das Ereignis : “Es tritt keine Kollision beim Ablegen von k Daten auf”.
Berechnen Sie die Wahrscheinlichkeit des Ereignisses 
ii) 	Sei p  (0,1). Bestimmen Sie ein (minimales)  mit : 
(6)

Aufgabe 2: (Kombinatorik, bed. Wahrscheinlichkeit)
Ein Universitätsdozent benötigt für ein Projekt noch Rechenergebnisse und schickt dazu 6 Jobs an den Großrechner des Rechenzentrums. Für die Fertigstellung des Projekts sind die Ergebnisse von 2 Jobs ausreichend. Da nach einigen Stunden noch keine Resultate vorliegen, fragt er beim zuständigen Operator nach mit dem Vorsatz, das Büro zu verlassen, wenn die Wahrscheinlichkeit, daß bis zum Abend mindestens zwei Ergebnisse vorliegen kleiner als 50% ist. Vom Operator erfährt er, daß von insgesamt 30 Jobs fünf zur Bearbeitung bereits ausgewählt wurden und bis zum Abend fertiggestellt sind. Wie soll der Dozent sich entscheiden, wenn der Operator
i) 	sich nicht erinnern kann, welche Jobs ausgewählt wurden,
ii) 	sicher ist, daß zumindest ein Job des Dozenten ausgewählt wurde,
(6)
i) 	sicher ist, daß zumindest der Job des Dozenten mit dem Namen J_1 ausgewählt wurde ?

Aufgabe 3: (Verteilungsfunktionen)
Man zeige für eine Zufallsvariable X mit zugehöriger Verteilung , Verteilungsfunktion F sowie a, b  :
i)	=F(b)-F(a)
ii)	F ist monoton nicht fallend
iii)	, wobei F(a-) den linksseitigen Grenzwert von F in a bezeichne
(6)

Aufgabe 4: (Zufallsvariable)
Es seien ={1,2,3,4,5,6}, A={1,3,5} und ={, A, , }. Auf  seien ferner folgende Abbildungen X und Y gegeben:

	1	2	3	4	5	6	
X()	0	1	0	1	0	1	
Y()	0	1	2	1	0	1	

Man überprüfe, ob X bzw. Y   - - Zufallsvariable sind ( bezeichnet die -Algebra der Borel´schen Mengen auf ).
(6)