Écart maximal entre les échantillons prélevés sans remplacement à partir d'une distribution uniforme discrète

16

Ce problème est lié aux recherches de mon laboratoire sur la couverture robotique:

Tirez au hasard n nombres de l'ensemble {1,2,,m} sans remplacement et triez les nombres dans l'ordre croissant. 1nm .

À partir de cette liste triée de nombres {a(1),a(2),,a(n)} , générez la différence entre les nombres consécutifs et les limites: g={a(1),a(2)a(1),,a(n)a(n1),m+1a(n)} . Cela donnen+1 lacunes.

Quelle est la distribution de l'écart maximum?

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

Cela peut être encadré à l'aide des statistiques de commande : P(g(n+1)=k)=P(k;m,n)=?

Voir le lien pour la répartition des écarts , mais cette question demande la répartition de l' écart maximal .

Je serais satisfait de la valeur moyenne, E[g(n+1)] .

Si n=m tous les espaces sont de taille 1. Si n+1=m il y a un espace de taille 2 et n+1 emplacements possibles. La taille maximale de l'espace est mn+1 , et cet espace peut être placé avant ou après n'importe lequel des n nombres, pour un total de n+1 positions possibles. La plus petite taille d'espace maximale est mnn+1. Définir la probabilité d'une combinaison donnée. T=(mn)1

J'ai partiellement résolu la fonction de masse de probabilité comme (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

Travail en cours (1): L'équation pour le premier écart, est simple: P ( a ( 1 ) = k ) = P ( k ; m , n ) = 1a(1) La valeur attendue a une valeur simple: E[P(a(1))]=1

P(a(1)=k)=P(k;m,n)=1(mn)k=1mn+1(mk1n1)
. Par symétrie, je m'attends à ce que toutes lesnlacunes aient cette distribution. Peut-être la solution pourrait-elle être trouvée en tirant de cette distributionnfois.E[P(a(1))]=1(mn)k=1mn+1(mk1n1)k=mn1+nnn

Travaux en cours (2): il est facile d'exécuter des simulations 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
la source
1
Dans ces conditions, vous devez avoir n <= m. Je pense que vous voulez g = {a_ (1), a_ (2) -a_ (1), ..., a_ (n) -a_ (n-1)}. Est-ce que sélectionner au hasard signifie sélectionner chaque nombre avec une probabilité de 1 / m lors du premier tirage? Puisque vous ne remplacez pas la probabilité serait de 1 / (m-1) sur le second et ainsi de suite jusqu'à 1 sur le mième tirage si n = m. Si n <m, cela s'arrêterait plus tôt avec le dernier tirage ayant une probabilité 1 / (m- (n-1)) sur le nième tirage.
Michael R. Chernick
2
Your original description of g made no sense, because (I believe) you transposed two of the subscripts. Please verify that my edit conforms with your intention: in particular, please confirm that you mean for there to be n gaps, of which a(1) is the first.
whuber
1
@gung I think this is research, rather than self-study
Glen_b -Reinstate Monica
1
I think your minimum and maximum gap sizes should be 1 and mn+1. The minimum gap size is when consecutive integers are chosen, and the maximum gap size occurs when you select m and n1 first integers 1,,n1 (or 1 and mn+2,,m)
probabilityislogic
1
Thank you Michael Chernick and probabilityislogic, your corrections have been made. Thank you @whuber for making the correction!
AaronBecker

Réponses:

9

f(g;n,m)a(1)ggn1{g+1,g+2,,m}(mgn1) such subsets out of the (mn) equally likely subsets, whence

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

Adding f(k;n,m) for all possible values of k greater than g yields the survival function

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

Let Gn,m be the random variable given by the largest gap:

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
la source
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