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

_{<em>Je me suis un peu amusé avec celui-ci. La première chose à laquelle j'ai pensé en lisant le problème est la théorie des groupes (le groupe symétrique S n en particulier). La boucle for construit simplement une permutation dans S n en composant des transpositions (c'est-à-dire des échanges) à chaque itération. Mes mathématiques ne sont pas très spectaculaires et je suis un peu rouillé, donc si ma notation est erronée, soyez indulgent avec moi.</em>}

---

Vue d'ensemble

Soit A soit le cas où notre tableau est inchangé après permutation. On nous demande finalement de trouver la probabilité de l'événement A , Pr(A) .

Ma solution tente de suivre la procédure suivante :

1. Considérer toutes les permutations possibles (c'est-à-dire les réorganisations de notre tableau).
2. Répartissez ces permutations en disjoint en fonction du nombre de ce que l'on appelle transpositions d'identité ils contiennent. Cela permet de réduire le problème à même permutations uniquement.
3. Déterminez la probabilité d'obtenir la permutation d'identité étant donné que la permutation est paire (et d'une longueur particulière).
4. Additionnez ces probabilités pour obtenir la probabilité globale que le tableau soit inchangé.

1) Résultats possibles

Remarquez que chaque itération de la boucle for crée un swap (ou transposition ) qui aboutit à l'une des deux choses suivantes (mais jamais aux deux) :

1. Deux éléments sont échangés.
2. Un élément est échangé avec lui-même. Pour nos besoins, le tableau reste inchangé.

Nous étiquetons le deuxième cas. Définissons un transposition d'identité comme suit :

Un transposition d'identité se produit lorsqu'un nombre est échangé avec lui-même. C'est-à-dire, lorsque n == m dans la boucle for ci-dessus.

Pour toute exécution donnée du code listé, nous composons N transpositions. Il peut y avoir 0, 1, 2, ... , N des transpositions d'identité apparaissant dans cette "chaîne".

---

Par exemple, considérons un N = 3 cas :

Given our input [0, 1, 2].
Swap (0 1) and get [1, 0, 2].
Swap (1 1) and get [1, 0, 2]. ** Here is an identity **
Swap (2 2) and get [1, 0, 2]. ** And another **

Notez qu'il y a un nombre impair de transpositions non identiques (1) et que le tableau est modifié.

---

2) Partitionnement basé sur le nombre de transpositions d'identité

Soit K_i soit l'événement qui i transpositions d'identité apparaissent dans une permutation donnée. Notez que cela constitue une partition exhaustive de tous les résultats possibles :

• Aucune permutation ne peut avoir simultanément deux quantités différentes de transpositions d'identité, et
• Toutes les permutations possibles doivent avoir entre 0 y N transpositions d'identité.

Ainsi, nous pouvons appliquer le Loi de la probabilité totale :

                      ![](https://i.stack.imgur.com/js91V.png)

Maintenant, nous pouvons enfin profiter de la partition. Notez que lorsque le nombre de non-identité transpositions est étrange, il n'y a aucune chance que le tableau reste inchangé*. Ainsi :

                        ![](https://i.stack.imgur.com/p5PKc.png)

* _{En théorie des groupes, une permutation est paire ou impaire, mais jamais les deux. Par conséquent, une permutation impaire ne peut pas être la permutation d'identité (puisque la permutation d'identité est paire).}

3) Déterminer les probabilités

Donc nous devons maintenant déterminer deux probabilités pour N-i même :

1. 
2. 

Le premier mandat

Le premier terme, représente la probabilité d'obtenir une permutation avec i transpositions d'identité. Cela s'avère être binomial puisque pour chaque itération de la boucle for :

• Le résultat est indépendant des résultats qui le précèdent, et
• La probabilité de créer une transposition d'identité est la même, à savoir 1/N .

