Wahrscheinlicheit, dass 2 Vektoren aus {0,1}^2n an derselben Stelle eine 1 haben

27.06.2012, 19:45

MinnieS

Wahrscheinlicheit, dass 2 Vektoren aus {0,1}^2n an derselben Stelle eine 1 haben

Meine Frage:
Wie hoch ist die Wahrscheinlichkeit dass zwei Vektoren x, y aus {0,1}^(2n), die genau k Einsen haben, an derselben Stelle eine 1 haben?

Es geht darum die Ws zu berechnen, dafür dass das Produkt (x^T)*y=1 ist.

(T heißt transponiert).

Meine Ideen:
Es soll wohl was mit/weniger (1-k/n)^k rauskommen!

27.06.2012, 19:50

HAL 9000

Auf diesen Beitrag antworten »

RE: Wahrscheinlicheit, dass 2 Vektoren aus {0,1}^2n an derselben Stelle eine 1 haben

Zitat:

Original von MinnieS
Meine Frage:
Wie hoch ist die Wahrscheinlichkeit dass zwei Vektoren x, y aus {0,1}^(2n), die genau k Einsen haben, an derselben Stelle eine 1 haben?

Zitat:

Original von MinnieS
Es geht darum die Ws zu berechnen, dafür dass das Produkt (x^T)*y=1 ist.

Deine erste Bedingung oben würde ich aber so deuten, dass dann $\begin{eqnarray*} x^T\cdot y = k \end{eqnarray*}$ ist, zumindest wenn du das übliche Skalarprodukt

$\begin{eqnarray*} x^T\cdot y = x_1y_1 + \ldots + x_{2n}y_{2n} \end{eqnarray*}$

meinst.

Oder soll die erste Bedingung oben lauten, dass an genau einer (!) Stelle beide Vektoren jeweils eine 1 haben, an allen anderen Stellen jedoch nicht (d.h. dort nur 00, 01 oder 10).

27.06.2012, 20:00

MinnieS

Auf diesen Beitrag antworten »

RE: Wahrscheinlicheit, dass 2 Vektoren aus {0,1}^2n an derselben Stelle eine 1 haben
Man ist im Raum \mathbb Z_{2} also {0,1}^(2n)....das heißt x und y bestehen nur aus Nullen und Einsen und beim Produktentsteht auch nur eine 0 oder 1 da man immer modulo 2 rechnet also nichts mit k.

27.06.2012, 20:02

MinnieS

Auf diesen Beitrag antworten »

RE: Wahrscheinlicheit, dass 2 Vektoren aus {0,1}^2n an derselben Stelle eine 1 haben
Man ist im Raum $\begin{eqnarray*} \mathbb Z_{2} \end{eqnarray*}$ also {0,1}^(2n)....das heißt x und y bestehen nur aus Nullen und Einsen und beim Produktentsteht auch nur eine 0 oder 1 da man immer modulo 2 rechnet also nichts mit k.

27.06.2012, 20:03

MinnieS

Auf diesen Beitrag antworten »

RE: Wahrscheinlicheit, dass 2 Vektoren aus {0,1}^2n an derselben Stelle eine 1 haben
Man ist im Raum $\begin{eqnarray*} \mathbb Z_{2}^{2n} \end{eqnarray*}$ also {0,1}^(2n)....das heißt x und y bestehen nur aus Nullen und Einsen und beim Produktentsteht auch nur eine 0 oder 1 da man immer modulo 2 rechnet also nichts mit k.

27.06.2012, 20:10

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von MinnieS
Man ist im Raum $\begin{eqnarray*} \mathbb Z_{2} \end{eqnarray*}$ also {0,1}^(2n)....das heißt x und y bestehen nur aus Nullen und Einsen und beim Produktentsteht auch nur eine 0 oder 1 da man immer modulo 2 rechnet also nichts mit k.

Aha, das musst du aber gleich am Anfang dazusagen - man kann schließlich auch als Ausgangsraum $\begin{eqnarray*} \{0,1\}^{2n} \end{eqnarray*}$ betrachten und trotzdem das Skalarprodukt mit Werten in $\begin{eqnarray*} \mathbb{R} \end{eqnarray*}$ rechnen!

Aber in diesem Kontext heißt doch jetzt die Bedingung $\begin{eqnarray*} x^T\cdot y=1 \end{eqnarray*}$ auch wieder was anderes, nämlich dass die Anzahl der Stelle mit gemeinsamen 1 ungerade ist, nicht wahr? verwirrt

28.06.2012, 19:26

MinnieS

Auf diesen Beitrag antworten »

Ja,schon, aber lass uns mal zuerst die WS berechnen, dass x und y nur EINE Eins gemeinsam haben,also eine Eins an ein und derselben Stelle. Das wäre ausch schon mal gut.

28.06.2012, 19:42

DaymMayne

Auf diesen Beitrag antworten »

Hallo,

abstrahiere doch mal so:

$\begin{eqnarray*} \begin{pmatrix} x_1 \\ x_2 \\ x_3 \end{pmatrix} \cdot \begin{pmatrix} y_1 \\ y_2 \\ y_3 \end{pmatrix} \end{eqnarray*}$

Was sind nun alle möglichen Vektoren zunächst?

Definiere als Ereignisraum Vektoren von Tupeln:

$\begin{eqnarray*} \begin{pmatrix} (x_1, y_1) \\ (x_2, y_2) \\ (x_3, y_3) \end{pmatrix} \end{eqnarray*}$

