Verteilung von Dingen auf Standorte mit begrenzter Kapazität

19.04.2016, 19:57

Pranke

Verteilung von Dingen auf Standorte mit begrenzter Kapazität

Meine Frage:
Hallo zusammen,
ich konnte bis jetzt leider nichts zu meinem Problem finden und hoffe ihr könnt mir helfen (bin nicht geübt in mathematischer Schreibweise, also bitte nett sein)!

Ich versuche mal meine Fragestellung zunächst mit einem Beispiel zu beschreiben, dessen Lösung ich schon kenne und das danach erweitert wird:

Y Unternehmen siedeln sich ohne weitere Restriktionen zufällig in X Städten an. Dabei ist ein Unternehmen immer nur in einer Stadt vertreten. Ich möchte wissen, in wie vielen Städten x sich überhaupt ein Unternehmen ansiedelt. Dafür nutzte ich folgende Formel, die auch schon mal bewiesen wurde:
x=(1-(1-(1/X)^Y)*X

Wenn beispielsweise 10 Städte betrachtet werden, in denen sich 8 Unternehmen ansiedeln wird erwartet, dass anschließend in 5,695... Städten ein oder mehrere Unternehmen gesiedelt haben. Über den Sinn des Beispiels brauch hier nicht gesprochen werden, aber sonst soweit so gut.

Jetzt zu meinem eigentlichen Problem: Die Anzahl an Unternehmen, die sich in einer Stadt ansiedeln können soll begrenzt werden. Also z.B. höchstens 2 Unternehmen pro Stadt. Durch so eine Restriktion ist die oben genannte Formel leider nicht mehr für genaue Lösungen nutzbar. Würden sich z.B. 18 Unternehmen auf die 10 Städte verteilen würde die Formel mir einen Wert von 8,499... ausgeben. Da aber höchstens 2 Unternehmen in einer Stadt Platz finden müssen diese 18 sich auf MINDESTENS 9 Städten verteilen.
Kann mir jemand eine allgemeingültige Formel für dieses Problem zeigen?

Vielen Dank schonmal,
Pranke

Meine Ideen:
s.O.

21.04.2016, 17:30

Pranke

Auf diesen Beitrag antworten »

Niemand eine Idee unglücklich

22.04.2016, 13:08

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Pranke
Y Unternehmen siedeln sich ohne weitere Restriktionen zufällig in X Städten an. Dabei ist ein Unternehmen immer nur in einer Stadt vertreten. Ich möchte wissen, in wie vielen Städten x sich überhaupt ein Unternehmen ansiedelt. Dafür nutzte ich folgende Formel, die auch schon mal bewiesen wurde:
x=(1-(1-(1/X)^Y)*X

Da ist eine öffnende Klammer zuviel, richtig ist (1-(1-1/X)^Y)*X, d.h. $\begin{align*} \left(1 - \left(1-\frac{1}{X}\right)^Y\right)\cdot X \end{align*}$ .

Es sollte betont werden, dass diese Formel die mittlere zu erwartende Stadtanzahl mit Unternehmen angibt, d.h., den Erwartungswert der entsprechenden Zufallsgröße.

Zitat:

Original von Pranke
Die Anzahl an Unternehmen, die sich in einer Stadt ansiedeln können soll begrenzt werden. Also z.B. höchstens 2 Unternehmen pro Stadt.

Damit ergibt sich ein Problem: Wie soll diese Begrenzung als Wahrscheinlichkeitsverteilung modelliert werden?

Ohne Begrenzung ist das klar: Jedes der $\begin{align*} Y \end{align*}$ Unternehmen siedelt mit gleicher Wahrscheinlichkeit $\begin{align*} \frac{1}{X} \end{align*}$ in jeder der Städte an, und das unabhängig voneinander.

Dieses Modell - insbesondere die Unabhängigkeit - ist nun nicht mehr haltbar und muss durch was anderes ersetzt werden. Die bloße Nennung der Einschränkung "maximal zwei Unternehmen pro Stadt" ist da nicht genug - z.B. folgendes Ersatzmodell: Es wird eine Stadt ausgewürfelt wie im ersten Modell. Ist dort höchstens ein Unternehmen bis dahin ansässig, so wird diese Stadt genommen, andernfalls wird die zufällige Stadtauswahl wiederholt - solange, bis es irgendwann klappt. Äquivalent dazu wäre folgendes Vorgehen: Man beschränkt sich von vornherein auf die Städte mit (bisher) höchstens einem ansässigen Unternehmen und würfelt unter diesen gleichverteilt aus.

Dieses Modell ist um Längen schwerer als das erste. Ich bin dran und meld mich wieder.

EDIT: Man könnte es so angehen:

Sei $\begin{align*} p_{X,Y}(k) \end{align*}$ die Wahrscheinlichkeit, dass nach der Ansiedelung von $\begin{align*} Y \end{align*}$ Unternehmen an $\begin{align*} X \end{align*}$ Städten nach Methode 2 genau $\begin{align*} k \end{align*}$ Städte bereits mindestens ein Unternehmen haben. Offenbar macht das nach den Restriktionen nur für $\begin{align*} 1\leq Y\leq 2X \end{align*}$ Sinn, und dort dann nur für $\begin{align*} \left\lceil \frac{Y}{2}\right\rceil \leq k\leq \min(Y,X) \end{align*}$ .

Klar ist dann: Genau $\begin{align*} k \end{align*}$ Städte bedeutet $\begin{align*} Y-k \end{align*}$ Städte mit genau zwei sowie $\begin{align*} 2k-Y \end{align*}$ Städte mit genau einem, sowie $\begin{align*} X-k \end{align*}$ Städte mit noch keinem ansässigen Unternehmen.

Diese Situation kann auf zwei mögliche Arten entstanden sein:

a) Das letzte Unternehmen Nr. $\begin{align*} Y \end{align*}$ ist in einer "neuen" Stadt angekommen. Vorher gab es also $\begin{align*} Y-k \end{align*}$ Städte mit genau zwei, $\begin{align*} 2k-Y-1 \end{align*}$ Städte mit genau einem und $\begin{align*} X-k+1 \end{align*}$ Städte mit keinem Unternehmen. Die Wahrscheinlichkeit dieses Pfades ist also $\begin{align*} \frac{X-k+1}{k+X-Y}\cdot p_{X,Y-1}(k-1) \end{align*}$ .

b) Das letzte Unternehmen Nr. $\begin{align*} Y \end{align*}$ ist in einer Stadt angekommen, wo bereits eine Firma war. Vorher gab es also $\begin{align*} Y-k-1 \end{align*}$ Städte mit genau zwei, $\begin{align*} 2k-Y+1 \end{align*}$ Städte mit genau einem und $\begin{align*} X-k \end{align*}$ Städte mit keinem Unternehmen. Die Wahrscheinlichkeit dieses Pfades ist demnach $\begin{align*} \frac{2k-Y+1}{k+X-Y+1}\cdot p_{X,Y-1}(k) \end{align*}$ .