Ainsi, pour N essais, la probabilité d'obtenir i les transpositions d'identité est :

                      ![](https://i.stack.imgur.com/9t2yi.png)

Le deuxième mandat

Donc, si vous êtes arrivés jusqu'ici, nous avons réduit le problème à trouver para N - i même. Cela représente la probabilité d'obtenir une permutation d'identité étant donné i des transpositions sont des identités. J'utilise une approche de comptage naïve pour déterminer le nombre de façons d'obtenir la permutation d'identité sur le nombre de permutations possibles.

Considérons d'abord les permutations (n, m) y (m, n) équivalent. Alors, soit M soit le nombre de permutations non-identiques possibles. Nous utiliserons fréquemment cette quantité.

                              ![](https://i.stack.imgur.com/AvSD7.png)

Le but ici est de déterminer le nombre de façons dont une collection de transpositions peut être combinée pour former la permutation d'identité. Je vais essayer de construire la solution générale à côté d'un exemple de N = 4 .

---

Considérons le N = 4 cas avec toutes les transpositions d'identité ( c'est-à-dire i = N = 4 ). Soit X représentent une transposition d'identité. Pour chaque X il y a N possibilités (elles sont : n = m = 0, 1, 2, ... , N - 1 ). Il existe donc N^i = 4^4 possibilités pour réaliser la permutation d'identité. Pour être complet, nous ajoutons le coefficient binomial, C(N, i) pour considérer l'ordre des transpositions d'identité (ici, il est juste égal à 1). J'ai essayé de représenter cela ci-dessous avec la disposition physique des éléments en haut et le nombre de possibilités en bas :

I  =  _X_   _X_   _X_   _X_
       N  *  N  *  N  *  N  * C(4, 4) => N^N * C(N, N) possibilities

Maintenant, sans substituer explicitement N = 4 y i = 4 nous pouvons examiner le cas général. En combinant ce qui précède avec le dénominateur trouvé précédemment, nous trouvons :

                          ![](https://i.stack.imgur.com/aaUPq.png)

C'est intuitif. En fait, toute autre valeur que 1 devrait probablement vous alarmer. Réfléchissez-y : on nous donne la situation dans laquelle tous les membres de la famille N Les transpositions sont dites identitaires. Quelle est la probabilité que le tableau soit inchangé dans cette situation ? Clairement, 1 .

---

Maintenant, encore une fois pour N = 4 considérons 2 transpositions d'identité ( c'est-à-dire i = N - 2 = 2 ). Par convention, nous placerons les deux identités à la fin (et tiendrons compte de l'ordre plus tard). Nous savons maintenant que nous devons choisir deux transpositions qui, une fois composées, deviendront la permutation d'identité. Plaçons un élément quelconque au premier emplacement, appelons-le t1 . Comme indiqué ci-dessus, il existe M possibilités en supposant t1 n'est pas une identité (elle ne peut pas l'être puisque nous en avons déjà placé deux).

I  =  _t1_   ___   _X_   _X_
       M   *  ?  *  N  *  N

Le seul élément restant qui pourrait être placé en deuxième position est l'inverse de t1 qui est en fait t1 (et c'est la seule par l'unicité de l'inverse). Nous incluons à nouveau le coefficient binomial : dans ce cas, nous avons 4 emplacements ouverts et nous cherchons à placer 2 permutations d'identité. De combien de façons pouvons-nous le faire ? 4 choisir 2.

I  =  _t1_   _t1_   _X_   _X_ 
       M   *  1   *  N  *  N  * C(4, 2) => C(N, N-2) * M * N^(N-2) possibilities

En regardant à nouveau le cas général, tout cela correspond à :

                      ![](https://i.stack.imgur.com/ijV3f.png)

---

Enfin, nous avons le N = 4 cas sans transposition d'identité ( c'est-à-dire i = N - 4 = 0 ). Comme il y a beaucoup de possibilités, cela commence à devenir délicat et nous devons faire attention à ne pas compter deux fois. Nous commençons de la même manière en plaçant un seul élément au premier endroit et en travaillant sur les combinaisons possibles. Prenons d'abord la plus facile : la même transposition 4 fois.

I  =  _t1_   _t1_   _t1_   _t1_ 
       M   *  1   *  1   *  1   => M possibilities

Considérons maintenant deux éléments uniques t1 y t2 . Hay M possibilités pour t1 et seulement M-1 possibilités pour t2 (depuis t2 ne peut être égal à t1 ). Si nous épuisons tous les arrangements, il nous reste les modèles suivants :

I  =  _t1_   _t1_   _t2_   _t2_ 
       M   *  1   *  M-1 *  1   => M * (M - 1) possibilities   (1)st

   =  _t1_   _t2_   _t1_   _t2_
       M   *  M-1 *  1   *  1   => M * (M - 1) possibilities   (2)nd

   =  _t1_   _t2_   _t2_   _t1_
       M   *  M-1 *  1   *  1   => M * (M - 1) possibilities   (3)rd