Nun, wie groß ist dein Ereignisraum? Für einen Komponente hast du 4 Möglichkeiten der Wahl:

$\begin{eqnarray*} (0,0), (0,1), (1,0), (1,1) \end{eqnarray*}$

Insgesamt ist dein Ereignisraum also später, wenn du mit n-Komponenten arbeitest $\begin{eqnarray*} 4^n \end{eqnarray*}$

Jetzt fixxierst du o.B.d.A eine Komponente. Du forderst, dass beide hier 1 sind. Das bedeutet du musst aus deinem Ereignisraum $\begin{eqnarray*} 4^n \end{eqnarray*}$ durch 3 teilen, weil die Tupel (0,0), (0,1), (1,0) nicht sein sollen. Die anderen Komponenten bleiben variabel. Mach dir das an einem Entscheidungsbaum klar. Jetzt solltest du mit der Zahl $\begin{eqnarray*} 4^n / 3 \end{eqnarray*}$ aber durchstarten können.

28.06.2012, 19:52

DaymMayne

Auf diesen Beitrag antworten »

Ach sehe gerade, dass die Vektoeren nur eine EINS gemeinsame haben sollen.

Dann gilt für alle anderen Komponenten eben:

(0,0), (0,1), (1,0) du musst also den Fall (1,1) für die restlichen Komponenten rauskürzen.

Die guten Vektoren wären dann der Kardinalität: 3^{n-1}

Warum 3^{n-1} ?

Pro Komponente hast du 3 Wahlmöglihckeiten, du wählst n-1 komponenten.

Für eine Komponente hast du nur eine Wahlmöglichkeit, nämlich das Tupel (1,1).

Dein Ereignisraum hat Kardinalität 4^n

06.07.2012, 10:38

MinnieS

Auf diesen Beitrag antworten »

Nee, die Vektoren sollen 2 Einsen gemeinsam haben, sodass das Produkt gleich 1 ist.

Wie kommt man nun von deiner Überlegung auf $\begin{eqnarray*} \left(1-\frac{k}{n}\right)^{k} \end{eqnarray*}$

06.07.2012, 11:38

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von MinnieS
Wie kommt man nun von deiner Überlegung auf $\begin{eqnarray*} \left(1-\frac{k}{n}\right)^{k} \end{eqnarray*}$

Deine Gedankensprünge sind wirklich schwer nachvollziehbar: Wie kommst du denn nun wieder auf die Formel?

Rekapitulieren wir nochmal die Gesamtsituation, denn irgendwie irritieren mich deine ungenauen Formulierungen immer wieder:

Zitat:

Original von MinnieS
Wie hoch ist die Wahrscheinlichkeit dass zwei Vektoren x, y aus {0,1}^(2n), die genau k Einsen haben

Es geht also nicht um zwei beliebige Vektoren aus $\begin{eqnarray*} x,y\in \{0,1\}^{2n} \end{eqnarray*}$ , dann würde der Grundraum genau $\begin{eqnarray*} 2^{4n} \end{eqnarray*}$ Paare $\begin{eqnarray*} (x,y) \end{eqnarray*}$ enthalten.
Sondern es geht nur um solche $\begin{eqnarray*} x,y \end{eqnarray*}$ , die jeweils genau $\begin{eqnarray*} k \end{eqnarray*}$ Einsen in ihren Komponenten haben, das macht dann nur noch $\begin{eqnarray*} \binom{2n}{k}^2 \end{eqnarray*}$ Paare - soweit erstmal richtig?

Und für ein zufällig gewähltes Paar aus diesem Grundraum fragst du dich nun nach der Wahrscheinlichkeit, dass bei genau einer (!) Komponente sowohl in $\begin{eqnarray*} x \end{eqnarray*}$ als auch $\begin{eqnarray*} y \end{eqnarray*}$ eine 1 steht - auch richtig verstanden?

In dem Fall komme ich für $\begin{eqnarray*} 1\leq k\leq \frac{n+1}{2} \end{eqnarray*}$ auf die Wahrscheinlichkeit

$\begin{eqnarray*} p_k = \frac{\binom{k}{1}\cdot \binom{2n-k}{k-1}}{\binom{2n}{k}} \end{eqnarray*}$ ,

für alle anderen $\begin{eqnarray*} k \end{eqnarray*}$ auf Wahrscheinlichkeit Null.

06.07.2012, 14:27

MinnieS

Auf diesen Beitrag antworten »

$\begin{eqnarray*} \left(1-\frac{k}{n}\right)^{k} \end{eqnarray*}$
Das hatte ich schon ganz oben bei meiner Fragestellung geschrieben und es ging schon die ganze Zeit nur um die, die k Einsen haben. Steht alles ganz genau so in meiner obigen Fragestellung. Da gibt es nichts falsch zu verstehen.

$\begin{eqnarray*} \binom{2n}{k}^2 \end{eqnarray*}$ Paare ist richtig!
Genau, dass bei genau einer Komponente eine 1 steht. Und es soll bei x und y genau dieselbe Stelle sein!

06.07.2012, 14:34

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von MinnieS
Steht alles ganz genau so in meiner obigen Fragestellung. Da gibt es nichts falsch zu verstehen.

Offenbar doch, zumindest sprach DaymMayne von einem Ereignisraum mit 4^n Elementen - und du hast nicht widersprochen. Augenzwinkern

Neue Frage »

Antworten »

Wahrscheinlicheit, dass 2 Vektoren aus {0,1}^2n an derselben Stelle eine 1 haben

Verwandte Themen