Répartition du plus gros fragment d'un bâton cassé (espacements)

21

Soit un bâton de longueur 1 cassé en k+1 fragments uniformément au hasard. Quelle est la distribution de la longueur du plus long fragment?

Plus formellement, soit (U1,Uk) soit IID U(0,1) , et soit (U(1),,U(k)) les statistiques d'ordre associées, c'est-à - dire que nous commandons simplement l'échantillon dans d'une manière que U(1)U(2),,U(k) . LaisserZk=max(U(1),U(2)U(1),,U(k)U(k1),1U(k)) .

Je m'intéresse à la distribution de Zk . Les moments, les résultats asymptotiques ou les approximations de k sont également intéressants.

gui11aume
la source
9
C'est un problème bien étudié; voir R. Pyke (1965), « Spacings », JRSS (B) 27 : 3, pp. 395-449. J'essaierai de revenir pour ajouter des informations plus tard, sauf si quelqu'un me bat dessus. Il y a aussi un article de 1972 du même auteur (" Spacings revisited ") mais je pense que ce que vous recherchez est à peu près tout dans le premier. Il y a quelques asymptotiques dans Devroye (1981) , "Lois du logarithme itéré pour les statistiques d'ordre des espacements uniformes" Ann. Probab. , 9 : 5, 860-867.
Glen_b -Reinstate Monica
4
Ceux-ci devraient également fournir de bons termes de recherche pour trouver un travail ultérieur si vous en avez besoin.
Glen_b -Reinstate Monica
3
C'est génial. La première référence est difficile à trouver. Pour ceux qui sont intéressés, je l'ai mis sur The Grand Locus .
gui11aume
Veuillez corriger l'erreur d'impression: au lieu de U ( k ) . Y(k)U(k)
Viktor
Merci @Viktor! Pour de si petites choses, n'hésitez pas à faire le montage vous-même (je pense qu'il sera revu par d'autres utilisateurs pour approbation).
gui11aume

Réponses:

18

Avec les informations fournies par @Glen_b, j'ai pu trouver la réponse. En utilisant les mêmes notations que la question

P(Zkx)=j=0k+1(k+1j)(1)j(1jx)+k,

si a > 0 et 0 sinon. Je donne également l'attente et la convergence asymptotique à la distribution de Gumbel ( NB : pas Beta)a+=aa>00

E(Zk)=1k+1i=1k+11ilog(k+1)k+1,P(Zkx)exp(e(k+1)x+log(k+1)).

The material of the proofs is taken from several publications linked in the references. They are somewhat lengthy, but straightforward.

1. Proof of the exact distribution