Considérons maintenant trois éléments uniques, t1 , t2 , t3 . Plaçons t1 d'abord et ensuite t2 . Comme d'habitude, nous avons :

I  =  _t1_   _t2_   ___   ___ 
       M   *  ?   *  ?  *  ?  

Nous ne pouvons pas encore dire combien de possibles t2 Il n'y en a pas encore, et nous verrons pourquoi dans une minute.

Nous plaçons maintenant t1 en troisième position. Avis, t1 doit aller là, car si nous devions aller au dernier endroit, nous ne ferions que recréer la (3)rd arrangement ci-dessus. Le double comptage est mauvais ! Il reste donc le troisième élément unique t3 à la position finale.

I  =  _t1_   _t2_   _t1_   _t3_ 
       M   *  ?   *  1  *   ?  

Alors pourquoi avons-nous dû prendre une minute pour considérer le nombre de t2 de plus près ? Les transpositions t1 y t2 ne peut pas sont des permutations disjointes ( c'est-à-dire ils doivent partager un (et un seul puisqu'ils ne peuvent pas non plus être égaux) de leurs n o m ). La raison en est que si elles étaient disjointes, nous pourrions intervertir l'ordre des permutations. Cela signifie que nous compterions deux fois les (1)st arrangement.

Dites t1 = (n, m) . t2 doit être de la forme (n, x) o (y, m) pour certains x y y afin d'être non disjoints. Notez que x ne peut pas être n o m y y beaucoup ne sont pas n o m . Ainsi, le nombre de permutations possibles qui t2 pourrait être est en fait 2 * (N - 2) .

Donc, revenons à notre mise en page :

I  =  _t1_    _t2_    _t1_   _t3_ 
       M   * 2(N-2) *  1   *  ?  

Ahora t3 doit être l'inverse de la composition de t1 t2 t1 . Faisons-le manuellement :

(n, m)(n, x)(n, m) = (m, x) 

Ainsi, t3 doit être (m, x) . Notez que c'est no disjoint de t1 et n'est pas égal à l'un ou l'autre t1 o t2 il n'y a donc pas de double compte pour ce cas.

I  =  _t1_    _t2_    _t1_   _t3_ 
       M   * 2(N-2) *  1  *   1    => M * 2(N - 2) possibilities   

Enfin, en mettant tout ça ensemble :

        ![](https://i.stack.imgur.com/8Ab3p.png)

---

4) Mettre tout en place

Alors c'est tout. Travaillez à l'envers, en substituant ce que nous avons trouvé dans la somme originale donnée à l'étape 2. J'ai calculé la réponse à la question N = 4 le cas ci-dessous. Il correspond très bien au nombre empirique trouvé dans une autre réponse !

         N  =  4
         M  =  6   \_\_\_\_\_\_\_\_\_ \_\_\_\_\_\_\_\_\_\_\_\_\_ \_\_\_\_\_\_\_\_\_
                  | Pr(K\_i) | Pr(A | K\_i) | Product | 
         \_\_\_\_\_\_\_\_\_|\_\_\_\_\_\_\_\_\_|\_\_\_\_\_\_\_\_\_\_\_\_\_|\_\_\_\_\_\_\_\_\_|
        |         |         |             |         |
        |  i = 0  |  0.316  |  120 / 1296 |  0.029  |
        |\_\_\_\_\_\_\_\_\_|\_\_\_\_\_\_\_\_\_|\_\_\_\_\_\_\_\_\_\_\_\_\_|\_\_\_\_\_\_\_\_\_|
        |         |         |             |         |
        |  i = 2  |  0.211  |    6 / 36   |  0.035  |
        |\_\_\_\_\_\_\_\_\_|\_\_\_\_\_\_\_\_\_|\_\_\_\_\_\_\_\_\_\_\_\_\_|\_\_\_\_\_\_\_\_\_|
        |         |         |             |         |
        |  i = 4  |  0.004  |    1 / 1    |  0.004  |
        |\_\_\_\_\_\_\_\_\_|\_\_\_\_\_\_\_\_\_|\_\_\_\_\_\_\_\_\_\_\_\_\_|\_\_\_\_\_\_\_\_\_|
                            |             |         |
                            |     Sum:    |  0.068  |
                            |\_\_\_\_\_\_\_\_\_\_\_\_\_|\_\_\_\_\_\_\_\_\_|

