Laden...

Große Zahl in viele zufällige Summanden aufteilen

Erstellt von Moschn vor 13 Jahren Letzter Beitrag vor 13 Jahren 4.302 Views
Hinweis von herbivore vor 13 Jahren

Abgeteilt von Zahl in drei zufällige Summanden aufteilen

Bitte beachtet bei einer Antwort, dass eine Lösung nicht ganz so einfach ist, wie es auf den ersten Augenblick aussieht, zumindest dann, wenn die Ergebnisse gleichverteilt seinen sollen. In dem verlinkten Thread wurde darüber, was für eine Gleichverteilung zu beachten ist und welche Arten von Gleichverteilung es gibt, ausführlich diskutiert. Bitte lest vor einer Antwort daher bitte den verlinkten Thread.

M
Moschn Themenstarter:in
16 Beiträge seit 2009
vor 13 Jahren

Hi all

Tut mir erstmal leid, dass ich den Thread wieder ausgrabe, aber in meinem Problem geht es um ähnliches:

Ich muss von einer relativ grossen Zahl (bsp: 1*10^6) viele zufällige Summanden bilden (bsp: 200 Summanden). Nun machen die hohe Anzahl von Summanden die Möglichkeit zunichte, zuerst alle Möglichkeiten auszurechnen und dann eine zufällige davon zu nehmen - der Rechenaufwand wäre enorm.

Der andere Ansatz von Gaussmath, funktioniert auch nicht, weil nach ca. 15 summanden ist die Summe erreicht, und alle weiteren Summanden sind 0.

Hat jemand eine Lösung für so ein Problem?

Danke im voraus

Moschn

B
48 Beiträge seit 2010
vor 13 Jahren

Ein Vorschlag:

Ich mach das mal für 1000 weil 10^6 unübersichtlich ist.

