Qual é o valor O para a seleção aleatória ingênua do conjunto finito?

Question

Essa questão sobre obter valores aleatórios de um conjunto finito me fez pensar ...

É bastante comum que as pessoas desejem recuperar x valores únicos de um conjunto de valores y. Por exemplo, posso querer lidar com uma mão de um baralho de cartas. Eu quero 5 cartões e quero que todos sejam únicos.

Agora, posso fazer isso ingênuo, escolhendo um cartão aleatório 5 vezes e tentar novamente cada vez que recebo uma duplicata, até receber 5 cartões. Isso não é tão bom, no entanto, para um grande número de valores de grandes conjuntos. Se eu quisesse 999.999 valores de um conjunto de 1.000.000, por exemplo, esse método fica muito ruim.

A questão é: quão ruim? Estou procurando alguém para explicar um valor o (). Obter o Xésimo Número fará as tentativas de Y ... mas quantos? Eu sei como descobrir isso por um determinado valor, mas existe uma maneira direta de generalizar isso para toda a série e obter um valor o ()?

(A pergunta não é: "Como posso melhorar isso?" Porque é relativamente fácil de corrigir, e tenho certeza de que foi coberto muitas vezes em outros lugares.)

Answer 1

Variáveis

n = a quantidade total de itens no conjunto
m = a quantidade de valores únicos que devem ser recuperados do conjunto de n itens
D (i) = a quantidade esperada de tentativas necessárias para atingir um valor na etapa i
eu = denota uma etapa específica. i ∈ [0, n-1
T (m, n) = quantidade total esperada de tentativas para selecionar M itens exclusivos de um conjunto de n itens usando o algoritmo ingênuo

Raciocínio

O primeiro passo, i = 0, é trivial. Não importa qual valor escolhamos, obtemos um único na primeira tentativa. Por isso:

d (0) = 1

Na segunda etapa, i = 1, pelo menos precisamos 1 tente (a tentativa onde escolhemos um valor exclusivo válido). Além disso, há uma chance de escolhermos o valor errado. Essa chance é (quantidade de itens escolhidos anteriormente)/(quantidade total de itens). Neste caso 1/n. No caso em que escolhemos o item errado, há uma chance de 1/n que possamos escolher o item errado novamente. Multiplicando isso por 1/n, já que essa é a probabilidade combinada de escolhermos errados nas duas vezes, fornece (1/n)². Para entender isso, é útil desenhar um árvore de decisão. Tendo escolhido um item não único duas vezes, há uma probabilidade de fazê-lo novamente. Isso resulta na adição de (1/n)³ para o total de quantidades esperadas de tentativas na etapa i = 1. Cada vez que escolhemos o número errado, há uma chance de escolher o número errado novamente. Isto resulta em:

d (1) = 1 + 1/n + (1/n)² + (1/n)³ + (1/n)⁴ + ...

Da mesma forma, no passo geral I: a chance de escolher o item errado em uma opção é I/N, resultando em:

d (i) = 1 + i/n + (i/n)² + (i/n)³ + (i/n)⁴ + ... =
= soma ((i/n)^k ), onde k ∈ [0, ∞

Isto é um Sequência geométrica E, portanto, é fácil calcular sua soma:

d (i) = (1 - i/n)^-1

A complexidade geral é então calculada somando a quantidade esperada de tentativas em cada etapa:

T (m, n) = soma (d (i)), onde i ∈ [0, m-1] =
= 1 + (1 - 1/n)^-1 + (1 - 2/n)^-1 + (1 - 3/n)^-1 + ... + (1 - (m -1)/n)^-1

Estendendo as frações na série acima por n, obtemos:

T (m, n) = n/n + n/(n-1) + n/(n-2) + n/(n-3) + ... + n/(n-m + 2) + n /(n-m+1)

Podemos usar o fato de que:

n/n ≤ n/(n-1) ≤ n/(n-2) ≤ n/(n-3) ≤ ... ≤ n/(n-m+2) ≤ n/(n-m+1 )

Como a série tem termos m e cada termo satisfaz a desigualdade acima, obtemos:

T (m, n) ≤ n/(n-m + 1) + n/(n-m + 1) + n/(n-m + 1) + n/(n-m + 1) + ... + n/(n-m+ 1)+ n/(n-m+ 1) =
= m*n/(n-m+1)

Pode ser (e provavelmente é) possível estabelecer um limite superior um pouco mais rigoroso usando alguma técnica para avaliar a série em vez de limitar pelo método aproximado de (quantidade de termos) * (maior termo)

Conclusão

Isso significaria que a ordem Big-O é O (m*n/(n-m+1)). Não vejo maneira possível de simplificar essa expressão da maneira como é.

Olhando para o resultado para Verifique se faz sentido, vemos que, se N é constante e M se aproxima cada vez mais de n, os resultados aumentarão rapidamente, uma vez que o denominador fica muito pequeno. É isso que esperaríamos, se, por exemplo, considerarmos o exemplo dado na pergunta sobre a seleção de "999.999 valores de um conjunto de 1.000.000". Se, em vez disso, deixarmos M constante e N crescerá muito, muito grande, a complexidade convergirá para o (m) no limite n → ∞. Isso também é o que esperávamos, pois, ao mesmo tempo em que escolhemos um número constante de itens de um conjunto de tamanhos infinitamente "próximos a", a probabilidade de escolher um valor escolhido anteriormente é basicamente 0. ou seja, precisamos de M tentativas independentemente de n, pois não há não Colisões.

Answer 2

Se você já escolheu eu valoriza, a probabilidade de escolher um novo de um conjunto de valores y é

(y-i)/y.

Portanto, o número esperado de ensaios para obter (i+1) -th elemento é

y/(y-i).

Assim, o número esperado de ensaios para escolher x elemento exclusivo é a soma

 y/y + y/(y-1) + ... + y/(y-x+1)

Isso pode ser expresso usando números harmônicos Como

y (h_y - h_yx).

Na página da Wikipedia, você obtém a aproximação

H_x = ln (x) + gama + o (1/x)

Portanto, o número de ensaios necessários para escolher x elementos exclusivos de um conjunto de elementos y é

y (ln(y) - ln(y-x)) + O(y/(y-x)).

Se precisar, você pode obter uma aproximação mais precisa usando uma aproximação mais precisa para H_x. Em particular, quando X é pequeno, é possível melhorar muito o resultado.

Answer 3

Sua pergunta real é realmente muito mais interessante do que eu respondi (e mais difícil). Eu nunca fui bom em estatísticas (e já faz um tempo desde que fiz), mas intuitivamente, eu diria que a complexidade do tempo de execução desse algoritmo provavelmente seria algo como exponencial. Enquanto o número de elementos escolhidos for pequeno o suficiente em comparação com o tamanho da matriz, a taxa de colisão será tão pequena que estará próxima do tempo linear, mas em algum momento o número de colisões provavelmente crescerá rapidamente e a corrida -Time vai descer o ralo.

Se você deseja provar isso, acho que você teria que fazer algo moderadamente inteligente com o número esperado de colisões em função do número desejado de elementos. Pode ser possível fazer a indução também, mas acho que seguir essa rota exigiria mais inteligência do que a primeira alternativa.

EDIT: Depois de pensar um pouco, aqui está minha tentativa:

Dada uma variedade de m elementos, e procurando por n elementos aleatórios e diferentes. É então fácil ver que quando queremos escolher o io elemento, as chances de escolher um elemento que já visitamos são (i-1)/m. Este é então o número esperado de colisões para essa escolha específica. Para escolher n Elementos, o número esperado de colisões será a soma do número de colisões esperadas para cada escolha. Nós conectamos isso ao Wolfram alfa (soma (i-1)/m, i = 1 a n) e obtemos a resposta (n**2 - n)/2m. O número médio de escolhas para o nosso algoritmo ingênuo é então n + (n**2 - n)/2m.

A menos que minha memória falhe completamente (o que totalmente possível, na verdade), isso dá um tempo de execução média O(n**2).

Answer 4

Se você estiver disposto a assumir que seu gerador de números aleatórios sempre encontrará um valor único antes de voltar a um valor visto anteriormente para um determinado empate, esse algoritmo é O (M^2), onde M é o número de exclusivos valores que você está desenhando.

Portanto, se você estiver desenhando valores M de um conjunto de valores n, o 1º valor exigirá que você desenhe no máximo 1 para obter um valor exclusivo. O segundo requer no máximo 2 (você vê o 1º valor, depois um valor exclusivo), o 3º 3, ... o Mth m. Portanto, no total você precisa 1 + 2 + 3 + ... + m = [m*(m + 1)]/2 = (m^2 + m)/2 desenha. Este é o (m^2).

Sem essa suposição, não tenho certeza de como você pode garantir que o algoritmo será concluído. É bem possível (especialmente com um gerador de números pseudo-aleatórios que pode ter um ciclo), que você continuará vendo os mesmos valores repetidamente e nunca chegará a outro valor único.

== edit ==

Para o caso médio:

No seu primeiro empate, você fará exatamente um empate. No seu segundo empate, você espera fazer 1 (o sorteio bem -sucedido) + 1/n (o sorteio "parcial" que representa sua chance de se repetir) no seu terceiro empate, você espera fazer 1 (o sorteio bem -sucedido) + 2/n (o sorteio "parcial" ...) ... no seu MTH Draw, você espera fazer 1 + (M-1)/N empate.

Assim, você fará 1 + (1 + 1/n) + (1 + 2/n) + ... + (1 + (m-1)/n) se baseia no caso médio.

Isso é igual à soma de i = 0 a (m-1) de [1 + i/n]. Vamos denotar essa soma (1 + i/n, i, 0, m-1).

Então:

sum(1 + i/n, i, 0, m-1) = sum(1, i, 0, m-1) + sum(i/n, i, 0, m-1)
                        = m + sum(i/n, i, 0, m-1)
                        = m + (1/n) * sum(i, i, 0, m-1)
                        = m + (1/n)*[(m-1)*m]/2
                        = (m^2)/(2n) - (m)/(2n) + m 

Abaixamos os termos de ordem baixa e as constantes, e entendemos que isso é O (m^2/n), onde m é o número a ser desenhado e n é o tamanho da lista.

Answer 5

Há um belo algoritmo O (n) para isso. Vai o seguinte. Digamos que você tenha n itens, dos quais deseja escolher M itens. Suponho que a função Rand () produz um número real aleatório entre 0 e 1. Aqui está o algoritmo:

items_left=n
items_left_to_pick=m
for j=1,...,n
    if rand()<=(items_left_to_pick/items_left)
        Pick item j
        items_left_to_pick=items_left_to_pick-1
    end
    items_left=items_left-1
end

Pode-se provar que esse algoritmo realmente escolhe cada subconjunto de itens M com igual probabilidade, embora a prova não seja óbvio. Infelizmente, não tenho uma referência à mão no momento.

Editar A vantagem desse algoritmo é que é necessária apenas a memória O (m) (assumindo que os itens sejam simplesmente inteiros ou podem ser gerados na voação) em comparação com a realização de um shuffle, que leva a memória O (n).

Answer 6

O pior caso desse algoritmo é claramente quando você está escolhendo o conjunto completo de n itens. Isso é equivalente a perguntar: em média, quantas vezes devo rolar um dado N-sideling antes que cada lado subisse pelo menos uma vez?

Resposta: n * h_N, onde h_N é o enésimo número harmônico,

um valor famosamente aproximado por log(N).

Isso significa que o algoritmo em questão é N log N.

Como um exemplo divertido, se você rolar um dado comum de 6 lados até ver um de cada número, levará em média 6 h₆ = 14,7 rolos.

Answer 7

Antes de poder responder a essa pergunta em detalhes, vamos definir a estrutura. Suponha que você tenha uma coleção {a1, a2, ..., e} de n objetos distintos, e deseja escolher objetos distintos desse conjunto, de modo que a probabilidade de um determinado objeto AJ apareça no resultado seja igual a todos os objetos .

Se você já escolheu K itens e escolhe um item radomicamente do conjunto completo {A1, A2, ..., e}, a probabilidade de que o item não tenha sido escolhido antes de IS (nk)/n. Isso significa que o número de amostras que você deve tomar antes de obter um novo objeto é (assumindo a independência da amostragem aleatória) geométrico com parâmetro (nk)/n. Assim, o número esperado de amostras para obter um item extra é N/(NK), que é próximo de 1 se k for pequeno em comparação com n.

Concluindo, se você precisar de objetos únicos, selecionados aleatoriamente, este algoritmo lhe dá

n/n + n/(n-1) + n/(n-2) + n/(n-3) + .... + n/(n- (m-1))

o que, como Alderath mostrou, pode ser estimado por

m*n / (n-m+1).

Você pode ver um pouco mais dessa fórmula: * O número esperado de amostras para obter um novo elemento exclusivo aumenta à medida que o número de objetos já escolhidos aumenta (o que soa lógico). * Você pode esperar tempos de computação muito longos quando M está próximo de n, especialmente se n for grande.

Para obter m membros únicos do conjunto, use uma variante de Algoritmo de David Knuth Para obter uma permutação aleatória. Aqui, assumirei que os N objetos são armazenados em uma matriz.

for i = 1..m
  k = randInt(i, n)
  exchange(i, k)
end

Aqui, Randint amostra um número inteiro de {i, i+1, ... n} e troca vira dois membros da matriz. Você só precisa embaralhar as vezes, então o tempo de computação é O (m), enquanto a memória é O (n) (embora você possa adaptá -lo apenas para salvar as entradas de modo que um [i] <> i, o que daria Você (m) no tempo e na memória, mas com constantes mais altas).

Answer 8

A maioria das pessoas esquece que, se o número já foi executado, também leva um tempo.

O número de tentativas pode, como descrito anteriormente, ser avaliado de:

T(n,m) = n(H(n)-H(n-m)) ⪅ n(ln(n)-ln(n-m))

que vai para n*ln(n) Para valores interessantes de m

No entanto, para cada uma dessas 'tentativas', você terá que fazer uma pesquisa. Isso pode ser simples O(n) Runtro, ou algo como uma árvore binária. Isso lhe dará um desempenho total de n^2*ln(n) ou n*ln(n)^2.

Para valores menores de m (m < n/2), você pode fazer uma aproximação muito boa para T(n,m) usando o HA-Nequação, produzindo a fórmula:

2*m*n/(2*n-m+1)

Como m vai para n, isso dá um limite mais baixo de O(n) tentativas e desempenho O(n^2) ou O(n*ln(n)).

Todos os resultados são, no entanto, muito melhores, que eu jamais esperaria, o que mostra que o algoritmo pode realmente estar bem em muitos casos não críticos, onde você pode aceitar tempos de execução ocasionais (quando tiver azar).