Observations aléatoires d'une commande totale, combien elles nous disent?

Question

Supposons que nous ayons une commande totale sur les éléments $ a_1, a_2, ..., a_n $, ce qui signifie qu'il y a la permutation $ pi $ tel que $ a _ { pi (1)}. Mais nous ne savons pas $ pi $. Ce que nous savons, c'est un ensemble d'observations aléatoires de l'ordre par paire des éléments. La matrice d'observation $ B in {0,1 } ^ {n fois n} $ est généré au hasard comme suit:$$ b_ {i, j} sim begin {case} text {bernoulli} (p) qquad text {if} i> j 0 qquad qquad qquad text {sinon} end { cas} $$dans lequel $ p in [0,1] $ est une constante. La formule ci-dessus signifie que les éléments au-dessus de la diagonale sont tirés de $ text {bernoulli} (p) $ et le reste des éléments sont $0$. Matrice $ B $ indique nos observations de la commande, c'est-à-dire si $ B_ {i, j} = 1 $ Nous connaissons l'ordre de $ a_i $ et $ a_j $, et sinon ne le faites pas. La raison pour laquelle les éléments sur le triangle inférieur de $ B $ sont zéro, c'est parce que les observations symétriques sont redoutantes.

question 1

Laisser $ K $ indique le nombre d'ordonnances de $ a_1, ..., a_n $ qui sont cohérents avec nos observations partielles. Depuis $ B $ est une variable aléatoire, $ K $ est également une variable aléatoire. La question est de savoir quelle est la valeur attendue de $ K $ et quelle est sa concentration autour de la moyenne en fonction de $ p $? Il y a deux cas extrêmes: (1) si $ p = 0 $ Toutes les commandes sont valides et donc $ K = n! $ (2) Si $ p = 1 $ Nous avons la commande complète et $ K = 1 $.

Pour 0 $ toutefois $ K $ ne serait pas une constante. Je suppose que pour suffisamment grand $ n $ si $ p gg mathcal {o} ( frac { log n} {n}) $ conduirait à $ mathbb {e} [k] à 1 $. La justification derrière cela est que nous aurions $ omega (np) = omega (n log n) $ Comparaisons qui sont asymptotiquement plus grandes que le nombre de comparaisons les algorithmes de tri. Cependant, cela est loin d'être clair car les observations sont prises au hasard.

La réponse est idéalement une distribution avec le paramètre $ p $ Pour le nombre de possibilités. Mais si ce n'est pas possible, les limites de queue ou la valeur et la variance attendues sont également acceptables.

question 2

La motivation derrière la définition de $ K $ devait capturer la quantité d'incertitude qui reste. Mais il semble le surestimer ou ne l'exprime pas très bien, car si nous ne connaissons pas quelques paires $ K $ se développera de façon exponentielle avec ce nombre. Je pensais donc à une autre façon naturelle de la définir.

Laisser $ O in {0,1 } ^ {n fois n} $ être le résultat de nos observations, dans lesquelles $ O_ {i, j} = 1 $ désigne que nous avons observé $ a_i. De cette matrice, nous pouvons calculer la fermeture transitive $ O ^ star $, qui applique une propriété transitive pour trouver toutes les relations "plus petites que" dans les données. Par exemple, si nous avons $ O_ {i, j} = 1 $ et $ O_ {j, k} = 1 $ nous aurons $ O ^ star_ {i, k} = 1 $. Cela vaut également pour une chaîne de longueur arbitraire.

Laisser $ S $ être la somme de tous les éléments de $ O ^ star $. Si nous pouvons conclure les relations entre toutes les paires, $ S $ atteindra sa valeur maximale de $ S = n (n-1) / 2 $, et donc $ I = frac {s} {(n (n-1) / 2)} $ est une valeur qui montrera à quel point nous savons sur la commande, avec $1$ ce qui signifie que nous connaissons exactement la commande, et $0$ ce qui signifie que nous ne savons rien. Maintenant, la question est: quelle est sa signification $ mathbb {e} [i] $ en tant que fonction de $ n $ et $ p $? Et s'il est possible d'analyser, quelle est la concentration de $ I $ autour de sa moyenne? Aussi, quel est le seuil pour $ p $ en tant que fonction de $ n $ qui fait $ mathbb {e} [i] $ sauter à $0$ ou $1$?

Par simulations, j'ai trouvé que lorsque $ n à infty $, même pour une petite valeur de $ p = frac { log n} {n} $ mène à $ I to1 $ avec une forte probabilité. La raison de cette divergence apparente entre $ I $ et $ K $ est-ce que si nous avons $ m $ paires inconnues dans $ O ^ star $, alors $ K $ se développera de façon exponentielle wrt $ m $ tandis que $ S $ ne sera affecté que linéairement. Bien que le $ I $ et $ log k $ sont liés, je ne pense pas qu'il y ait une relation exacte entre eux.