Qual é a probabilidade de um determinado bit após um embaralhamento?

Question

Deixei $S = \{b_1, b_2 ,...,b_n\}$ ser uma sequência de bits de tamanho $n$, $b_i \in \{0, 1\}$

Deixei $f$ser um algoritmo de embaralhamento simples (você pode considerar Fisher – Yates como um exemplo).

Nós temos $$f(S) = S^{\prime} = \{b_1^{\prime}, b_2^{\prime} ,...,b_n^{\prime}\}$$

Qual é a probabilidade de $$b_i^{\prime} = b_i ~|~ i \in [n]$$

---

Exemplo:

E se $[0, 1, 1, 0] \rightarrow [0, 0, 1, 1]$ ... Qual é a probabilidade de que o último bit "$1$"que observo aqui após embaralhar é verdadeiro na sequência original antes de embaralhar?

A última parte aqui é apenas um exemplo. Pode ser qualquer bit.

Answer 1

Parece que você está apenas falando sobre permutações aleatórias, e o algoritmo de embaralhamento específico não faz diferença. Nesse caso, a probabilidade de que um determinado bit termine em uma posição específica é a mesma para todos os bits. Se houver$n$ $1$-bits e $m$ $0$-bits, então a probabilidade de que o bit em uma determinada posição seja $1$ depois que o shuffle é $\frac n{n+m}$. Por outro lado, a probabilidade de que uma posição selecionada aleatoriamente antes do embaralhamento tenha um$1$ nele também está $\frac n{n+m}$, e uma vez que os eventos são independentes, a probabilidade de que a posição contém $1$ antes e depois do embaralhamento é $\frac{n^2}{(n+m)^2}$. Da mesma forma, a probabilidade de que uma posição aleatória contém$0$ ambas as vezes é $\frac{m^2}{(n+m)^2}$, então a probabilidade de que contenha o mesmo número nas duas vezes é $$\frac{n^2+m^2}{(n+m)^2}$$.

Answer 2

Não tenho certeza se entendi totalmente a pergunta, mas o código Python no link fornecido mostra aleatoriamente um número inteiro estritamente entre o bit atual e o último (incluindo) para troca, exceto a primeira troca, que acontece wp$1$.

Acho que encontrei uma solução para um problema mais simples, mas você deve conseguir estendê-la para o seu. Vamos supor que os dois últimos bits em$S$ está $11$, então, após a primeira troca, você ainda tem $1$. Você pode condicionar o número total de trocas com o último bit. Os dois primeiros dois casos não são swaps e exatamente um swap. Se não houvesse trocas,$P(S_n =1|no \ swaps)=1$ e a probabilidade de nenhuma troca é $\frac{1}{n-1}$. Para o segundo caso, se não sabemos nada sobre os valores dos bits nas posições em$S$, deixei $\sigma$ seja a parte de $1$ dentro $S$, então $P(S_n =1|1 \ swap)=\sigma$, o valor do bit naquele local específico. A probabilidade de exatamente uma troca é\begin{align} P(swap) &= \frac{1}{n-1} + \frac{1}{2}\times \frac{1}{n-1} + \frac{1}{3}\times \frac{1}{n-1} + \ldots \\&= \frac{1}{n-1} \bigg(1+\frac{1}{2}+ \ldots + \frac{1}{n-2}\bigg) \approx\frac{\log(n-2)}{n-1} \end{align}