Wahrscheinlichkeit, dass zwei Eckpunkte durch einen Pfad in einem zufällig gerichteten Graphen verbunden sind

Definieren Sie als zufällig gerichteten Graphen ( Eckpunkte; wir setzen mit der Wahrscheinlichkeit Kante zwischen zwei Eckpunkte ). $G(n, p)$ $n$ $p$

Was sind die bekannten Ergebnisse für das folgende Problem:

Fixiere zwei Eckpunkte und . Wie groß ist die Wahrscheinlichkeit, dass zwischen und mindestens ein Pfad (höchstens ) vorhanden ist ? (Das Ergebnis sollte eindeutig eine Funktion von , und ) Die Obergrenze würde auch funktionieren, wenn keine genaue Antwort bekannt ist. $v$ $u$ $k$ $u$ $v$ $n$ $p$ $k$

graph-theory upper-bounds random-walks random-graphs Daniel
quelle

Welche Werte von

p

$p$ berücksichtigen Sie?

Igor Shinkar

@IgorShinkar macht es einen großen Unterschied? Ich habe keine bestimmte Nummer im Sinn; a nur eine Wahrscheinlichkeit

p \in (0, 1)

$p \in (0,1)$ .

Daniel

Haben Sie versucht, den Standardansatz von Erdos-Renyi zu ändern, und wenn ja, welche Schwierigkeiten gibt es?

Usul

Haben Sie darüber nachgedacht, die erwartete Anzahl von Pfaden zu berechnen ? Aufgrund der Linearität der Erwartungen sollte dies viel einfacher zu berechnen / zu schätzen sein. Es wäre auch ein guter Indikator für die Wahrscheinlichkeit, dass es einen Pfad gibt. dh Wenn die erwartete Anzahl von Pfaden 0,01 beträgt, gibt es mit einer Wahrscheinlichkeit von mindestens 99% keinen Pfad. Und wenn die erwartete Anzahl von Pfaden 100 beträgt, würde ich vermuten, dass es einen Pfad mit hoher Wahrscheinlichkeit gibt.

Thomas

Guter Vorschlag Thomas. Nur um sicherzugehen, dass ich Ihre Idee verstehe: Geben Sie die Anzahl der Pfade der Länge

mit

. Die erwartete Anzahl von der Länge

ist (richtig?). Definieren Sie "X_i = (Y_i> 0)", das das Ereignis eines Pfads der Größe zwischen zwei Eckpunkten (Vorhandensein eines Pfads) anzeigt . Ich weiß, dass , das durch . Dies würde eine Obergrenze von für .

i

$i$

Y_{i}

$Y_i$

i

$i$

E [Y_{i}] = (\binom{n - 2}{i - 1}) (i - 1)! p^{i}

$E[Y_i] = { n-2 \choose i-1} (i-1)! p^i$

i (i > 0)

$i (i > 0)$

P (X_{i}) = P (Y_{i} > 0) = \sum_{j = 1}^{\infty} P (Y_{i} = j)

$P(X_i) = P(Y_i > 0) = \sum_{j=1}^{\infty} P(Y_i = j)$

E [Y_{i}] = \sum_{j = 0}^{\infty} j . P (Y_{i} = j)

$E[Y_i] = \sum_{j=0}^{\infty} j. P(Y_i = j)$

\sum_{i = 1}^{k} E [Y_{i}]

$\sum_{i=1}^{k}E[Y_i]$

P (\lor_{i = 1}^{k} X_{i} = 1) = P (\lor_{i = 1}^{k} Y_{i} > 0)

$P( \vee_{i=1}^k X_i =1 ) = P( \vee_{i=1}^k Y_i >0)$

Daniel

Antworten:

Stellen Sie sich einen BFS-Explorationsprozess vor, der in Stufen abläuft . Setzen Sie . Untersuchen Sie bei alle Kanten von bis (wobei die Menge aller Eckpunkte ist) und setzen Sie , dass sie aus allen bestehen auf diese Weise erreichte Eckpunkte; Ihre Anzahl hat eine Binomialverteilung, die leicht berechnet werden kann. Überprüfen Sie nach Schritten, ob der Scheitelpunkt zu . $k$ $V_0 = \{u\}$ $V_0,\ldots,V_i$ $V_i$ $V \setminus \bigcup_{j=0}^i V_j$ $V$ $V_{i+1}$ $k$ $v$ $\bigcup_{j=0}^k V_j$

Beachten Sie, dass dieser Vorgang sowohl im ungerichteten als auch im gerichteten Fall genau gleich ist. Daher ist die Antwort, was auch immer es ist, für beide Modelle identisch. Vermutlich ist im ungerichteten Fall die Antwort bekannt und kann nachgeschlagen werden. Andernfalls können Sie versuchen, es zu schätzen, indem Sie die Größen schätzen und so die Wahrscheinlichkeitdass zu . $|V_i|$ $\frac{1}{n-1} \sum_{i=1}^k |V_i|$ $v$ $\bigcup_{i=1}^k V_i$

Yuval Filmus
quelle

Warum das Downvote?

Yuval Filmus

dies würde eine Wahrscheinlichkeit eines Weges mit einer Länge von genau k ergeben, nicht höchstens k; Ist das korrekt?

Daniel

Wie es geschrieben steht, ist es für die "höchstens" Variante.

Yuval Filmus