Qual dessas duas seqüências é aleatória e qual não é?

Nós deixamos $\alpha = \alpha_1\alpha_2\alpha_3\ldots$ uma sequência aleatória infinita (sob a medida uniforme) em que $\alpha_i$ talvez $1$ ou $0$ e defina a função booleana $B_k$ :

B_{k} (α_{1} \dots α_{k}) = {\begin{cases} 1 if at least ⌈ k / 2 ⌉ of its inputs are 1 \\ 0 otherwise \end{cases}

$B_k(\alpha_1\ldots\alpha_k) = \begin{cases} 1 \text{ if at least } \lceil k/2 \rceil \text{ of its inputs are } 1 \\ 0 \text{ otherwise} \end{cases}$

Em seguida, definimos duas sequências:

B_{3} (α_{1} α_{2} α_{3}) B_{3} (α_{4} α_{5} α_{6}) B_{3} (α_{7} α_{8} α_{9}) \dots

$B_3(\alpha_1\alpha_2\alpha_3)B_3(\alpha_4\alpha_5\alpha_6)B_3(\alpha_7\alpha_8\alpha_9)\ldots$

B_{4} (α_{1} α_{2} α_{3} α_{4}) B_{4} (α_{5} α_{6} α_{7} α_{8}) B_{4} (α_{9} α_{10} α_{11} α_{12}) \dots

$B_4(\alpha_1\alpha_2\alpha_3\alpha_4)B_4(\alpha_5\alpha_6\alpha_7\alpha_8)B_4(\alpha_9\alpha_{10}\alpha_{11}\alpha_{12})\ldots$

Qual dessas duas seqüências é ( algoritmicamente ) aleatória e por quê? Devo observar que, aparentemente, existe um fato teórico da medida que revela qual não é aleatório.

probability-theory randomness Newb
fonte

E se

k = 2 n + 1

$k=2n+1$ então

P (B_{k} = 1) < P (B_{k} = 0)

$P(B_k = 1) < P(B_k = 0)$ . Isso não é suficiente, informalmente?

OJFord 10/06/14

talvez um relacionadas questão

Nikos M.

Não é cada

B_{k}

$B_k$ sequência igual à sequência de soma parcial de

a_{i}

$a_i$ 's (ou mais corretamente a diferença de 2 seqüências de soma parcial)?

Nikos M.

também posso dar outro tipo de resposta em termos de processo sigal. Cada

B_{k}

$B_k$ A sequência atua como filtro passa-baixo (filtrando as altas frequências) como resultado, porque o ruído aleatório tem especialmente as altas frequências, cada

B_{k}

$B_k$ deve ser progressivamente menos aleatório (eventualmente igual a uma sequência de 1s).

Nikos M.

@Newb De acordo com o artigo da Wikipedia que você vincula, existem várias possibilidades e o padrão é uma convenção de campo. Você deve tomar cuidado ao usar essas convenções aqui sem esclarecimentos - nem todo leitor é especialista em domínio.

Raphael

Respostas:

A segunda sequência não é aleatória. Deixei $\alpha_1,\alpha_2,\alpha_3,\alpha_4$ seja aleatório, iid Bernoulli $1/2$ variáveis aleatórias. Deixei $\beta = B_4(\alpha_1 \alpha_2 \alpha_3 \alpha_4)$ .

Qual é a distribuição da variável aleatória $\beta$ ? Responda: $\beta=1$ se pelo menos dois dos $\alpha$ são $1$ , tão $\Pr[\beta=1] = 11/16$ .

Em outras palavras, $\beta$ é inclinado para $1$ . Conclui-se que a segunda sequência não é algorítmica aleatória: é um conjunto de variáveis aleatórias independentes de Bernoulli com $p=11/16$ , ou seja, o resultado de uma sequência infinita de lançamentos de uma moeda tendenciosa.

DW
fonte

Tudo certo! Isso faz todo o sentido. Obrigado. Você tem algum raciocínio sobre por que a primeira sequência é aleatória?

Newb

Por outro lado, seria porque

B_{3}

$B_3$ é "justo": existem 4 sequências de 3 bits que

B_{3}

$B_3$ mapeia para sequências de 1 e 4 bits que mapeiam para 0, assumindo que a sequência original seja aleatória,

P r [B = 1] = P r [B = 0] = \frac{1}{2}

$Pr[B=1] = Pr[B=0] = \frac12$ .

gardenhead

Eu não concordo com isso, apenas afirma que a variável aleatória

β

$\beta$ não tem probabilidades iguais de p1 e p2. Por que uma variável aleatória com P1 = 1/3 e P0 = 2/3, não é considerada aleatória? Por que os RVs com uma distribuição diferente não são aleatórios (um RV gaussiano não é aleatório, é tendencioso em relação à média)?

precisa

Na verdade eu estou postando uma pergunta (em breve?) Reportar-o relaton entre aleatoriedade probabilística e algorítmica (pela outra pergunta que eu ligado nos comentários)

Nikos M.

Eu acho que você está certo, enquanto ambos são aleatórios em um sentido, algoritmicamente aleatório não é o mesmo que probabilisticamente aleatório. Como não sou especialista em aleatoriedade algorítmica, é verdade que posso dizer. Eu também estaria interessado em elaborar esses pontos.

gardenhead