Rozkłady na posortowane listy

10

Powiedzmy, że mamy uporządkowaną listę przedmiotów

[a, b, c, ... x, y, z, ...]

Szukam rodziny dystrybucji z obsługą na powyższej liście, regulowanej przez niektóre parametry alfa, dzięki czemu:

Dla alfa = 0 przypisuje prawdopodobieństwo 1 do pierwszego elementu, a powyżej, i 0 do reszty. Oznacza to, że jeśli próbkujemy z tej listy, z wymianą, zawsze otrzymujemy a.
Wraz ze wzrostem alfa przypisujemy coraz większe prawdopodobieństwa reszcie listy, przestrzegając kolejności listy, po ~ wykładniczym rozkładzie.
Gdy alfa = 1, przypisujemy jednakowe prawdopodobieństwo wszystkim pozycjom na liście, więc próbkowanie z listy przypomina ignorowanie jej kolejności.

Jest to bardzo podobne do rozkładu geometrycznego, ale istnieją pewne znaczące różnice:

Rozkład rozkładu geometrycznego jest zdefiniowany dla wszystkich liczb naturalnych. W moim przypadku powyżej lista ma ustalony rozmiar.
Rozkład geometryczny nie jest zdefiniowany dla alfa = 0.

distributions sampling discrete-data Amelio Vazquez-Reina
źródło

1

Wygląda na to, że opisujesz rodzinę skróconych rozkładów geometrycznych. Istnieje jednak nieskończenie wiele rodzin, które zachowują się jakościowo jak opis. Chodzi o to, aby wyjaśnić, do czego chciałbyś wykorzystać taką rodzinę.

whuber

Dzięki @whuber Tak, rozumiem, że istnieje nieskończenie wiele dystrybucji pasujących do tego opisu. Jakieś konkretne, które przychodzą ci na myśl? Mam system, który aktualnie wybiera pierwszy element tej listy (reprezentujący wyniki), ale chcę losowo wybrać ten wybór (i sparametryzować tę randomizację). Nie szukam konkretnego rodzaju „rozpadu” opartego na alfa. Tak długo, jak alfa = 0 nie reprezentuje losowości, tj. Wybierz pierwszy element, 1 oznacza „wybierz dowolny element”, a cyfry od 0 do 1 oznaczają „coś pomiędzy” tymi dwoma alfami, byłoby wystarczająco dobre.

Amelio Vazquez-Reina

11

$r_i$ $i$ $\{0, 1, \ldots, n-1\}$ $n$ $i$

p_{i} = \frac{α^{r_{i}}}{\sum_{k = 1}^{n} α^{r_{k}}}

$p_i = \frac{\alpha^{r_i}}{\sum_{k=1}^n \alpha^{r_k}}$

$\alpha=0$ $0^0 = 1$ $\alpha < 1$ $\frac{1-\alpha^n}{1-\alpha}$ $\alpha=1$ $n$

$\alpha=1$ $\alpha\rightarrow 0$

$\alpha=0.5$

p_{0} \approx 0.5005 p_{1} \approx 0.2502 p_{2} \approx 0.1251 p_{3} \approx 0.0626 p_{4} \approx 0.0313 p_{5} \approx 0.0156 p_{6} \approx 0.0078 p_{7} \approx 0.0039 p_{8} \approx 0.0020 p_{9} \approx 0.0010

$p_0 \approx 0.5005 \\ p_1 \approx 0.2502 \\ p_2 \approx 0.1251 \\ p_3 \approx 0.0626 \\ p_4 \approx 0.0313 \\ p_5 \approx 0.0156 \\ p_6 \approx 0.0078 \\ p_7 \approx 0.0039 \\ p_8 \approx 0.0020 \\ p_9 \approx 0.0010$

$\alpha$

josliber
źródło

Miły. Jest to o wiele mądrzejsze, niż mogłem się spodziewać.

Matthew Drury

@Matthew Są to skrócone rozkłady geometryczne, o których wspominałem wcześniej.

whuber

4

Spróbuję zbudować przykład z pierwszych zasad.

Weźmy trzy dystrybucje jako nasze bloki konstrukcyjne:

P jest rozkładem przypisującym prawdopodobieństwo do pierwszego elementu listy, od zera do wszystkich pozostałych.
$\frac{1}{2}$ $\frac{1}{4}$ $1$
U jest równomiernym rozkładem na liście.

Teraz chcemy wziąć jednoparametrową rodzinę dodatnich wypukłych kombinacji tych rozkładów

α (t) P + β (t) E + γ (t) U

$\alpha(t) P + \beta(t) E + \gamma(t) U$

$\alpha(t) + \beta(t) + \gamma(t) = 1$ $t \in [0, 1]$ $\alpha(0) = 1$ $\gamma(1) = 1$

$(\alpha(t), \beta(t), \gamma(t))$ $(1, 0, 0), (0, 1, 0), (0, 0, 1)$ $t \in (0, 1)$

Oto opcja krzywej:

(1 - t (1 - t)) (1 - t, 0, t) + t (1 - t) (\frac{1}{3}, \frac{1}{3}, \frac{1}{3})

$(1 - t(1-t)) \left(1 - t, 0, t \right) + t(1 - t) \left(\frac{1}{3}, \frac{1}{3}, \frac{1}{3} \right)$

$(1-t, 0, t)$ $\left(\frac{1}{3}, \frac{1}{3}, \frac{1}{3} \right)$ $t \in (0, 1)$

Matthew Drury
źródło

Rozkłady na posortowane listy

Odpowiedzi: