Benutzer:Philipendula/IP-Ranges

Statistik für Wikipedia-Admins

Schreib doch mal ein WikiBook "Statistik für Wikipedia-Admins". Vielleicht ist mein Denken etwas verlangsamt (nicht vom Vatertagsausflug!), aber ich grüble jetzt zwei Tage über folgendes:

• Ein Vandale benutzt bekanntermaßen IPs aus einem Pool von N Adressen. Bemerkt wurden seine Edits von n dieser N Adressen. Von diesen n benutzten Adressen sind m bei mehr als einem Login benutzt worden. Schätze ab, von wievielen Adressen aus er insgesamt editiert hat.

--Pjacobi 14:18, 19. Mai 2007 (CEST)

Fürn Buch ist es vielleicht zu wenig. Wär aber ne nette Klausuraufgabe. Wenn ich den Kopf mal frei hab, denk ich drüber nach. Gruß --Philipendula 15:05, 19. Mai 2007 (CEST)

Ich hab mal gegrübelt und mir ist nicht klar: Wenn er N viele IPs zur Verfügung hat und es ist ein sehr großer Pool, ist die Wahrscheinlichkeit, dass er zweimal die selbe Nummer kriegt, quasi Null. D.h. er hätte dann theoretisch so viele IPs gekriegt, wie sich eingeloggt hat. Wenn also eine IP mehrmals vorkommt, ist N entweder sehr klein oder es ist die Zahl, die gesucht ist. Suchen wir die Range, die er faktisch zur Verfügung hat? Viele Grüße --Philipendula 01:12, 20. Mai 2007 (CEST)

Mal ins Unreine gedacht (setzen wir π, 2 und i zu 1). Sei N=1000. Und rechnen wir (in umgekehrter Richtung zur eigentlichen Fragestellung) zwei Fälle durch.

• Fall 1: Er macht 40 Logins (die alle beobachtet werden). M.E. sollten dann ca. 2 IPs je zwei Logins haben, also 38 je einen.
  • Beobachtet wird also n=38, m=2
• Fall 2: Er macht 80 Logins (die zu 50% beobachtet werden). M.E. sollten dann ca. 8 IPs je zwei Logins haben, also 72 je einen.
  • Beobachtet wird also n=36, m=6. (Die Doppel-Login IPs werden nur zu 25% nicht beobachtet, denn wenn ein Login auffällt, sieht man auch den anderen)

Pjacobi 01:29, 20. Mai 2007 (CEST)

Zur Klarstellung: Ist N bekannt? --Philipendula 10:18, 20. Mai 2007 (CEST)

Ja. --Pjacobi 18:44, 22. Mai 2007 (CEST)

Hallo!

Bin gestern zufällig über diese Seite gestoßen und habe über das Problem nachgedacht. Wenn ich es richtig verstanden habe, würde sich die Sache, umformuliert als Urnenproblem, folgendermaßen darstellen: Aus einem Pool von N Kugeln, von denen jede eindeutig gekennzeichnet ist, entnimmt man n Kugeln mit Zurücklegen. Von diesen n gezogenen Kugeln sind m Kugeln unterschiedlich. (m drückt also nicht die Anzahl der Doppel-Logins, sondern die Anzahl der unterschiedlichen IPs einem Set von n Logins aus).

Die Wahrscheinlichkeit für ein beliebiges N unter gegebenem n und m P(X=N|n,m) sollte sich folgendermaßen berechnen lassen:

$P(N|n,m)={\frac {\text{guenstige Faelle}}{\text{moegliche Faelle}}}$

günstige Fälle: Möglichkeiten, n Kugeln mit Zurücklegen aus N zu ziehen, wobei sich genau m Kugeln unterscheiden.

mögliche Fälle: Möglichkeiten, n Kugeln mit Zurücklegen aus N zu ziehen: = $N^{n}$

Beispiel für n = 4, m = 3: In der Urne befinden sich N Kugeln, in einer Ziehung wurden n=4 Kugeln gezogen, davon waren m=3 unterschiedlich. Umgelegt auf das IP-Problem: Es gab n=4 Logins aus m=3 unterschiedlichen IP-Adressen. Geschätzt werden soll der Umfang N.

Die günstigen Fälle berechnen sich m.M. folgendermaßen:

${\text{guenstige Faelle}}={{n-1} \choose {m-1}}{N \choose m}$

und damit die Wahrscheinlichkeit:

$P(N|n,m)={\frac {{{n-1} \choose {m-1}}{N \choose m}}{N^{n}}}$

Das Problem n Kugeln aus $N=\{N_{1},N_{2},\ldots ,N_{N}\}$ auszuwählen (davon m unterschiedliche), könnte man auch so anschreiben:

$k_{1}$ mal wurde $N_{1}$ gezogen, $k_{2}$ mal $N_{2}$, ..., $k_{N}$ mal $N_{N}$, mit 0 ≤ $k_{i}$ ≤ (n-m+1).

n-m+1 weil $k_{i}$ maximal n verringert um die Anzahl der restlichen Gruppen (m-1) sein kann, deren k in diesem Fall 1 wäre. Die Summe über die ks muss n ergeben ($\sum _{i=1}^{N}{k_{i}}=n$) und m der ks müssen ungleich 0 sein, weil m unterschiedliche Kugeln aus N gezogen wurden.

Die Anzahl der Möglichkeiten m der N ks ungleich 0 zu setzen entspricht dem Problem, m Kugeln ohne Zurücklegen aus einer Menge von N Kugeln zu ziehen und berechnet sich durch ${N \choose m}$.

In jeder dieser Möglichkeit, unterschiedliche ks ungleich 0 zu setzen, gibt es ${{n-1} \choose {m-1}}$ Möglichkeiten, die ausgewählten ks mit Werten 0 ≤ $k_{i}$ ≤ (n-m+1) zu belegen. Grafisch entspricht das dem Problem, die Anzahl der Möglichkeiten n Kugeln in m Gruppen einzuteilen.

Hier ein paar Verteilungen

$P(N|n=8,m=5)$

$P(N|n=20,m=5)$

Je größer n wird, desto wahrscheinlicher ist m als bester Schätzer für N.

$P(N|n=5,m=5)$

Sind n und m gleich groß, kann N nicht geschätzt werden, da N+1 wahrscheinlicher als N ist.

Die Wahrscheinlichkeiten für N sind in allen drei Szenarios sehr klein, weil $N^{n}$ rapide anwächst und im Vergleich zu den günstigen Fällen sehr groß ist.

---Wijaa 09:15, 18. Aug. 2007 (CEST)