Defina a invariância das coincidências. Exemplifique.

Passo 1

O enunciado pede para definirmos o que é a invariância das coincidências no contexto de probabilidade (mais precisamente no problema das permutações) e apresentar um exemplo. Para isso, vamos usar conceitos de variáveis indicadoras e expectativa em permutações aleatórias.

Passo 2

Definimos o número de coincidências (ou pontos fixos) em uma permutação aleatória de n\) elementos como \[X = \sum_{k=1}^{n} I_k,
onde
I_k = \begin{cases} 1, &\text{se o elemento }k\text{ for enviado de volta para a posição }k,\\\\ 0, &\text{caso contrário.} \end{cases}çãá
A invariância das coincidências é o fato de que a expectativa de X\] não depende de \(n; isto é,
\mathbb{E}[X]=1 \quad\text{para todo }n\ge1.

Passo 3

Para ver por que \mathbb{E}[X]=1 seja independente de n, usamos a linearidade da esperança:
\mathbb{E}[X] = \mathbb{E}\Bigl[\sum_{k=1}^n I_k\Bigr] = \sum_{k=1}^n \mathbb{E}[I_k].
Como em uma permutação aleatória a chance de o elemento k ficar fixo na posição k é \tfrac{1}{n}, temos
\mathbb{E}[I_k] = 1\cdot\frac{1}{n} + 0\cdot\Bigl(1-\frac{1}{n}\Bigr) = \frac{1}{n}.
Logo
\mathbb{E}[X] = \sum_{k=1}^n \frac{1}{n} = n\cdot\frac{1}{n} =1.

Passo 4

Exemplo clássico: suponha que você tenha n cartas e n envelopes, cada envelope rotulado de 1 a n. As cartas são embaralhadas aleatoriamente e colocadas uma em cada envelope. A variável X conta quantas cartas acabam no envelope cujo rótulo coincide com o seu número. A invariância diz que, não importa o tamanho de n, em média você terá exatamente uma carta no envelope certo:
\mathbb{E}[X]=1.

Resposta

A invariância das coincidências afirma que, ao permutar aleatoriamente n objetos, a expectativa do número de elementos que permanecem em sua posição original (coincidências) é sempre
\mathbb{E}[X]=1,
independente de n.
Exemplo: ao distribuir n cartas aleatoriamente em n envelopes rotulados, espera-se, em média, uma carta no envelope que lhe corresponde.

Exercícios relacionados