De forma eficiente a seleção de um subconjunto de tamanho $m$ a partir de um conjunto de tamanho de $n$

Question

Este é um cruzamento post de minha pergunta aqui no matemática.se.

Eu tenho uma lista de $n$ itens e gostaria de seleccionar aleatoriamente um $m$ definir de que forma eficiente (em termos de tempo de complexidade).Além disso, eu quero todos os possíveis subconjuntos a serem selecionados com probabilidade igual.A solução óbvia é escolher aleatoriamente um número inteiro de $1$ para $n$ e escolher o elemento correspondente, em seguida, repita $m$ vezes, não contando o evento no qual a pessoa escolhe e já escolhido o elemento.Isto torna-se cada vez mais ineficiente como $m$ abordagens $n$ assim, para $m>n/2$ não faria sentido, em vez de pegar um $(n-m)$-definir e retornar o seu elogio.

Para valores de $m$ perto $n/2$, uma melhor solução que eu acho que seria considerar cada um dos $n$ elementos e decidir escolher a que elemento ou descartá-lo, a cada vez que atualizar a probabilidade de escolher ou descartar, dependendo do número de elementos escolhidos vs descartada antes.Especificamente, o algoritmo deve ir da seguinte forma (python):

def randomSubset(n,m):
  L = []
  for i in range(n):
    if uniform(0,1)<m/(n-i): L,m = L+[i],m-1
  return L

No entanto, eu estou preocupado com o que isso pode não resultar em cada subconjunto a ser escolhido com igual probabilidade.

Eu tenho duas perguntas.Primeiro, que esse algoritmo escolher subconjuntos com igual probabilidade (se for assim, eu gostaria de uma prova de que ele faz e, se não eu também gostaria de uma prova de que ele não).Segundo, mais amplamente, eu gostaria de saber o que bom que existem soluções para este problema.Claramente se $m< em seguida, o primeiro método é melhor do que o segundo no entanto, em algum ponto, o segundo método (se ele de fato o trabalho) é melhor do que o primeiro.Além disso, uma abordagem completamente diferente, pode ser melhor em geral.

Answer 1

A probabilidade de que o elemento $1$ pertence a uma aleatórios $m$-subconjunto de um $n$-elemento é definido $m/n$.Portanto, você deve incluir $1$ em seu subconjunto com probabilidade $m/n$.

Se você colocar o $1$ em seu subconjunto, então você é deixado com a escolha de um $(m-1)$-subconjunto de um $(n-1)$-conjunto de elementos.

Se você não colocou $1$ em seu subconjunto, então você é deixado com a escolha de um $m$-subconjunto de um $(n-1)$-conjunto de elementos.

Isso significa que você tem um pouco de atualização de seu algoritmo, substituindo $m$ com $m-|L|$.

O algoritmo resultante é um pouco semelhante ao reservatório de amostragem.

Uma terceira abordagem, com algumas semelhanças, é a geração de uma permutação aleatória de $1,\ldots,n$ e selecionar a primeira $m$ entradas.

O lado negativo de todas essas abordagens são que eles são executados em tempo $ heta(n)$, enquanto $m \ll \sqrt{n}$, seu primeiro algoritmo é executado no (esperado) tempo $ il heta(m)$.

Podemos melhorar o $ heta(n)$ tempo de execução da seguinte forma.Nós irá gerar aleatoriamente ordenados $m$-subconjunto dado $m$ índices de $i_1,\ldots,x$, onde $i_j \in \{1,\ldots,n-(j-1)\}$.O $j$'ī esimo elemento do subconjunto será o $i_j$'th menor número de $\{1,\ldots,n\}$ fora os números que não já escolhido.

Para completar a descrição do algoritmo, precisamos resolver o seguinte problema:dado $S \subseteq \{1,\ldots,n\}$ e $i$, encontrar o $i$'ī esimo menor elemento de $\overline{S}$.Podemos assumir que $S$ é armazenado em uma estrutura (tal como um auto-balanceamento de uma árvore binária), que pode eficientemente resposta o seguinte tipo de consulta:dado $x$, como muitos elementos em $S$ são menores do que $x$.Podemos, então, encontrar o $i$'th menor número de $\overline{S}$ usando busca binária.

No geral, este algoritmo é executado em $ il heta(m)$ para todos os valores de $m$, onde o til esconde fatores logarítmica em $n$.(Quando $m \ll \sqrt{n}$ podemos utilizar a sua primeira abordagem, assim, se livrar desta dependência $n$.)