Teile erst in zwei Summanden auf. Trivial wäre die Mitte zu wählen: 500+500.
Etwas eleganter ist eine normalverteilte Zufallszahl mit Mittelwert 500 und geeigneter Streuung zu nehmen. Sagen wir diese Zufallszahl wird 470. Um auf die 1000 zu kommen ist der zweite Summand ("Komplementärwert) damit natürlich 530.

Somit hast Du deine ersten beiden Summanden 470 und 530.

Für beide wiederholst Du das Verfahren, mit 470/2 und 530/2 als Mittelwerte der beiden Zufallszahlen. Mit diesen beiden Werten und den jeweiligen "Komplementärwerten" hast Du die 1000 schon in vier Summanden zerlegt.

Die Normalverteilung bringt es mit sich Grenzfälle abzufangen: Kleiner 0 und Größer als die aktuell zu zerlegende Zahl darf es natürlich nicht werden. Diese Grenzen bei einer Überschreitung zu nehmen scheint mir aber sinnvoll zu sein. Außerdem sollte die Streuung kleiner werden mit zunehmenden Iterationen.

Nach 8 Iterationen hast Du maximal 256 Summanden (einige können 0 sein). Oder müssen es exakt 200 sein?

49.485 Beiträge seit 2005
vor 13 Jahren

Hallo bSharp,

mit Gleichverteilung - auf die ich im Anfang des Threads ausdrücklich hingewiesen habe - hat das dann allerdings nicht viel zu tun. Eher damit, dass am Ende alle Summanden ungefähr gleich groß sind.

herbivore

M
Moschn Themenstarter:in
16 Beiträge seit 2009
vor 13 Jahren

Nach 8 Iterationen hast Du maximal 256 Summanden (einige können 0 sein). Oder müssen es exakt 200 sein?

Das Ziel wäre eig. eine Anzahl von Summanden und die zu teilende Zahl angeben zu können...

Ausserdem wäre das mit der Streuung keinen "echten" Zufall. Einen echten Zufall wurde bisher in diesem Thread nur mit der Methode, alle möglichen Konstellationen zuerst zu berechnen und dann eine zufällige davon zu berechnen. Die andere Möglichkeit wurde von gaussmath vorgestellt, welche aber nur für 3 Summanden gilt.

mfg

Moschn

49.485 Beiträge seit 2005
vor 13 Jahren

Hallo Moschn,

Einen echten Zufall wurde bisher in diesem Thread nur mit der Methode, alle möglichen Konstellationen zuerst zu berechnen und dann eine zufällige davon zu berechnen.

wobei die vermutlich wegen der hier exorbitant hohen Anzahl von Kombinationen nicht realisierbar wäre.

Die andere Möglichkeit wurde von gaussmath vorgestellt, welche aber nur für 3 Summanden gilt.

Die Lösung mit dem Berechnen der Anzahl der Kombinationen und dem zufälligen Auswählen einer davon, ist ja auch nur für drei Summanden implementiert. 😃 Andersherum lässt sich auch der Vorschlag von gaussmath auf mehr als drei Summanden übertragen. Das Problem dabei ist jedoch, dass für eine exakte Gleichverteilung viel zu viele Versuche verworfen werden müssten. Es wären ja nur die Versuche zulässig, bei denen die die (Hilfs-)Zufallszahlen (zufällig) monoton steigend wären. Eine Sortierung würde die exakte Gleichverteilung nicht gewährleisten.

Anderseits denke ich, die Störung der Gleichverteilung praktisch gesehen so gering wäre, dass man sie vernachlässigen kann. Entsprechend wäre also mein Vorschlag für eine praktikable Erweiterung des ursprünglichen Vorschlags von gaussmath auf große Zahlen und viele Summanden:

Wenn die Summe s ist und diese in n Summanden zerlegt werden soll: Fülle ein Array der Größe n+1 mit n-1 Zufallszahlen zwischen 0 und s (jeweils einschließlich), packe außerdem 0 und s in das Array, sortiere das Array absteigend: Die Differenzen zwischen je zwei direkt aufeinander folgenden Elementen sind dann deine Summanden.

herbivore

M
Moschn Themenstarter:in
16 Beiträge seit 2009
vor 13 Jahren

Anderseits denke ich, die Störung der Gleichverteilung praktisch gesehen so gering wäre, dass man sie vernachlässigen kann. Entsprechend wäre also mein Vorschlag für eine praktikable Erweiterung des ursprünglichen Vorschlags von gaussmath auf große Zahlen und viele Summanden: ...

Ich habe deinen Vorschlag gleich kurz ausprobiert und leider ergiebt dies nicht die anvisierte "Gleichverteilung". Siehe Anhang

EDIT: Der Grund, dass ich auf diesem "echten" Zufall beharre, besteht darin, dass ich eine Verschlüsselung implementiere. Dabei ist es natürlich sehr schlecht keine "Gleichverteilung" zu haben, weil man dann einfacher auch die Summanden schliessen kann.

49.485 Beiträge seit 2005
vor 13 Jahren

Hallo Moschn,

was genau zeigt dein Diagramm? Und inwiefern spricht das gegen die Gleichverteilung aller möglichen Kombinationen? Dass die vorkommenden Zahlen nicht gleichverteilt sind, wenn die Kombinationen gleichverteilt sind, geht ja schon aus dem anderen Thread hervor.

herbivore

M
Moschn Themenstarter:in
16 Beiträge seit 2009
vor 13 Jahren

Hallo herbivore,

Sorry habe ein nicht sooo perfektes Diagramm gemacht^^ hier ein weiteres und so hoffe ich besseres.

Das ganze beschreibt fünf Durchgänge, dieses Ansatzes mit der Zielsumme von 1'000'000 und 298 Summanden (fragt mich nicht wie ich auf diese 298 gekommen bin 😄). Es zeigt die Häufigkeit, mit welcher die einzelnen Summanden auftreten.

Nur habe ich gemerkt, dass auch eine Häufigkeitsanalyse nichts bringt 😉 weil ich nicht abschätzen kann was denn eig gesucht ist 😉

Dazu aber noch eine Rechnung:

Zielsumme: 100'000
Anzahl Summanden: 200

-> Anzahl mögliche Konstellationen: (100'000+199)! / (199! * [100'000 - 199]! = 2.0822 * 10^622
-> Extrem gorsse Zahl!

Doch sobald man nicht neu würfelt, sondern einfach sortiert, gibt es wieder, unter der Annahme keiner doppelten Zufälle, 200! Möglichkeiten um dieselbe Konstellation zu erreichen. Doch bei den doppelten sieht es anders aus: Sobald eine Zfallszhl doppelt vertreten ist, also das Ergebniss 0 der Differenz rauskommen würde, haöbiert sich die Anzahl der 200! Möglichkeiten um dieselbe Konstellation zu erhalten.
Ganz zu schweigen davon, wenn 2 doppelte Zufälle eintraten.

Dies sieht man auch bei meinem Diagramm: 0 ist eig nie aufgetreten (das hängt natürlich auch von der hohen Zielsumme 1'000'000 ab).
EDIT: Bei meinem Diagramm wird aufgerundet, d. h. nur diejenige Differenz, die perfekt 0 ist, wöre unter 0 aufgelistet.

mfg Moschn

PS: mit doppelten Zufällen meine ich, dass man bei diesen 200 Zufällen, die man nach herbivores Vorschlag sortieren würde, 2 erhält, die den gleichen Wert besitzen.

49.485 Beiträge seit 2005
vor 13 Jahren

Hallo Moschn,

das neue Diagramm sieht doch schonmal nicht schlecht aus. Kleine Zahlen sind deutlich wahrscheinlicher als große Zahlen. Im Bereich für die Zahlen zwischen 1 und 1000 gibt es knapp über 200 Treffer. Die Wahrscheinlichkeit, dass dann die Null nicht exakt getroffen wird, liegt bei ca. 5:1. Dass keine 0 dabei ist, ist also also kein Indiz für einen Fehler. Dass man durch das Sortieren die Gleichverteilung etwas stört, hatte ich ja von Anfang an geschrieben. Meines Erachtens belegen deine Argumente aber nicht, dass die Gleichverteilung entscheidend gestört ist.

herbivore

M
Moschn Themenstarter:in
16 Beiträge seit 2009
vor 13 Jahren

Hallo herbivore

Die Gleichverteilung ist nicht gestört, sobald man 0, als keinen Gültigen Wert auffasst. ImAnhang ist eine Grafik des gleichen tests wie letztes mal nur diesmal mit 100 Summanden, einer Zielsumme von 300 und 5 Durchgängen. Hier sieht man deutlich, dass 0 weniger Häufig vorkommt als 1. Nach meiner Meinung sollte 0 aber mind. soviel wie 1 vorkommen (das ist so ein Bauchgefühl 😃 kann ich nicht richtig begründen 😄).

Na gut wenn man jetzt einfach 0 ausschliessen will und von rein Positiven Summanden ausgeht, kommt man wieder in einer mehr oder weniger komplexen Situation. Um ein Ergebnis ohne 0 zu erhalten, müsste man solange neu Würfeln, bis die 0 nicht mehr vorkommt, denn man kann den Zufallszahlen ja nicht sagen, dass sie nicht das gleiche wie vorhin ergeben dürfen. Das ganze liesse sich natürlich in einer Überprüfung in der eigentlichen Schlaufe verwirklichen, aber trozdem: wenn man beim letzten Summanden angekommen ist, muss man wohl relativ viel neu Würfeln, um eine Zahl zu erhalten, die ungleich einer vorhergegangenen ist.

Gruss

Moschn

49.485 Beiträge seit 2005
vor 13 Jahren

Hallo Moschn,

du hast recht, die Null ist wirklich benachteiligt. Am besten sieht man dass, wenn man sich nochmal den Algorithmus für den Fall Summe 100 und 3 Summanden anschaut. Dafür müssen zwei Zufallszahlen zwischen 0 und 100 gezogen werden. In 101 Fällen beträgt die Differenz der beiden Zahlen 0, in 100 Fällen beträgt die Differenz der beiden Zahlen 1 und in weiteren 100 Fällen -1. Wenn man nun die Fälle, bei denen die Differenz -1 ist, verwirft (das ist ja genau der Vorschlag von zommi im anderen Thread), dann hat man die Gleichverteilung gerettet. Wenn man aber sortiert, dann hat man 200 Fälle, in denen die Differenz 1 ist, gegenüber nur 101 Fällen, in denen die Differenz 0 ist. Insofern ist eine 0 in der Mitte ungefähr halb so wahrscheinlich wie eine 1. Genaugenommen müsste man jetzt noch die Anzahl der Fälle für 0 oder 1 an den Rändern betrachten, aber die können den drastischen Unterschied in der Mitte sicher nicht kompensieren.

Das zur Erklärung. Eine Lösung habe ich allerdings nicht. Die Schwierigkeiten, die du schilderst, kann ich nachvollziehen, aber zumindest momentan nicht lösen. Aber ich bin ja auch nicht der einzige Helfer im Forum. 😃

herbivore