Verdeling op permutaties afgeleid van de waarschijnlijkheid van paarsgewijze rangschikkingen

Een vervolgvraag voor Waarschijnlijkheidsschattingen voor paarsgewijze meerderheidsstemmen - ik denk dat dit niet het geval is Het geeft eigenlijk een antwoord in vreselijk precieze zin, maar het zou iets geven dat ik graag zou gebruiken in plaats van een. :-)

Ik kijk in feite naar een bepaalde klasse van verdeling van permutaties en probeer de kans te bepalen dat twee items in een bepaalde volgorde worden geplaatst. Ik vermoed dat ik hier op goed versleten terrein loop, maar ik heb niets kunnen vinden.

P is a $N \times N$ matrix with P > 0 and $P_{ij} = 1-P_{ji}$. Define a random variable $T$ taking values in $S_N$ (the permutations of $1, \ldots, N$) by

$P(T = \sigma) \propto \prod_{\sigma(i) < \sigma(j)} P_{ij}$ `

For fixed i, j I'd like to calculate $P(T(i) < T(j))$.

It's clear that this can't simply be $P_{ij}$: If you have e.g. $P_{12} = P_{23} = P_{31} = 0.9$ then $P(T(1) < T(2)) = 0.5$.

Helaas is het mij niet duidelijk hoe een algemene oplossing eruit zou moeten zien. Ik vermoed dat er misschien geen mooie gesloten-vorm-oplossing is, dus ik zou blij zijn met een redelijk efficiënte manier om een ​​numerieke benadering te berekenen.

One thing worth noting is that if we let $R_{ij} = P(T(i) < T(j))$ then for all k we have the constraint

$ R_ {ik} \ geq R_ {ij} + R_ {jk} - 1 $

Ik vermoed, maar heb nog niet kunnen bewijzen dat als P aan deze beperking voldoet dan P = R. Als dit het geval is, dan lijkt het waarschijnlijk dat R kan worden berekend als een oplossing voor deze beperkingen (plus die $ R_ {ij} = 1 - R_ {ji} $) die een bepaalde afstandsfunctie van P minimaliseert

2

1 antwoord

In an indirect way, this related to graphical models and the problem of estimating events in a given model. Your matrix yields a digraph with parallel edges between each pair of nodes $(i,j)$ labelled $P_{ij}$ and $P_{ji} = 1 - P_{ij}$. Now pick any two nodes $i,j$. The probability of the event $T(i) < T(j)$ has to be summed over all DAGs induced by the sampling process in which $T(i)$ is before $T(j)$ in the topological (and total) order.

Dit is uw klassieke som-van-producten, met een exponentieel aantal termen in de som. Ik vermoed dat het probleem zou zijn #P -hard (dat wil zeggen onhandelbaar voor schatting) tenzij er een diepere structuur is die men kan aannemen of exploiteren (bijvoorbeeld in hoe de schatting van het grafische model gemakkelijk is als een gerelateerde grafiek de veldbreedte heeft begrensd).

Update: In response to your comment (I ran out of space in the comment field), there are two slightly half-assed things I can suggest:

  1. Misschien wilt u beginnen met knooppuntstructuur , zoals methoden om ideeën op te doen over wat een convergente procedure kan er uitzien. Hoewel het andere problemen zijn, is mijn vermoeden dat veel van de probleemstructuur vergelijkbaar is.
  2. Aan de kant van de theorie, zelfs als het probleem hardnekkig is, kun je misschien een benaderend antwoord krijgen (met garanties) met vergelijkbare ideeën (of zelfs een korting) op de methode die wordt gebruikt voor schatting van de permanente . Dat is hoogst niettriviaal. Dit artikel bespreekt een deel van de literatuur een
1
toegevoegd
Ik vermoed dat je gelijk hebt dat het probleem in het algemeen hardnekkig is. Helaas denk ik niet dat er helaas een veel diepere structuur in het probleem zal zijn. De kansen zijn echter goed dat de originele P mogelijk in de buurt van R ligt, omdat ze zijn afgeleid van gegevens die waarschijnlijk 'dichtbij' zijn aan de gemodelleerde versie van het beschreven proces. Dus als er een iteratief proces is dat samenvalt met het resultaat, zou het misschien snel convergeren in mijn waargenomen geval, zelfs als het slechte algemene prestaties heeft?
toegevoegd de auteur sickgemini, de bron