Probabilidade de encontrar a mediana com espaço finito

9

Este é um desdobramento desta pergunta do StackOverflow

Suponha que você tenha um número fixo k de locais de armazenamento e espaço para dois contadores. Você receberá itens n em ordem aleatória (todas as permutações dos itens n são igualmente prováveis). Depois de receber cada item, você pode armazená-lo em um dos locais k (descartando um dos valores armazenados anteriormente) ou descartar o item. Você também pode incrementar ou decrementar qualquer um dos contadores. Qualquer item descartado não pode ser recuperado.

As perguntas são

  1. Qual é a estratégia que maximiza sua probabilidade de encontrar a mediana exata?
  2. Qual é essa probabilidade?

Obviamente, se k > n / 2 , podemos encontrar a mediana. Em geral, parece que a mesma estratégia de tentar manter o número de valores altos descartados igual ao número de valores baixos descartados deve ser ótima, mas não tenho certeza de como prová-lo, nem como descobrir a probabilidade de encontrar a mediana.

Também é interessante o caso em que não sabemos n , mas sabemos a distribuição de probabilidade de n .

Edit: Suponha por enquanto que os valores são distintos (sem duplicatas). Entretanto, se você puder resolver o caso não distinto também, isso seria impressionante.

    
por deinst 31.07.2010 в 16:29
fonte

2 respostas

5

Munro e Paterson estudaram essencialmente esse problema em seu artigo Seleção e classificação com armazenamento limitado . Eles mostram que seu algoritmo requer que k = Ω (√n) tenha sucesso com probabilidade constante e que isso é assintoticamente ideal apelando para resultados básicos sobre caminhadas aleatórias unidimensionais.

Se eu quisesse provar otimalidade absoluta, a primeira coisa que eu tentaria seria considerar um algoritmo arbitrário A e então parear sua execução com um algoritmo A 'que, na primeira vez em que A se desvia seu algoritmo, o seu algoritmo faria em vez disso e, em seguida, tenta seguir A, tanto quanto possível.

    
por user382751 31.07.2010 / 19:48
fonte
0

Um palpite: descarte o elemento que está mais longe da média dos valores armazenados no momento.

A comparação com a mediana atual não funciona se a distribuição de valores for multimodal e obtivermos valores de um modo não dominante primeiro.

    
por Mau 31.07.2010 / 16:39
fonte