Intervalo máximo entre as amostras retiradas sem substituição de uma distribuição uniforme e discreta

16

Esse problema está relacionado à pesquisa do meu laboratório em cobertura robótica:

Desenhe aleatoriamente n números do conjunto {1,2,,m} sem substituição e classifique os números em ordem crescente. 1nm .

A partir dessa lista ordenada de números {a(1),a(2),,a(n)} , gere a diferença entre números consecutivos e os limites: g={a(1),a(2)a(1),,a(n)a(n1),m+1a(n)} . Isso fornecen+1 lacunas.

Qual é a distribuição da diferença máxima?

P(max(g)=k)=P(k;m,n)=?

Isso pode ser estruturado usando estatísticas de ordem : P(g(n+1)=k)=P(k;m,n)=?

Veja o link para a distribuição de lacunas , mas esta pergunta solicita a distribuição da lacuna máxima .

Eu ficaria satisfeito com o valor médio, E[g(n+1)] .

Se n=m todas as lacunas são do tamanho 1. Se n+1=m há uma lacuna do tamanho 2 , e n+1 locais possíveis. O tamanho máximo do intervalo é mn+1 , e esse intervalo pode ser colocado antes ou depois de qualquer um dos n números, para um total de n+1 posições possíveis. O menor tamanho máximo de espaço é mnn+1. Defina a probabilidade de qualquer combinação dada. T=(mn)1

Resolvi parcialmente a função de massa de probabilidade como (1)P(g(n+1)=k)=P(k;m,n)={0k<mnn+11k=mnn+11k=1 (occurs when m=n)T(n+1)k=2 (occurs when m=n+1)T(n+1)k=m(n1)n?m(n1)nkmn+1T(n+1)k=mn+10k>mn+1

Trabalho atual (1): A equação da primeira lacuna, é direta: O valor esperado possui um valor simples: . Por simetria, espero que todas as lacunas tenham essa distribuição. Talvez a solução possa ser encontrada usando essa distribuição vezes. P ( a ( 1 ) = k ) = P ( k ; m , n ) = 1a(1)

P(a(1)=k)=P(k;m,n)=1(mn)k=1mn+1(mk1n1)
E[P(a(1))]=1(mn)k=1mn+1(mk1n1)k=mn1+nnn

Trabalho atual (2): é fácil executar simulações de Monte Carlo.

simMaxGap[m_, n_] := Max[Differences[Sort[Join[RandomSample[Range[m], n], {0, m+1}]]]];
m = 1000; n = 1; trials = 100000;
SmoothHistogram[Table[simMaxGap[m, n], {trials}], Filling -> Axis,
Frame -> {True, True, False, False},
FrameLabel -> {"k (Max gap)", "Probability"},
PlotLabel -> StringForm["m=``,n=``,smooth histogram of maximum map for `` trials", m, n, trials]][![enter image description here][1]][1]
AaronBecker
fonte
1
Com essas condições, você deve ter n <= m. Eu acho que você quer g = {a_ (1), a_ (2) -a_ (1), ..., a_ (n) -a_ (n-1)}. Selecionar aleatoriamente significa selecionar cada número com probabilidade 1 / m no primeiro sorteio? Como você não substitui, a probabilidade seria 1 / (m-1) no segundo e assim por diante até 1 no m-ésimo empate, se n = m. Se n <m, isso parava mais cedo, com o último empate tendo probabilidade 1 / (m- (n-1)) no enésimo empate.
Michael R. Chernick 31/12/16
2
Sua descrição original de não fazia sentido, porque (acredito) você transpôs dois dos subscritos. Verifique se minha edição está de acordo com sua intenção: em particular, confirme que você quer que haja n lacunas, das quais a ( 1 ) é a primeira. gna(1)
whuber
1
@gung Acho que isso é pesquisa, e não auto-estudo
Glen_b -Reinstate Monica
1
Eu acho que seus tamanhos mínimo e máximo de gap devem ser e m - n + 1 . O tamanho mínimo do intervalo é quando números inteiros consecutivos são escolhidos, e o tamanho máximo do intervalo ocorre quando você seleciona m e n - 1 primeiros inteiros 1 , , n - 1 (ou 1 e m - n + 2 , , m )1mn+1mn11,,n11mn+2,,m
probabilityislogic
1
Obrigado Michael Chernick e probabilityislogic, suas correções foram feitas. Obrigado @whuber por fazer a correção!
AaronBecker

Respostas:

9

Seja a chance de que o mínimo, a ( 1 ) , seja igual a g ; isto é, a amostra consiste em g e um subconjunto n - 1 de { g + 1 , g + 2 , , m } . Existem ( m - gf(g;n,m)a(1)ggn1{g+1,g+2,,m} tais subconjuntos do ( m(mgn1) subconjuntos igualmente prováveis, de onde(mn)

Pr(a(1)=g=f(g;n,m)=(mgn1)(mn).

Adicionar para todos os valores possíveis de k maiores que g produz a função de sobrevivênciaf(k;n,m)kg

Pr(a(1)>g)=Q(g;n,m)=(mg)(mg1n1)n(mn).

Seja a variável aleatória dada pela maior lacuna:Gn,m

Gn,m=max(a(1),a(2)a(1),,a(n)a(n1)).

(This responds to the question as originally framed, before it was modified to include a gap between a(n) and m.) We will compute its survival function

P(g;n,m)=Pr(Gn,m>g),
from which the entire distribution of Gn,m is readily derived. The method is a dynamic program beginning with n=1, for which it is obvious that

(1)P(g;1,m)=Pr(G1,m>1)=mgm, g=0,1,,m.

For larger n>1, note that the event Gn,m>g is the disjoint union of the event

a1>g,

for which the very first gap exceeds g, and the g separate events

a1=k and Gn1,mk>g, k=1,2,,g

for which the first gap equals k and a gap greater than g occurs later in the sample. The Law of Total Probability asserts the probabilities of these events add, whence

(2)P(g;n,m)=Q(g;n,m)+k=1gf(k;n,m)P(g;n1,mk).

Fixing g and laying out a two-way array indexed by i=1,2,,n and j=1,2,,m, we may compute P(g;n,m) by using (1) to fill in its first row and (2) to fill in each successive row using O(gm) operations per row. Consequently the table can be completed in O(gmn) operations and all tables for g=1 through g=mn+1 can be constructed in O(m3n) operations.

Figure

These graphs show the survival function gP(g;n,64) for n=1,2,4,8,16,32,64. As n increases, the graph moves to the left, corresponding to the decreasing chances of large gaps.

Closed formulas for P(g;n,m) can be obtained in many special cases, especially for large n, but I have not been able to obtain a closed formula that applies to all g,n,m. Good approximations are readily available by replacing this problem with the analogous problem for continuous uniform variables.

Finally, the expectation of Gn,m is obtained by summing its survival function starting at g=0:

E(Gn,m)=g=0mn+1P(g;n,m).

Figure 2: contour plot of expectation

This contour plot of the expectation shows contours at 2,4,6,,32, graduating from dark to light.

whuber
fonte
Suggestion: line "Let Gn,m be the random variable given by the largest gap:", please add the last gap of m+1an. Your expectation plot matches my Monte Carlo simulation.
AaronBecker