HEC-ESCP-EML 2000.Math 2, option scientifique Leproble`meconsisteenl’analysed’unalgorithmedetrietl’e´tudedesacomplexite´. On note lnxnee´´pregoratimh´eelstriiend’unrtisofimetcptnelelxet logxson logarithme en base 2. On rappelle que 2 lnx logx= 2 ln 2 ´ PartieI:Etuded’unesuitere´elle Dans cette partie la lettrendise´alegs´in2.`atneinrtaruleuaomgneratoujoursune Onconside`relasuite(uk)k∈Nrpmesrnoreemeitrdiepa´efinu1tourutnafiiop,ttere´vnrelatila,ruercn:enoed´rce ∗ n−1 X 2 un=n−1 +ui n i=1 1)a)Calculeru2etu3en fonction deu1. b)Montrer que, pour toutnol`ian3s´aeugma:,onanun−(n+ 1)un−1= 2n−2. uk 2)Pour tout entier naturelknon nul, on pose :vk= . k+ 1 a)Pour toutnegs´`aalex3,imprreuaomnivn−vn−1en fonction den. b)etmrDe´lsr´eedeuxinerαetβruop,tnafiire´vleer´uttoxnon nul et distinct de−´e:1l,’´egalit 2x−2α β = + x(x+ 1)x x+ 1 n X 1u14 c)Pour toutnaelt,eg´l’´iarbl:´eitvn= 2+−2 +. k3n+ 1 k=2 n X 1 1n 3)Pour toutn, on posehn= etzn=−ln( ). k nn−1 k=2 a)Calculerunen fonction dehn,u1etn. n X b)rPuoevlr´’ge:e´tilahn=zk+ lnn. k=2 c)g´enermeedet´erilesarudenataenlrmieretD´are´lzn. d)ivquenalreui´eunnEde´ddtehnquandntend vers l’infini. e)un´equDi´veterminerlanedteunquandntend vers l’infini. ´ PartieII:Etuded’unesuitedevariablesal´eatoires
AOspneeuerd`sionncde´silibaborpecanoltpaorabibil´teestnot´eePairaaelbae´lriote,unevZec,seap,dfin´esuieetrc prenantunnombrefinidevaleursre´ellesnote´esz1, z2, . . . , zpntmeetvun´ene´eAne´tunnoaborilibepdlle. On noteE(Z/Aeroiat´ealleabrivanaecedal’lse´pre)Zibaborpalruoptncaahllseonneditieconlit´A, i. e. p X P E(Z/A) =ziP([Z=zi]/A) i=1 Soit (A1, A2, . . . , Aqbibaroeponent´liemene´vedsuotstnit´eegal.erPunlllr´’uoevst`emecompletd’´)nuys q X E(Z) =P(Aj)E(Z/Aj) j=1
Broepbibaeeemacspalt´silnodeartiesontesous-pssrunuˆmdte´nfieinscoesirtoeal´satecsnadsee´re´diTbaelavirlsseuoet probabilit´eestnot´eeP. Onconsid`ereunesuite(In)n∈Nedleabrivatoeal´sariseetllqeeup,uortoutnnon nul,Insuit la loi uniforme sur l’ensemble ∗ [1, nteui(re`eesunsndinoocra,trtpeD’auetn.tre1e,engralsnesua,sirpmcorsientsede]]Xn)n∈Nbairaselavedesl´eatoir ∗ ayantlesproprie´t´essuivantes •X1ela`e´ag0ecbliaarteanstonvaltse •pour tout entier naturelnenllseedsllescoidionontiomua´snilage,2a`Xnsachant [In= 1] et deXnsachant [In=n] sonttoutesdeuxe´gales`alaloiden−1 +Xn−1 •pour tout entier natureln3ateag`lneitottuaerns´eumoiitel que 2≤i≤n−1, la loi conditionnelle deXnsachant [In=i´egale`a]estolaledin−1 +Zn,i+Tn,iou`Zn,ietTn,isindoire´eatesalailbvxradtuesno,setnadnepe´Zn,iayant mˆemeloiqueXi−1, etTn,iantyameˆmioleeuqXn−i. Par exemple, on a :P([X6= 9]/[I6= 1]) =P([X5= 4]) et aussiP([X6= 9]/[I6= 3]) =P([Z6,3+T6,3= 4]) ce qui, X comptetenudeshypothe`ses,s’´ecrit:P([X6= 9]/[I6= 3]) =P([X2=j])P([X3= 4−je´tnate´emmosal,])uendte j aux valeurs convenables de l’entierj. 1)a)Montrer queX2etnatsnoa`elage´sˆuesqretcenemurae´lailbripeaeot1.eevarstun
1 2 ´ b)e´:slatis´egirletablEP([X3= 2]) =etP([X3decnare´]3=)=ealcu.C’esplerlX3qu’on noteraU3. 3 3 2)mrnirealoldiete´eDX4etcalculersonesp´nareuqecnno’retoaU4. 3)encecurrrr´entpaopruuq,ertrem,noretunaertienuttolEnocprda´ennon nul,Xnsˆuremen,presquednerp,teds n(n−1) valeursenti`eresinf´erieuresou´egalesa`. 2 4)Soitnuratrnieinmoaueltnenulaa`´sgeonet.2nOUnesp´l’cedeeranXn. n−1 X 2 ` a)esr´tauldetssolalAdia’sedelirl’´egalit´e:sup-raitAe´,tebaUn=n−1 +Ui. n i=1 ` b)A l’aide de la partie I, donner l’expression deUnen fonction denaviutnelu’uqqe´nasiindeUnquandntend vers l’infini. 5)Pour tout entier naturelnnon nul, on noteαntitelavepalpsulre`eri)pr(eutienlberaailrvaesapXnavec une probabilite´nonnulle. a)Soitnetkdeux entiers naturels, l’entiernegs´`aal3.e´attnuaomni Montrer queP([Xn=k]) est nul si et seulement si les nombresP([n−1 +Xn−1=k]) etP([n−1 +Zn,i+Tn,i=k]) (l’entierivairadenta2`n−1) sont nuls. Ende´duirequeαnmoins´egestausrembonsedmuminimualan−1 +αn−1, n−1 +α1+αn−2, n−l+α2+ αn−3, . . . , n−1 +αn−2+α1. b)ere`ofalitcnnocoOnidnsgd´efinie,pourtoutxstrictement positif, parg(x) =xlogx−2x+ 2. 2 i.Montrer quegest convexe. Pour tout couple d’entiers (i, n) tel que 2≤i≤n−e´tilage´ni’leri´edu,end1: n+ 1 g(i) +g(n+ 1−i)≥2g. 2 ii.Pour tout entier naturelnate´rilbnon,lunt´lie:inl’ga´eg(n+ 1)−g(n)≤log (nsclertpaasnErt1+.)tna`iaat 2 n= 1 etn= 2, montrer que, pour tout entier naturelnnon nul, on a :g(n+ 1)−g(n)≤n−1. 6)pnE´cornaderaptntteourtou,pirblate´,ecnerruce´rletarueinrnt´e:galiin´el,l’nounn αn≥(n(+ 1) logn+ 1)−2n 2
´ Partie III :Etude d’un algorithme de tri
Alerenunre`etunaertiOnconsidnnon nul et un ensembleE={e1, e2, . . . , en}`oue1, e2, . . . , en´vslfiiretnaonsestdeer´ e1< e2. .< e< .n. On munit l’ensemble des permutations deErobabilit´edlepauniformene´toePd`sieerO.nocn lesnviaarlae´lbseerstaioT1, T2, . . . , Tnnui,`qepetuotaoitatumrσdeEas,tlencisoemtndsedes´el´eesimagesEparσ, i.e.T1(σ) =σ(e1), T2(σ) =σ(e2), . . . , Tn(σ) =σ(en), et on noteT´laeuearevtcele(irtoT1, T2, . . . , Tn). Pour toute liste (α1, α2, . . . , αn´ed’eml´tsen)distinctsdeEon a donc : 1 P[T= (α1, α2, . . . , αn)] = n! 1)lbaeraaiotri´laeeete´DlaerinrmavelidloT1. 0 2)On supposentionaleg2.`amoaus´inrepeatumruoPtuotσdeEon noteT(σestliladentme´emeei´rle)elrp 1 0 0 ntele´l´ementexistee(σ) = 0 sinon,T(σme`eixuedel) σ(e1), σ(e2), . . . , σ(enieurf´er)ina`σ(e1) =T1(σ) si utT1 2 0 0 le´mentexisteetT) = 0 sinon, etc ´el´ementinfe´rieur`aσ(e1unteldeuxi`eme´e)is2(σ.,T(σ) le (n−emtnlee´me´e-)`i1 n−1 0 eme´el´ementexisteetT σ) = 0 sinon. infe´rieur`aσ(e1) si un tel (n−1)-i`n−1( Par exemple, si n= 4,(e1, e2, e3, e4) = (3,5,7,10) et (σ(e1), σ(e2), σ(e3), σ(e4)) = (7,10,5,3) 0 00 alorsT(σ) = 5, T(σ) = 3 etT(σ) = 0. 1 23 Soitkvre´irafitn1neuient≤k≤n−1. a)Combien y a-t-il de listes (i1, i2, . . . , iknt2rifiasv´ereitne’d)≤i1< i2. .< .< ik≤n? ´ b)Soit (α1, α2, . . . , αk)untsle´’eme´ilendetsdistinctsde{e1, e2, . . . , ek}:gelati.et´Ebaillr´’ k \ 1 0 P=α] [Tj j∩[T1=ek+1] = nk! j=1 c)reui´el’Enedd´´teagil k \ 1 0 P[T=α j j]/[T1=ek+1] = k! j=1 ou`P(A/Bilabobprlaneiges´d)eledit´econditionnelAsachantB. 0 00 Ainsi la loi conditionnelle de(T ,. . .T ,)sachant 1 2, Tk[T1=ek+l]est uniforme. 2