Es gilt somit die Rekursionsformel

$\begin{align*} p_{X,Y}(k) = \frac{X-k+1}{k+X-Y}\cdot p_{X,Y-1}(k-1) + \frac{2k-Y+1}{k+X-Y+1}\cdot p_{X,Y-1}(k) \end{align*}$ für $\begin{align*} Y\geq 1 \end{align*}$ und $\begin{align*} \left\lceil \frac{Y}{2}\right\rceil \leq k\leq \min(Y,X) \end{align*}$ . (*)

mit den Startwerten $\begin{align*} p_{X,0}(0)=1,p_{X,0}(k)=0 \end{align*}$ für $\begin{align*} k\geq 1 \end{align*}$ sowie $\begin{align*} p_{X,Y}(k)=0 \end{align*}$ für $\begin{align*} Y\geq 1 \end{align*}$ sowie $\begin{align*} 0\leq k<\left\lceil \frac{Y}{2}\right\rceil \end{align*}$ .

Und $\begin{align*} E_{X,Y} = \sum_{k=1}^{X} k\cdot p_{X,Y}(k) \end{align*}$ ist der gesuchte Erwartungswert der Stadtanzahl mit mindestens einem Unternehmen.

So ist z.B. $\begin{align*} E_{10,8} = \frac{3\,289\,595\,409\,881}{551\,124\,000\,000} \approx 5.969 \end{align*}$ sowie $\begin{align*} E_{10,18} = \frac{281\,235\,270\,341\,654\,731\,824\,271}{28\,810\,829\,817\,907\,200\,000\,000} \approx 9.761 \end{align*}$ , nur um mal auf deine Beispiele einzugehen. Die Formeln liefern dann auch brav $\begin{align*} E_{10,19} = 1 \end{align*}$ , was ja auch ansonsten inhaltlich klar ist.

Ob es eine kurze "griffige" explizite Formel für diesen Erwartungswert gibt, kann ich jetzt nicht sagen. Der Kompliziertheit des Bruchs von eben wegen würde ich das eher nicht annehmen.

25.04.2016, 23:18

Pranke

Auf diesen Beitrag antworten »

Vielen Dank für deine Mühen!

Neue Frage »

Antworten »

Verteilung von Dingen auf Standorte mit begrenzter Kapazität

Verwandte Themen