Esse problema está relacionado à pesquisa do meu laboratório em cobertura robótica:
Desenhe aleatoriamente números do conjunto sem substituição e classifique os números em ordem crescente. .
A partir dessa lista ordenada de números , gere a diferença entre números consecutivos e os limites: . Isso fornece lacunas.
Qual é a distribuição da diferença máxima?
Isso pode ser estruturado usando estatísticas de ordem :
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, .
Se todas as lacunas são do tamanho 1. Se há uma lacuna do tamanho , e locais possíveis. O tamanho máximo do intervalo é , e esse intervalo pode ser colocado antes ou depois de qualquer um dos números, para um total de posições possíveis. O menor tamanho máximo de espaço é . Defina a probabilidade de qualquer combinação dada.
Resolvi parcialmente a função de massa de probabilidade como
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 ) = 1
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]
Respostas:
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) g g n−1 {g+1,g+2,…,m} tais subconjuntos do ( m(m−gn−1) subconjuntos igualmente prováveis, de onde(mn)
Adicionar para todos os valores possíveis de k maiores que g produz a função de sobrevivênciaf(k;n,m) k g
Seja a variável aleatória dada pela maior lacuna:Gn,m
(This responds to the question as originally framed, before it was modified to include a gap betweena(n) and m .)
We will compute its survival function
For largern>1 , note that the event Gn,m>g is the disjoint union of the event
for which the very first gap exceedsg , and the g separate events
for which the first gap equalsk and a gap greater than g occurs later in the sample. The Law of Total Probability asserts the probabilities of these events add, whence
Fixingg 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=m−n+1 can be constructed in O(m3n) operations.
These graphs show the survival functiong→P(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 forP(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 ofGn,m is obtained by summing its survival function starting at g=0 :
This contour plot of the expectation shows contours at2,4,6,…,32 , graduating from dark to light.
fonte