Verteilungsfunktion < Stochastik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 16:34 Mi 09.03.2005 | | Autor: | iftpr |
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Ich betrachte einen gerichteten Graphen ohne Zyklen (gerichtete Kreise) und ohne Mehrfachkanten. Dieser Graph hat höchstens n * (n-1) * 1/2 Kanten, die Zahl der Kanten ist ein Parameter. Betrachtet werden prinzipiell Wege vom Startknoten zum Zielknoten. Die Knoten sind topologisch geordnet (Kanten verlaufen immer "von vorne nach hinten").
Hier brauche ich Hilfe:
Ich suche eine Verteilungsfunktion für die Frage "Mit welcher Wahrscheinlichkeit gibt es einen Weg vom Startknoten zum Zielknoten mit einer Länge von weniger als k Kanten"
Als Parameter der Verteilung gehen die "Anzahl der Knoten" und die "Anzahl der Kanten" ein.
Eigene Gedanken:
:: Ich gehe davon aus (hoffe), dass es eine der Verteilungen ist, wie man sie in jedem Stochastik-Skript findet (das Problem ist einfach zu gut strukturiert um eine außergewöhnliche Verteilung zu haben) - ich habe aber noch keine passende gefunden...
:: Die Verteilung ist linksschief - ein Weg der Länge 1 ist wahrscheinlicher als ein Weg der Länge n-1, obwohl es im vollständigen Graphen jeweils genau einen davon gibt. Die Normalverteilung scheidet also aus. (Ich glaube, dass die Normalverteilung vorläge wenn es sich nicht um einen zyklenfreien Graphen handeln würde. )
:: Die beiden Parameter "Anzahl Knoten, Kanten" können evtl. zu eine Parameter "Anteil Kanten" zusammengefaßt werden.
zur Erklärung : Wozu benötige ich die Verteilung:
Ich benötige zumindest den "Erwartungswert für die Anzahl der Kanten wenn ich einen Start-Ziel-Weg zufällig wähle". Diesen verwende ich, um Ressourcen auf die Kanten und Ressourcenfenster auf die Knoten zu verteilen. Wenn ein Weg innerhalb der Ressourcenfenster bleibt ist er "gültig". Mit der Verteilung versuche ich , Graphen mit einem vorgegebenen Anteil gültiger Wege zu generieren.
Bereits jetzt vielen Dank für Eure Gedanken dazu
P.S.: Das Problem stellt sich mir im Rahmen einer wissenschaftlichen Arbeit - als "nice to know". Das eigentliche Thema hat mit Stochastik auch nicht in Ansätzen zu tun. Die Lösung dieses Problems beeinträchtigt nicht die Note meiner Arbeit.
|
|
| |
|
Hallo Till!
![[willkommenmr]](/images/smileys/willkommenmr.png "[willkommenmr]")
> Ich betrachte einen gerichteten Graphen ohne Zyklen
> (gerichtete Kreise) und ohne Mehrfachkanten. Dieser Graph
> hat höchstens n * (n-1) * 1/2 Kanten, die Zahl der Kanten
> ist ein Parameter. Betrachtet werden prinzipiell Wege vom
> Startknoten zum Zielknoten. Die Knoten sind topologisch
> geordnet (Kanten verlaufen immer "von vorne nach
> hinten").
Nur dass ich es richtig verstehe: Die Anzahl der Kanten ist nicht zufällig. Aber die Lage der Kanten ist zufällig. Die Ergebnismenge hat somit
[mm]{\frac{n(n-1)}{2}\choose m}[/mm]
Elemente, wobei m die vorgegebene Anzahl an Kanten ist. Außerdem ist jedes dieser Ergebnisse gleichwahrscheinlich (Laplace-Annahme). Stimmt das so weit?
> Hier brauche ich Hilfe:
> Ich suche eine Verteilungsfunktion für die Frage "Mit
> welcher Wahrscheinlichkeit gibt es einen Weg vom
> Startknoten zum Zielknoten mit einer Länge von weniger als
> k Kanten"
> Als Parameter der Verteilung gehen die "Anzahl der Knoten"
> und die "Anzahl der Kanten" ein.
Die Zufallsvariable (nennen wir sie X) ist also die kürzeste Anzahl an Kanten auf dem Weg vom Start zum Ziel. (In einem vollständigen Graphen gibt es ja mehrere Wege, interessant ist aber wohl nur der kürzeste.)
> Eigene Gedanken:
> :: Ich gehe davon aus (hoffe), dass es eine der
> Verteilungen ist, wie man sie in jedem Stochastik-Skript
> findet (das Problem ist einfach zu gut strukturiert um eine
> außergewöhnliche Verteilung zu haben) - ich habe aber noch
> keine passende gefunden...
> :: Die Verteilung ist linksschief - ein Weg der Länge 1 ist
> wahrscheinlicher als ein Weg der Länge n-1, obwohl es im
> vollständigen Graphen jeweils genau einen davon gibt. Die
> Normalverteilung scheidet also aus. (Ich glaube, dass die
> Normalverteilung vorläge wenn es sich nicht um einen
> zyklenfreien Graphen handeln würde. )
Ich denke, die Normalverteilung scheidet aus, da das eine stetige Verteilung ist, die betrachtete Zufallsvariable aber nur endlich viele verschiedene Werte annehmen kann: alle natürlichen Zahlen zwischen 1 und n-1 sowie 0, falls es überhaupt keinen Weg zwischen Start und Ziel gibt (das kann ja auch passieren). Oder nimmt X in diesem Fall den Wert [mm] $\infty$ [/mm] an? Das wäre aber merkwürdig, denn dann bekommst Du in jedem Fall [mm] $E(X)=\infty$ [/mm] als Ergebnis. Vielleicht verstehe ich aber auch noch etwas Grundlegendes falsch und dieser Fall kann gar nicht eintreten ![[verwirrt]](/images/smileys/verwirrt.gif "[verwirrt]")
> :: Die beiden Parameter "Anzahl Knoten, Kanten" können
> evtl. zu eine Parameter "Anteil Kanten" zusammengefaßt
> werden.
>
> zur Erklärung : Wozu benötige ich die Verteilung:
> Ich benötige zumindest den "Erwartungswert für die Anzahl
> der Kanten wenn ich einen Start-Ziel-Weg zufällig wähle".
> Diesen verwende ich, um Ressourcen auf die Kanten und
> Ressourcenfenster auf die Knoten zu verteilen. Wenn ein
> Weg innerhalb der Ressourcenfenster bleibt ist er "gültig".
> Mit der Verteilung versuche ich , Graphen mit einem
> vorgegebenen Anteil gültiger Wege zu generieren.
Das sagt mir leider nicht so viel. Aber vielleicht versteht ja jemand anderes, was Du genau meinst.
Ich habe mal folgendes Beispiel betrachtet: n=4 Knoten und m=3 Kanten. Damit gibt es 6 Kandidaten für Kanten, und wir suchen aus der Menge dieser Kandidaten genau 3 heraus. Die Ergebnismenge enthält somit [mm] ${6\choose 3}=20$ [/mm] Elemente. Ein Ergebnis wäre z.B. [mm] $\omega=\{(1,4),(1,2),(1,3)\}$.
[/mm]
Wenn nun die Kante (1,4) in der Menge der gewählten Kanten (also in [mm] $\omega$) [/mm] enthalten ist, kommen wir mit einer Kante direkt vom Start zum Ziel. Da die restlichen Kanten frei gewählt werden dürfen, gibt es dafür [mm] ${5\choose 2}=10$ [/mm] Möglichkeiten. Die zugehörige Wkt. beträgt also P(X=1)=1/2.
2 Kanten benötigt man, falls die Kombination [mm] $\{(1,2),(2,4)\}$ [/mm] oder [mm] $\{(1,3),(3,4)\}$ [/mm] dabei ist, aber nicht (1,4). Dafür gibt es 6 Möglichkeiten. Daraus folgt $P(X=2)=3/10$.
Genau 3 Kanten gibt es im Fall [mm] $\omega=\{(1,2),(1,3),(1,4)\}$, [/mm] also $P(X=3)=1/20$.
Und der oben erwähnte Fall, dass man das Ziel nicht erreicht, ergibt sich in 3 der 20 Fällen, also 15%.
Ich habe beim Rechnen des Beispiels nicht das Gefühl gehabt, dass ein leicht zu durchschauendes System hinter den Zahlen steckt, aber das mag daran liegen, dass ich noch nicht den rechten Überblick besitze. Ich bin aber sehr skeptisch, dass dahinter eine bekannte Verteilung steckt.
Hoffentlich konnte ich Dir mit meinen Gedanken schon ein wenig helfen. Ich stelle die Frage auf jeden Fall auf "teilweise beantwortet". Vielleicht meldet sich ja noch jemand.
Viele Grüße
Brigitte
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 01:52 Sa 12.03.2005 | | Autor: | iftpr |
Hallo Brigitte!
Zunächsteinmal danke, dass du dir die Mühe gemacht hast, dich mit meinem Problem zu beschäftigen!
> Nur dass ich es richtig verstehe: Die Anzahl der Kanten ist
> nicht zufällig. Aber die Lage der Kanten ist zufällig. Die
> Ergebnismenge hat somit
>
> [mm]{\frac{n(n-1)}{2}\choose m}[/mm]
>
> Elemente, wobei m die vorgegebene Anzahl an Kanten ist.
> Außerdem ist jedes dieser Ergebnisse gleichwahrscheinlich
> (Laplace-Annahme). Stimmt das so weit?
Ja, stimmt genau.
> Die Zufallsvariable (nennen wir sie X) ist also die
> kürzeste Anzahl an Kanten auf dem Weg vom Start zum Ziel.
> (In einem vollständigen Graphen gibt es ja mehrere Wege,
> interessant ist aber wohl nur der kürzeste.)
Ja. Mich interessiert P(X <= k) , also die Wkt. ,dass (mindestens) ein Weg mit höchstens k Kanten existiert.
Das ist in der Tat nichts anderes, als dass der kürzeste Weg weniger als k Kanten hat.
> Ich denke, die Normalverteilung scheidet aus, da das eine
> stetige Verteilung ist, die betrachtete Zufallsvariable
> aber nur endlich viele verschiedene Werte annehmen kann:
Ja. (aber kann ich eine diskrete Verteilung nicht durch eine stetige Verteilung annähern[?]
Die Summe von 1000 Würfeln nähert sich doch auch der Normalverteilung an... )
> alle natürlichen Zahlen zwischen 1 und n-1 sowie 0, falls
> es überhaupt keinen Weg zwischen Start und Ziel gibt (das
> kann ja auch passieren). Oder nimmt X in diesem Fall den
> Wert [mm]\infty[/mm] an? Das wäre aber merkwürdig, denn dann
> bekommst Du in jedem Fall [mm]E(X)=\infty[/mm] als Ergebnis.
> Vielleicht verstehe ich aber auch noch etwas Grundlegendes
> falsch und dieser Fall kann gar nicht eintreten
>
Den Fall mit [mm]\infty[/mm] kann man vermeiden wenn man bei "kein Weg" Y = n setzt. 
> Ich habe mal folgendes Beispiel betrachtet: n=4 Knoten und
> m=3 Kanten.
Dieses Beispiel hatte ich auch betrachtet. Allerdings zusätzlich für alle möglichen AnzahlenKantenInGraphen. Hier fällt auf, dass für die Wkten, dass es (mindestens) einen Weg mit 1 (bzw. 2, 3) Kanten in Abhängigkeit der AnzahlKantenInGraph gibt, "schöne" Funktionsverläufe herauskommen. Geht man aber den nächsten Schritt und betrachtet die Wkt wie oben beschrieben, so ergibt sich leider nichts schönes mehr - schließlich lassen sich die Wkten nicht einfach addieren, da sie nicht unabhängig sind.
> Ich habe beim Rechnen des Beispiels nicht das Gefühl
> gehabt, dass ein leicht zu durchschauendes System hinter
> den Zahlen steckt, aber das mag daran liegen, dass ich noch
> nicht den rechten Überblick besitze. Ich bin aber sehr
> skeptisch, dass dahinter eine bekannte Verteilung steckt.
Hmm....
Mittlerweile glaube ich auch nicht mehr an eine "schöne" Verteilung - zumindest keine, die man sich über das Rechnen von Beispielen herleiten kann. Aber auch das ist ein Ergebnis.
Grüße
Till
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 08:54 Sa 12.03.2005 | | Autor: | Brigitte |
Hallo Till!
> > Ich denke, die Normalverteilung scheidet aus, da das eine
>
> > stetige Verteilung ist, die betrachtete Zufallsvariable
>
> > aber nur endlich viele verschiedene Werte annehmen kann:
>
>
> Ja. (aber kann ich eine diskrete Verteilung nicht durch
> eine stetige Verteilung annähern[?]
> Die Summe von 1000 Würfeln nähert sich doch auch der
> Normalverteilung an... )
Richtig. Aber das geht nur unter bestimmten Voraussetzungen, insbesondere für lange Summen von Zufallsvariablen (wie Dein Beispiel), und ich sehe nicht, dass X sich als Summe von anderen Zufallsvariablen darstellen lässt.
> > alle natürlichen Zahlen zwischen 1 und n-1 sowie 0, falls
>
> > es überhaupt keinen Weg zwischen Start und Ziel gibt (das
>
> > kann ja auch passieren). Oder nimmt X in diesem Fall den
>
> > Wert [mm]\infty[/mm] an? Das wäre aber merkwürdig, denn dann
> > bekommst Du in jedem Fall [mm]E(X)=\infty[/mm] als Ergebnis.
> > Vielleicht verstehe ich aber auch noch etwas
> Grundlegendes
> > falsch und dieser Fall kann gar nicht eintreten
> >
>
> Den Fall mit [mm]\infty[/mm] kann man vermeiden wenn man bei "kein
> Weg" Y = n setzt.
OK.
> > Ich habe mal folgendes Beispiel betrachtet: n=4 Knoten
> und
> > m=3 Kanten.
>
> Dieses Beispiel hatte ich auch betrachtet. Allerdings
> zusätzlich für alle möglichen AnzahlenKantenInGraphen. Hier
> fällt auf, dass für die Wkten, dass es (mindestens) einen
> Weg mit 1 (bzw. 2, 3) Kanten in Abhängigkeit der
> AnzahlKantenInGraph gibt, "schöne" Funktionsverläufe
> herauskommen. Geht man aber den nächsten Schritt und
> betrachtet die Wkt wie oben beschrieben, so ergibt sich
> leider nichts schönes mehr - schließlich lassen sich die
> Wkten nicht einfach addieren, da sie nicht unabhängig
> sind.
Das verstehe ich nicht. Du meinst wohl, da sie nicht disjunkt sind. Aber selbst das ist mir unklar. Die Ereignisse X=1,X=2,X=3,X=4 sind paarweise disjunkt, die zugehörigen Wkt. darf man addieren. Bei dem Beispiel, das ich aufgeschrieben hatte, kommst Du ganz bestimmt auf [mm] $P(X\le [/mm] k)$, eben für das gewählte m=3. Oder möchtest Du die Ergebnisse für verschiedene m noch kombinieren?
Ich denke, dass man für Spezialfälle, z.B. [mm] $P(X\le [/mm] 1)$ für bel. m und n eine Formel aufstellen kann, aber wohl schwerlich für [mm] $P(X\le [/mm] k)$. Aber wer weiß, vielleicht findet ja hier jemand noch was...
Viele Grüße
Brigitte
|
|
|
|
