A mediana da distribuição com restrição de memória

Question

Tarefa

Eu quero aproximado da mediana de uma distribuição dada $D$ que eu possa amostra.

Um algoritmo simples para isso, usando $n$ amostras, é:

samples = [D.sample() for i in range(n)] # generate n samples from D
sort(samples)
return samples[n/2]

No entanto, eu estou procurando um algoritmo que requer menos de $S(n)$ espaço.

Ideias

Eu olhei para estes algoritmos:

• A mediana das medianas:Necessidades $S(n)$ o espaço, portanto ele não funciona para mim.
• Randomizados mediana:Parece que este pode ser facilmente generalizado para um algoritmo que utiliza $O(n^{3/4})$ espaço.

Existem outros algoritmos que utilizam menos de $S(n)$ o espaço que poderia resolver meu problema?Em particular, eu estava pensando, pode ser que exista um algoritmo que usa $S(m)$ espaço de geração de lotes de amostras de $D$ tamanho $m$...

Detalhes

• Idealmente, eu estou procurando uma referência a um algoritmo que também inclui a análise (probabilidade de sucesso, espera-tempo de execução, etc.).
• Na verdade, eu preciso de um algoritmo para estimar $D$'s $p$-ésimo percentil para um determinado $p$, mas eu estou esperando mais mediana-encontrar algoritmos podem ser generalizadas para isso.
• Eu gostaria de obter a mesma precisão como o simples algoritmo mostrado acima.Uma maneira de conseguir isso é usando um algoritmo cuja saída de distribuição é o mesmo que o algoritmo de amostragem (mas, talvez, o novo algoritmo pode falhar em casos raros)

Answer 1

Com certeza, você definitivamente pode conseguir isso usando um pouco mais de tempo de execução.Aqui é conceptualmente simples abordagem, que pode não ser o ideal, mas vai começar e é, provavelmente, muito bom:

Usar o binário de pesquisa para encontrar aproximado da mediana $m$.Como você sabe se é candidato $m$ é muito grande ou muito pequeno?Exemplo $n$ momentos da distribuição, a conta de quantas vezes as amostras são $\ge m$, e compare-contagem $n'/2$.Isso pode ser feito com $S(1)$ espaço.

Em seguida, a tecla questão torna-se:como podemos escolher $n$, para controlar a probabilidade de erro?Uma abordagem simples é escolher $n$ para ser suficientemente maior do que $n$ que a probabilidade de erro em cada iteração da pesquisa binária é $t$ menor do que a probabilidade de erro ao utilizar o $n$ amostras, onde $t$ é o número de iterações da busca binária necessário para atingir a precisão desejada.Em seguida, uma união vinculados garante que isso vai corresponder a sua exatidão condições.

Infelizmente, a sua precisão condição é um pouco difícil de trabalhar, quando não sabemos nada sobre a distribuição de dados, como o rigor da amostra, a mediana pode ser arbitrariamente ruim.Por exemplo, considere uma distribuição saídas $0$ com probabilidade $(1-\epsilon)/2$ e $100$ com probabilidade $(1+\epsilon)/2$.Em seguida, a amostra mediana é igualmente propensos a ser 0 ou 100, considerando que a distribuição mediana é 100, assim, o erro médio da amostra, a mediana é de cerca de 50 (a menos que você está desenhando $\gg 1/\epsilon^2$ amostras).Isso é particularmente desagradável de distribuição, e vai ser difícil para se trabalhar.Mas se você assumir que a distribuição é aproximadamente Gaussiana (dizem), com desvio padrão $\sigma$, e , em seguida, o erro da amostra, mediana, com $n$ amostras, é de cerca de $1.25 \sigma/\sqrt{n}$.Assim, o algoritmo acima pode ser usado onde definimos $t \approx \lg (\sqrt{n}/1.25)$ e nós conjunto $n' \approx n t^2$.

Essa é uma abordagem simples.Provavelmente, você pode fazer melhor.Você pode gostar de olhar para cima streaming de algoritmos para o cálculo da mediana, e como eles enfrentam o problema que você está trabalhando com:dado um número ilimitado de amostras da distribuição, mas apenas uma quantidade limitada de espaço, qual é a melhor estimativa que podemos obter para a mediana?Por exemplo, aqui está um algoritmo simples:a primeira camada repetidamente leva três amostras e saídas a mediana dos três;a segunda camada repetidamente leva três números da primeira camada e saídas a mediana dos três;e assim por diante.Após logarítmica número de camadas, você obter uma aproximação razoável para a mediana.Existe toda uma literatura sobre este assunto, e você deve ser capaz de encontrar muitas mais.