Soit des variables aléatoires uniformes IID dans l'intervalle ( 0 , 1 ) . En les commandant, nous obtenons les statistiques d'ordre k notées ( U ( 1 ) , , U ( k ) ) . Les espacements uniformes sont définis comme Δ i = U ( i ) - U ( i - 1 ) , avec U ((U1,,Uk)(0,1)k(U(1),,U(k))Δi=U(i)U(i1)U(0)=0 and U(k+1)=1. The ordered spacings are the corresponding ordered statistics Δ(1)Δ(k+1). The variable of interest is Δ(k+1).

For fixed x(0,1), we define the indicator variable 1i=1{Δi>x}. By symmetry, the random vector (11,,1k+1) is exchangeable, so the joint distribution of a subset of size j is the same as the joint distribution of the first j. By expanding the product, we thus obtain

P(Δ(k+1)x)=E(i=1k+1(11i))=1+j=1k+1(k+1j)(1)jE(i=1j1i).

We will now prove that E(i=1j1i)=(1jx)+k, which will establish the distribution given above. We prove this for j=2, as the general case is proved similarly.

E(i=121i)=P(Δ1>xΔ2>x)=P(Δ1>x)P(Δ2>x|Δ1>x).

If Δ1>x, the k breakpoints are in the interval (x,1). Conditionally on this event, the breakpoints are still exchangeable, so the probability that the distance between the second and the first breakpoint is greater than x is the same as the probability that the distance between the first breakpoint and the left barrier (at position x) is greater than x. So

P(Δ2>x|Δ1>x)=P(all points are in (2x,1)|all points are in (x,1)),soP(Δ2>xΔ1>x)=P(all points are in (2x,1))=(12x)+k.

2. Expectation

For distributions with finite support, we have

E(X)=P(X>x)dx=1P(Xx)dx.

Integrating the distribution of Δ(k+1), we obtain

E(Δ(k+1))=1k+1j=1k+1(k+1j)(1)j+1j=1k+1j=1k+11j.

The last equality is a classic representation of harmonic numbers Hi=1+12++1i, which we demonstrate below.

Hk+1=011+x++xkdx=011xk+11xdx.

With the change of variable u=1x and expanding the product, we obtain

Hk+1=01j=1k+1(k+1j)(1)j+1uj1du=j=1k+1(k+1j)(1)j+1j.

3. Alternative construction of uniform spacings

In order to obtain the asymptotic distribution of the largest fragment, we will need to exhibit a classical construction of uniform spacings as exponential variables divided by their sum. The probability density of the associated order statistics (U(1),,U(k)) is

fU(1),U(k)(u(1),,u(k))=k!,0u(1)u(k+1).

If we denote the uniform spacings Δi=U(i)U(i1), with U(0)=0, we obtain

fΔ1,Δk(δ1,,δk)=k!,0δi++δk1.

By defining U(k+1)=1, we thus obtain

fΔ1,Δk+1(δ1,,δk+1)=k!,δ1++δk=1.

Now, let (X1,,Xk+1) be IID exponential random variables with mean 1, and let S=X1++Xk+1. With a simple change of variable, we can see that

fX1,Xk,S(x1,,xk,s)=es.

Define Yi=Xi/S, such that by a change of variable we obtain

fY1,Yk,S(y1,,yk,s)=skes.

Integrating this density with respect to s, we thus obtain

fY1,Yk,(y1,,yk)=0skesds=k!,0yi++yk1,and thusfY1,Yk+1,(y1,,yk+1)=k!,y1++yk+1=1.

So the joint distribution of k+1 uniform spacings on the interval (0,1) is the same as the joint distribution of k+1 exponential random variables divided by their sum. We come to the following equivalence of distribution

Δ(k+1)X(k+1)X1++Xk+1.

4. Asymptotic distribution

Using the equivalence above, we obtain

P((k+1)Δ(k+1)log(k+1)x)=P(X(k+1)(x+log(k+1))X1++Xk+1k+1)=P(X(k+1)log(k+1)x+(x+log(k+1))Tk+1),

where Tk+1=X1++Xk+1k+11. This variable vanishes in probability because E(Tk+1)=0 and Var(log(k+1)Tk+1)=(log(k+1))2k+10. Asymptotically, the distribution is the same as that of X(k+1)log(k+1). Because the Xi are IID, we have

P(X(k+1)log(k+1)x)=P(X1x+log(k+1))k+1=(1exlog(k+1))k+1=(1exk+1)k+1exp{ex}.

5. Graphical overview

The plot below shows the distribution of the largest fragment for different values of k. For k=10,20,50, I have also overlaid the asymptotic Gumbel distribution (thin line). The Gumbel is a very bad approximation for small values of k so I omit them to not overload the picture. The Gumbel approximation is good from k50.

Distribution of the largest fragment of a broken stick

6. References

The proofs above are taken from references 2 and 3. The cited literature contains many more results, such as the distribution of the ordered spacings of any rank, their limit distribution and some alternative constructions of the ordered uniform spacings. The key references are not easily accessible, so I also provide links to the full text.

  1. Bairamov et al. (2010) Limit results for ordered uniform spacings, Stat papers, 51:1, pp 227-240
  2. Holst (1980) On the lengths of the pieces of a stick broken at random, J. Appl. Prob., 17, pp 623-634
  3. Pyke (1965) Spacings, JRSS(B) 27:3, pp. 395-449
  4. Renyi (1953) On the theory of order statistics, Acta math Hung, 4, pp 191-231
gui11aume
la source
Brilliant. By the way, is there a known asymptotics to E(Zk2)?
Amir Sagiv
@AmirSagiv c'est une bonne question. J'ai jeté un coup d'œil aux références et je n'ai pas pu le trouver. Je n'ai pas non plus pu adapter la preuve ci-dessus. Cela m'a fait réaliser que je ne sais pas quelle est la distribution d'un carré d'un Gumbel. Peut-être un bon point de départ?
gui11aume
1
$gui11aume Look here : mathoverflow.net/a/293381/42864
Amir Sagiv
1
@AmirSagiv Ceci est un très bon article. Pour une raison quelconque, j'ai mal compris votre question et j'ai pensé que vous étiez intéressé par la distribution asymptotique deZk2 (même si votre commentaire était très clair), mon commentaire ci-dessus n'est donc pas si pertinent.
gui11aume
3

Ce n'est pas une réponse complète, mais j'ai fait quelques simulations rapides, et voici ce que j'ai obtenu: Histogramme du plus long fragment

Cela semble remarquablement beta-ish, et cela a un peu de sens, car les statistiques d'ordre des distributions uniformes iid sont beta wiki .

Cela pourrait donner un point de départ pour dériver le pdf résultant.

Je mettrai à jour si j'arrive à une solution finale fermée.

À votre santé!

Lima
la source
Encore une chose, la forme de l'histogramme pour augmenter k ne change pas considérablement, à part d'être "écrasé" près de 0.
Lima
1
Merci pour vos réflexions @Lima (et bienvenue à Cross Validated). Je pense que votre réponse peut être améliorée. Premièrement, je m'abstiendrai de faire des déclarations sans preuve. Si cela est incorrect, vous pouvez mettre les personnes qui voient ce fil sur la mauvaise piste. Deuxièmement, je documenterais ce que vous avez fait. Sans la valeur dekque vous avez utilisé ni le code, la figure n'aide personne. Enfin, je voudrais copier-éditer la réponse et supprimer tout ce qui ne répond pas directement à la question.
gui11aume
1
Merci pour les suggestions. Ils sont valables au-delà de l'échange de pile, et je me souviendrai de les utiliser.
Lima
1

I produced the answer for a conference in Siena (Italy) in 2005. The paper (2006) is presented on my web-site here (pdf). The exact distributions of all the spacings (smallest to largest) are found on pages 75 & 76.

I'm hoping to give a presentation on this topic at the RSS Conference in Manchester (England) in September 2016.

C.J.Stephens
la source
2
Welcome to the site. We are trying to build a permanent repository of high-quality statistical information in the form of questions & answers. Thus, we're wary of link-only answers, due to linkrot. Can you post a full citation & a summary of the information at the link, in case it goes dead? Also, please don't sign your posts here. Every post has a link to your userpage where you can post that information.
gung - Reinstate Monica