Correctness

Ce serait cool s'il y avait un résultat dans la théorie des groupes à appliquer ici - et peut-être qu'il y en a un ! Cela permettrait certainement de faire disparaître complètement tout ce comptage fastidieux (et de raccourcir le problème en quelque chose de beaucoup plus élégant). J'ai arrêté de travailler à N = 4 . Pour N > 5 ce qui est donné ne donne qu'une approximation (à quel point, je n'en suis pas sûr). La raison en est assez claire si l'on y réfléchit : par exemple, étant donné que N = 8 transpositions, il existe clairement des moyens de créer l'identité avec cuatro des éléments uniques qui ne sont pas comptabilisés ci-dessus. Le nombre de façons devient apparemment plus difficile à compter à mesure que la permutation s'allonge (pour autant que je puisse le dire...).

Quoi qu'il en soit, je ne pourrais certainement pas faire quelque chose comme ça dans le cadre d'un entretien. J'irais jusqu'à l'étape du dénominateur si j'avais de la chance. Au-delà de ça, ça semble assez méchant.

Answer 2

Je suis très curieux de savoir pourquoi ces personnes posent des questions si étranges sur les probabilités ?

Les questions de ce type sont posées parce qu'elles permettent à l'enquêteur de se faire une idée de l'attitude de la personne interrogée.

• capacité à lire du code (un code très simple mais au moins quelque chose)
• capacité à analyser un algorithme pour identifier le chemin d'exécution
• compétences pour appliquer la logique afin de trouver les résultats possibles et les cas limites
• des compétences en matière de raisonnement et de résolution de problèmes au fur et à mesure qu'ils travaillent sur le problème.
• compétences en matière de communication et de travail - posent-ils des questions ou travaillent-ils de manière isolée sur la base des informations dont ils disposent ?

... et ainsi de suite. La clé pour avoir une question qui expose ces attributs de la personne interrogée est d'avoir un morceau de code qui est faussement simple. Cela permet de démasquer les imposteurs : le non-codeur est bloqué ; l'arrogant saute à la mauvaise conclusion ; l'informaticien paresseux ou médiocre trouve une solution simple et arrête de chercher. Souvent, comme on dit, l'important n'est pas d'obtenir la bonne réponse, mais d'impressionner par son processus de réflexion.

---

Je vais tenter de répondre à la question, moi aussi. Lors d'un entretien, je m'expliquerai plutôt que de fournir une réponse écrite d'une ligne. En effet, même si ma "réponse" est fausse, je suis capable de faire preuve de logique.

A restera le même - c'est-à-dire les éléments dans les mêmes positions - lorsque

• m == n à chaque itération (de sorte que chaque élément ne s'échange qu'avec lui-même) ; ou
• tout élément qui est permuté est replacé à sa position initiale

Le premier cas est le cas "simple" que duedl0r donne, le cas où le tableau n'est pas modifié. Cela pourrait être la réponse, car

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

si le tableau change à i = 1 et revient ensuite à i = 2 il est dans l'état d'origine mais il n'est pas "resté le même" - il a été changé, puis changé à nouveau. C'est peut-être une technique d'intello.

Ensuite, si l'on considère la probabilité que des éléments soient échangés et rééchangés, je pense que ce calcul est au-dessus de ma tête lors d'un entretien. La considération évidente est qu'il ne doit pas nécessairement s'agir d'un échange - échange retour, il pourrait tout aussi bien s'agir d'un échange entre trois éléments, échangeant 1 et 2, puis 2 et 3, 1 et 3 et enfin 2 et 3. En outre, il pourrait y avoir des échanges entre 4, 5 éléments ou plus qui sont "circulaires" comme ceci.

En fait, plutôt que de considérer les cas où le tableau est inchangé, il peut être plus simple de considérer les cas où il est es changé. Examinez si ce problème peut être mis en correspondance avec une structure connue telle que Le triangle de Pascal .

---

C'est un problème difficile. Je suis d'accord pour dire qu'il est trop difficile à résoudre lors d'un entretien, mais cela ne signifie pas qu'il est trop difficile à poser lors d'un entretien. Le mauvais candidat n'aura pas de réponse, le candidat moyen devinera la réponse évidente, et le bon candidat expliquera pourquoi le problème est trop difficile à résoudre.

Je considère qu'il s'agit d'une question "ouverte" qui permet à l'interviewer de mieux connaître le candidat. C'est pourquoi, même si elle est trop difficile à résoudre au cours d'un entretien, c'est une question à laquelle il faut répondre. bon Question à poser lors d'un entretien. Poser une question ne se limite pas à vérifier si la réponse est bonne ou mauvaise.

Answer 3

Le code C ci-dessous permet de compter le nombre de valeurs du 2N-tuple d'indices que rand peut produire et de calculer la probabilité. En commençant avec N = 0, il montre des comptes de 1, 1, 8, 135, 4480, 189125, et 12450816, avec des probabilités de 1, 1, .5, .185185, .0683594, .0193664, et .00571983. Les comptes n'apparaissent pas dans le Encyclopédie des suites entières Donc, soit mon programme a un bug, soit il s'agit d'un problème très obscur. Si c'est le cas, le problème n'est pas destiné à être résolu par un candidat à un emploi, mais à exposer certains de ses processus de pensée et sa façon de gérer la frustration. Je ne le considérerais pas comme un bon problème d'entretien.

#include <inttypes.h>
#include <math.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>

#define swap(a, b)  do { int t = (a); (a) = (b); (b) = t; } while (0)

static uint64_t count(int n)
{
    // Initialize count of how many times the original order is the result.
    uint64_t c = 0;

    // Allocate space for selectors and initialize them to zero.
    int *r = calloc(2*n, sizeof *r);

    // Allocate space for array to be swapped.
    int *A = malloc(n * sizeof *A);

    if (!A || !r)
    {
        fprintf(stderr, "Out of memory.\n");
        exit(EXIT_FAILURE);
    }

    // Iterate through all values of selectors.
    while (1)
    {
        // Initialize A to show original order.
        for (int i = 0; i < n; ++i)
            A[i] = i;

        // Test current selector values by executing the swap sequence.
        for (int i = 0; i < 2*n; i += 2)
        {
            int m = r[i+0];
            int n = r[i+1];
            swap(A[m], A[n]);
        }

        // If array is in original order, increment counter.
        ++c;    // Assume all elements are in place.
        for (int i = 0; i < n; ++i)
            if (A[i] != i)
            {
                // If any element is out of place, cancel assumption and exit.
                --c;
                break;
            }

        // Increment the selectors, odometer style.
        int i;
        for (i = 0; i < 2*n; ++i)
            // Stop when a selector increases without wrapping.
            if (++r[i] < n)
                break;
            else
                // Wrap this selector to zero and continue.
                r[i] = 0;

        // Exit the routine when the last selector wraps.
        if (2*n <= i)
        {
            free(A);
            free(r);
            return c;
        }
    }
}

int main(void)
{
    for (int n = 0; n < 7; ++n)
    {
        uint64_t c = count(n);
        printf("N = %d:  %" PRId64 " times, %g probabilty.\n",
            n, c, c/pow(n, 2*n));
    }

    return 0;
}

Answer 4

Le comportement de l'algorithme peut être modélisé comme une Chaîne de Markov sur le groupe symétrique S _N .

Principes de base

El N éléments du tableau A peuvent être organisées en N ! différentes permutations. Numérotons ces permutations de 1 à N !, par exemple par ordre lexicographique. Ainsi, l'état du tableau A à tout moment dans l'algorithme peut être entièrement caractérisé par le nombre de permutations.

Par exemple, pour N \= 3, une numérotation possible de toutes les 3 ! = 6 permutations pourrait être :

1. a b c
2. a c b
3. b a c
4. b c a
5. c a b
6. c b a

Probabilités de transition entre états

A chaque étape de l'algorithme, l'état de A soit reste le même, soit passe d'une de ces permutations à une autre. Nous sommes maintenant intéressés par les probabilités de ces changements d'état. Appelons Pr( i j ) la probabilité que l'état change de permutation i à la permutation j en une seule itération de la boucle.

Comme nous choisissons m y n de manière uniforme et indépendante dans l'intervalle [0, N -1], il y a N ² résultats possibles, chacun d'entre eux étant également probable.

Identité

Pour N de ces résultats m \= n se maintient, il n'y a donc pas de changement dans la permutation. Par conséquent,

.

Transpositions

Les autres N ² - N sont des transpositions, c'est-à-dire que deux éléments échangent leurs positions et que la permutation change donc. Supposons que l'une de ces transpositions échange les éléments en position x y y . Il y a deux cas de figure où cette transposition peut être générée par l'algorithme : soit m = x , n = y o m = y , n = x . Ainsi, la probabilité pour chaque transposition est de 2 / N ².

Comment cela se rapporte-t-il à nos permutations ? Appelons deux permutations i y j voisins si et seulement si il existe une transposition qui transforme i en j (et vice versa). Nous pouvons alors conclure :

Matrice de transition

Nous pouvons organiser les probabilités Pr( i j ) dans une matrice de transition P [0,1] N !× N ! . Nous définissons

p _ij \= Pr( i j ),

où p _ij est l'entrée dans le i -ème ligne et j -ème colonne de P . Notez que

Pr( i j ) = Pr( j i ),

ce qui signifie P est symétrique.

Le point clé maintenant est l'observation de ce qui se passe lorsque nous multiplions P par lui-même. Prenez n'importe quel élément p (2) _{<em>ij </em>} de P ² :

Le produit Pr( i k ) - Pr( k j ) est la probabilité qu'en partant de la permutation i nous passons en permutation k en une étape, et passer à la permutation j après une autre étape ultérieure. Somme de toutes les permutations intermédiaires k nous donne donc la probabilité totale de en passant de i a j en 2 étapes .

Cet argument peut être étendu aux puissances supérieures de P . Une conséquence particulière est la suivante :

p ( N ) _{<em>ii </em>} est la probabilité de revenir à la permutation i après N étapes, en supposant que nous avons commencé à la permutation i .

Exemple

Jouons à ce jeu avec N \= 3. Nous avons déjà une numérotation pour les permutations. La matrice de transition correspondante est la suivante :

Multiplication de P avec lui-même donne :

Une autre multiplication donne :

Tout élément de la diagonale principale nous donne la probabilité recherchée, qui est de 15 / ₈₁ o 5 / ₂₇ .

Discussion

Bien que cette approche soit mathématiquement saine et puisse être appliquée à toute valeur de N il n'est pas très pratique sous cette forme. La matrice de transition P a N !² entrées, ce qui devient très vite énorme. Même pour N \= 10, la taille de la matrice dépasse déjà 13 trillions d'entrées. Une implémentation naïve de cet algorithme semble donc infaisable.

Cependant, par rapport à d'autres propositions, cette approche est très structurée et ne nécessite pas de dérivations complexes au-delà de la détermination des permutations voisines. J'espère que ce caractère structuré pourra être exploité pour trouver un calcul beaucoup plus simple.

Par exemple, on pourrait exploiter le fait que tous les éléments diagonaux de toute puissance de P sont égales. En supposant que nous pouvons facilement calculer la trace de P N la solution est alors simplement tr( P N ) / N !. La trace de P N est égal à la somme des N -puissances de ses valeurs propres. Donc si nous avions un algorithme efficace pour calculer les valeurs propres de P nous serions prêts. Je n'ai pas poussé l'exploration plus loin que le calcul des valeurs propres jusqu'à N \= 5, cependant.

Answer 5

Il est facile d'observer les limites 1/n n <= p <= 1/n.

Voici une idée incomplète pour montrer une borne supérieure inverse-exponentielle.

Vous tirez 2n fois des numéros parmi {1,2, ,n}. Si l'un d'entre eux est unique (il apparaît exactement une fois), le tableau sera définitivement modifié, car l'élément est parti et ne peut pas revenir à sa place initiale.

La probabilité qu'un nombre fixe soit unique est 2n * 1/n * (1-1/n)^(2n-1)=2 * (1-1/n)^(2n-1), soit asymptotiquement 2/e. 2 2n parce que vous choisissez à quel essai vous l'obtenez, 1/n que vous l'obtenez à cet essai, (1-1/n)^(2n-1) que vous ne l'avez pas obtenu aux autres essais].

Si les événements étaient indépendants, vous obtiendriez que la probabilité que tous les nombres soient non uniques est (2/e 2 )^n, ce qui signifierait que p <= O((2/e 2 )^n). Malheureusement, ils ne sont pas indépendants. Je pense que la limite peut être démontrée avec une analyse plus sophistiquée. Le mot clé est "problème des boules et des bacs".