Distributions sur des listes triées

10

Disons que nous avons une liste d'articles commandée

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

Je recherche une famille de distributions avec support sur la liste ci-dessus régie par un paramètre alpha afin que:

Pour alpha = 0, il affecte la probabilité 1 au premier élément, a ci-dessus et 0 au reste. Autrement dit, si nous échantillonnons à partir de cette liste, avec remplacement, nous obtenons toujours a.
À mesure que l'alpha augmente, nous attribuons des probabilités de plus en plus élevées au reste de la liste, en respectant l'ordre de la liste, après une décroissance exponentielle.
Lorsque alpha = 1, nous attribuons une probabilité égale à tous les éléments de la liste, donc l'échantillonnage de la liste revient à ignorer son ordre.

Ceci est très similaire à la distribution géométrique, mais il existe quelques différences notables:

La distribution de distribution géométrique est définie sur tous les nombres naturels. Dans mon cas ci-dessus, la liste a une taille fixe.
La distribution géométrique n'est pas définie pour alpha = 0.

distributions sampling discrete-data Amelio Vazquez-Reina
la source

1

Vous semblez décrire une famille de distributions géométriques tronquées. Cependant, il existe une infinité de familles qui se comportent qualitativement comme votre description. Plus précisément, alors, ce serait d'expliquer pourquoi vous aimeriez utiliser une telle famille.

whuber

Merci @whuber Oui, je comprends qu'il existe une infinité de distributions qui correspondent à cette description. Y en a-t-il qui vous viennent à l'esprit? J'ai un système qui sélectionne actuellement le premier élément de cette liste (représentant les scores), mais je veux randomiser ce choix (et paramétrer cette randomisation). Je ne recherche pas un type particulier de "désintégration" basé sur l'alpha. Tant que alpha = 0 ne représente aucune randomisation, c'est-à-dire choisir le premier élément, 1 représente "choisir n'importe quel élément", et les alphas entre 0 et 1 représentent "quelque chose entre les deux" ces deux alphas, ce serait suffisant.

Amelio Vazquez-Reina

11

Supposons que , le rang de l'élément de liste , a une valeur dans pour une liste avec éléments (les liens peuvent être rompus au hasard). Ensuite, nous pourrions définir la probabilité de sélectionner pour être: $r_i$ $i$ $\{0, 1, \ldots, n-1\}$ $n$ $i$

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

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

Il s'agit essentiellement d'une distribution géométrique tronquée correctement normalisée, et elle est également liée à la fonction Softmax . Dans le cas particulier de , utilisez la convention . Notez que le dénominateur peut toujours être écrit dans une simple expression de forme fermée. Pour il prend la valeur , et pour il prend la valeur . $\alpha=0$ $0^0 = 1$ $\alpha < 1$ $\frac{1-\alpha^n}{1-\alpha}$ $\alpha=1$ $n$

Avec , il est clair que cela affecte simplement une probabilité égale à chaque élément. Comme , cela approche en donnant toute la masse de probabilité au premier élément. $\alpha=1$ $\alpha\rightarrow 0$

Dans une liste de 10 éléments, la diminution à peu près exponentielle que vous avez demandée est claire avec : $\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$

Le graphique suivant montre comment la probabilité de sélection du premier élément change en fonction de , en utilisant une liste de longueur 10. $\alpha$

josliber
la source

Agréable. C'est beaucoup plus intelligent que je ne pourrais jamais espérer l'être.

Matthew Drury

@Matthew Ce sont les distributions géométriques tronquées auxquelles j'ai fait référence plus tôt.

whuber

4

Je vais essayer de construire un exemple à partir des premiers principes.

Prenons trois distributions comme blocs de construction:

P est la distribution attribuant la probabilité un au premier élément de la liste, zéro à tous les autres.
E est la distribution affectant la probabilité au premier élément de la liste, au suivant, et ainsi de suite. Puisque la liste est finie, celles-ci ne totaliseront pas , mais nous pouvons normaliser pour obtenir une distribution de probabilité. $\frac{1}{2}$ $\frac{1}{4}$ $1$
U est la distribution uniforme sur la liste.

Maintenant, nous voulons prendre une famille à un paramètre de combinaisons convexes positives de ces distributions

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

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

où pour tous les , avec la propriété supplémentaire que et . $\alpha(t) + \beta(t) + \gamma(t) = 1$ $t \in [0, 1]$ $\alpha(0) = 1$ $\gamma(1) = 1$

Géométriquement, nous voulons tracer une courbe dans le triangle équilatéral s'étendant entre les points qui commence au premier virage et se termine et au dernier. De plus, comme nous voulons que la distribution soit "exponentielle" au milieu, nous aimerions que la courbe occupe l'intérieur du triangle aux temps . $(\alpha(t), \beta(t), \gamma(t))$ $(1, 0, 0), (0, 1, 0), (0, 0, 1)$ $t \in (0, 1)$

Voici une option pour la courbe:

(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)$

J'ai construit ce travail à l'envers à partir des propriétés que nous aimerions. La courbe longe le bord du triangle entre les sommets de début et de fin. Le reste de la formule n'est qu'une somme convexe de cette courbe de bord et du point unique , qui pousse la courbe le long du bord vers l'intérieur aux instants . $(1-t, 0, t)$ $\left(\frac{1}{3}, \frac{1}{3}, \frac{1}{3} \right)$ $t \in (0, 1)$

Matthew Drury
la source

Distributions sur des listes triées

Réponses: