Quelle est la probabilité que le tableau reste le même ?

Question

Cette question a été posée lors d'un entretien avec Microsoft. Je suis très curieux de savoir pourquoi ces personnes posent des questions aussi étranges sur les probabilités ?

Étant donné un rand(N), un générateur aléatoire qui génère des nombres aléatoires de 0 à N-1.

int A[N]; // An array of size N
for(i = 0; i < N; i++)
{
    int m = rand(N);
    int n = rand(N);
    swap(A[m],A[n]);
}

EDITAR: Notez que la graine n'est pas fixe.

quelle est la probabilité que le tableau A reste le même ?
Supposons que le tableau contient des éléments uniques.

Answer 1

Une solution simpliste consiste à

p >= 1 / N N

Puisqu'il est possible que le tableau reste le même si m = n pour chaque itération. Et m est égal à n avec possibilité 1 / N .

C'est certainement plus élevé que ça. La question est de savoir de combien

Deuxième réflexion : On pourrait aussi dire que si l'on mélange un tableau au hasard, chaque permutation a la même probabilité. Puisqu'il y a n! permutations, la probabilité d'en obtenir une seule (celle que nous avons au début) est de

p = 1 / N !

ce qui est un peu mieux que le résultat précédent.

Comme nous l'avons vu, l'algorithme est biaisé. Cela signifie que chaque permutation n'a pas la même probabilité. Ainsi, 1 / N! n'est pas tout à fait exact. Vous devez trouver comment est la distribution des permutations.

Answer 2

Pour information, je ne suis pas sûr que la limite ci-dessus (1/n^2) tienne :

N=5 -> 0.019648 < 1/25
N=6 -> 0.005716 < 1/36

Code d'échantillonnage :

import random

def sample(times,n):
    count = 0;
    for i in range(times):
        count += p(n)
    return count*1.0/times;

def p(n):
    perm = range(n);
    for i in range(n):
        a = random.randrange(n)
        b = random.randrange(n)

        perm[a],perm[b]=perm[b],perm[a];

    return perm==range(n)

print sample(500000,5)

Answer 3

Tout le monde suppose que A[i] == i ce qui n'a pas été explicitement explicite. Je vais faire cette hypothèse également, mais notez que la probabilité dépend du contenu. Par exemple, si A[i]=0 alors la probabilité = 1 pour tout N.

Voici comment procéder. Laissez P(n,i) soit la probabilité que le tableau résultant diffère par exactement i transpositions du tableau original.

Nous voulons savoir P(n,0) . C'est vrai que :

P(n,0) = 
1/n * P(n-1,0) + 1/n^2 * P(n-1,1) = 
1/n * P(n-1,0) + 1/n^2 * (1-1/(n-1)) * P(n-2,0)

Explication : on peut obtenir le tableau original de deux façons, soit en faisant une transposition "neutre" dans un tableau qui est déjà bon, soit en retournant la seule transposition "mauvaise". Pour obtenir un tableau avec une seule "mauvaise" transposition, on peut prendre un tableau avec 0 mauvaise transposition et faire une transposition qui n'est pas neutre.

EDIT : -2 au lieu de -1 dans P(n-1,0)

Answer 4

Ce n'est pas une solution complète, mais c'est au moins quelque chose.

Prenez un ensemble particulier de swaps qui n'ont aucun effet. Nous savons que ses swaps ont dû finir par former un tas de boucles de tailles différentes, utilisant un total de n les échanges. (Aux fins du présent document, un swap sans effet peut être considéré comme une boucle de taille 1).

Peut-être pouvons-nous

1) Répartissez-les en groupes en fonction de la taille des boucles.
2) Calculez le nombre de façons d'obtenir chaque groupe.

(Le principal problème est qu'il existe un tonne de différents groupes, mais je ne suis pas sûr de la façon dont on calcule réellement ce chiffre si l'on ne tient pas compte des différents groupes).

Answer 5

Question intéressante.

Je pense que la réponse est 1/N, mais je n'ai pas de preuve. Quand je trouverai une preuve, je modifierai ma réponse.

Ce que j'ai eu jusqu'à maintenant :

Si m == n, vous ne changerez pas le tableau. La probabilité d'obtenir m == n est de 1/N, car il y a N^2 possibilités, et seule N convient ((i,i) pour chaque 0 <= i <= N-1).

Ainsi, nous obtenons N/N^2 = 1/N.

Dénote Pk la probabilité qu'après k itérations de permutations, le tableau de taille N reste le même.

P1 = 1/N. (Comme nous l'avons vu ci-dessous)

P2 = (1/N) P1 + (N-1/N) (2/N^2) = 1/N^2 + 2(N-1) / N^3.

Explanation for P2:
We want to calculate the probability that after 2 iterations, the array with 
N elements won't change. We have 2 options : 
- in the 2 iteration we got m == n (Probability of 1/N)
- in the 2 iteration we got m != n (Probability of N-1/N)

If m == n, we need that the array will remain after the 1 iteration = P1.
If m != n, we need that in the 1 iteration to choose the same n and m 
(order is not important). So we get 2/N^2.
Because those events are independent we get - P2 = (1/N)*P1 + (N-1/N)*(2/N^2).

Pk = (1/N)*Pk-1 + (N-1/N)*X. (la première pour m == n, la seconde pour m != n)

Je dois réfléchir davantage à ce que X représente. (X est juste un remplacement pour la formule réelle, pas une constante ou autre chose)

Example for N = 2.
All possible swaps:

(1 1 | 1 1),(1 1 | 1 2),(1 1 | 2 1),(1 1 | 2 2),(1 2 | 1 1),(1 2 | 1 2)
(1 2 | 2 1),(1 2 | 2 2),(2 1 | 1 1),(2 1 | 1 2),(2 1 | 2 1),(2 1 | 2 2)
(2 2 | 1 1),(2 2 | 1 2),(2 2 | 2 1),(2 1 | 1 1).

Total = 16. Exactly 8 of them remain the array the same.
Thus, for N = 2, the answer is 1/2.

EDIT : Je souhaite introduire une autre approche :

Nous pouvons classer les échanges en trois groupes : les échanges constructifs, les échanges destructeurs et les échanges inoffensifs.

L'échange constructif est défini comme un échange qui permet à au moins un élément de se déplacer à sa place.

Un échange destructif est défini comme un échange qui fait bouger au moins un élément de sa position correcte.

Un échange inoffensif est défini comme un échange qui n'appartient pas aux autres groupes.

Il est facile de voir qu'il s'agit d'une partition de tous les échanges possibles. (intersection = ensemble vide).

Maintenant, l'affirmation que je veux prouver :

    The array will remain the same if and only if 
the number of Destructive swap == Constructive swap in the iterations.

Si quelqu'un a un contre-exemple, veuillez le noter en commentaire.

Si cette affirmation est correcte, nous pouvons prendre toutes les combinaisons et les additionner - 0 échange inoffensif, 1 échange inoffensif, ,N échanges inoffensifs.

Et pour chaque échange inoffensif k possible, nous vérifions si N-k est pair, si non, nous sautons. Si oui, on prend (N-k)/2 pour destructeur, et (N-k) pour constructif. Et on regarde toutes les possibilités.