x <- c(-1, 1, 2, 3) # valorile câștigului
p <- ___ # P(N = 0), ..., P(N = 3): câte zaruri arată 6
medie_var <- function(x, p) { # x = valorile, p = probabilitățile
m <- ___ # media
v <- ___ # varianța, din definiție
c(medie = m, varianta = v, sd = sqrt(v))
}
medie_var(x, p)
___ # (c): miza s pentru care jocul este corect
set.seed(401)
joc <- function() { # câștigul net la o partidă
k <- ___ # câte dintre cele 3 zaruri arată 6
if (k == 0) -1 else k
}
castig <- replicate(1e5, joc()) # 100 000 de partide
c(medie = mean(castig), varianta = var(castig), sd = sd(castig))
mc <- ___ # media primelor n partide, n = 1, 2, ...
plot(mc, type = "l", log = "x", ylim = c(-0.6, 0.6),
xlab = "numărul de partide n", ylab = "media primelor n partide")
abline(h = medie_var(x, p)[["medie"]], lty = 2) # media teoreticăSeminarul 4. Media și varianța variabilelor aleatoare discrete. Metoda indicatorilor
Fișă de lucru (fără rezolvări)
Aceasta este fișa de lucru: enunțurile, scheletele de cod R și răspunsurile finale pentru exercițiile marcate „Dacă timpul permite” și „Pentru acasă”. Rezolvările complete vor fi publicate ulterior.
Media și varianța rezumă o repartiție prin două numere: unde se află „centrul” ei și cât de împrăștiate sunt valorile în jurul acestuia. În ședința de astăzi le calculăm în trei feluri — din definiție, cu formulele repartițiilor uzuale și, mai ales, descompunând variabila într-o sumă de indicatori — și verificăm fiecare rezultat în R, prin calcul exact și prin simulare. Ședința se încheie cu două aplicații clasice din informatică: problema colecționarului de cupoane și numărul mediu de comparații efectuate de algoritmul Quicksort. Fiecare exercițiu are o parte matematică și una în R (Laborator; în fișă, cu un schelet de cod de completat), iar funcțiile R scrise la început sunt refolosite pe parcurs.
Obiective. La sfârșitul ședinței studentul trebuie să poată:
- calcula media, varianța și abaterea standard ale unei variabile discrete date prin tabelul de repartiție, folosi formula de transport și decide dacă un joc de noroc este corect;
- recunoaște o repartiție uzuală (binomială, geometrică, Poisson, hipergeometrică) într-o problemă concretă, aplica formulele pentru medie și varianță și interpreta abaterea standard;
- scrie o variabilă care numără ca sumă de indicatori și calcula media ei prin liniaritate, chiar când indicatorii nu sunt independenți (perechi cu aceeași zi de naștere, puncte fixe, cupoane, Quicksort);
- calcula varianța unei sume: de variabile independente (varianțele se adună) și de indicatori dependenți (apar termeni suplimentari);
- calcula în R media și varianța unei repartiții tabelate, aproxima \(\E[X]\) și \(\Var(X)\) prin
meanșivarpe un eșantion simulat, urmări mediile curente și scrie funcții recursive simple.
Structura. Breviar; media și varianța din definiție și formula de transport; media și varianța repartițiilor uzuale; liniaritatea mediei și metoda indicatorilor; varianța sumei de variabile independente; exerciții suplimentare; temă. Pentru aprofundare: (Blitzstein and Hwang 2019, cap. 4), (Bertsekas and Tsitsiklis 2008, cap. 2), (Ross 2014, cap. 4), pentru simulări în R (Wagaman and Dobrow 2021), iar pentru analiza algoritmilor probabiliști (colecționarul de cupoane, Quicksort) (Mitzenmacher and Upfal 2017, cap. 2).
De rezolvat la seminar (în această ordine):
- Exercițiul 1 — media și varianța din tabelul de repartiție, un joc corect; funcția
medie_varși mediile curente; - Exercițiul 4 (a)–(c), (e) — media și varianța repartițiilor binomială și geometrică; varianța unei sume de variabile independente;
- Exercițiul 7 — metoda indicatorilor: media și varianța numărului de perechi; funcția
perechi; - Exercițiul 9 — colecționarul de cupoane: sumă de variabile geometrice independente; funcțiile
colectioneazașiF_T; - Exercițiul 10 (a), (b), (d) — numărul mediu de comparații în Quicksort; funcția recursivă
quicksort_comp.
Dacă timpul permite:
- Exercițiul 2 — formula de transport și \(\E[g(X)]\ne g(\E[X])\);
- Exercițiul 8 — varianța numărului de puncte fixe: indicatori dependenți;
- Exercițiul 11 — media a \(n\) măsurători independente.
Pentru acasă:
- Exercițiile 3 (jocul de la Sankt Petersburg), 5 (cereri la un server) și 6 (controlul calității cu și fără întoarcere);
- exercițiile suplimentare 12, 13, 14 și 15 (Secțiunea 6);
- enunțurile din Secțiunea 7.
Rezolvările complete vor fi publicate ulterior; scheletele de cod R se completează în locurile marcate cu ___. Exercițiile marcate „Dacă timpul permite” și „Pentru acasă” au, după enunț, răspunsurile finale, pentru verificare.
1 Breviar
Folosim noțiunile și rezultatele din partea a doua a Cursul 3: media, formula de transport, varianța și tabelul mediilor și varianțelor repartițiilor uzuale. Le reamintim pe scurt, cu trimiterile corespunzătoare; în rezolvări (publicate ulterior) indicăm la fiecare pas rezultatul aplicat.
Media (Definiția 24 din Cursul 3): \(\E[X]=\sum_x x\,\PP(X=x)\), dacă \(\sum_x|x|\,\PP(X=x)<\infty\); altfel media nu există (Exemplul 16 din Cursul 3). Interpretare: media aritmetică a valorilor lui \(X\) într-un număr mare de repetări ale experimentului.
Formula de transport (Teorema 25 din Cursul 3): \(\E[g(X)]=\sum_x g(x)\,\PP(X=x)\), fără a determina repartiția lui \(g(X)\). În general \(\E[g(X)]\ne g(\E[X])\).
Proprietățile mediei (Teorema 26 din Cursul 3): liniaritatea \(\E[aX+bY]=a\E[X]+b\E[Y]\), fără nicio ipoteză de independență; \(\E[\Ind_A]=\PP(A)\); dacă \(X\indep Y\), atunci \(\E[XY]=\E[X]\E[Y]\).
Metoda indicatorilor: dacă \(X\) numără câte dintre evenimentele \(A_1,\dots,A_n\) se realizează, atunci \(X=\Ind_{A_1}+\dots+\Ind_{A_n}\) și \(\E[X]=\PP(A_1)+\dots+\PP(A_n)\) (Exemplul 18 din Cursul 3).
Varianța și abaterea standard (Definiția 28 din Cursul 3, Teorema 29 din Cursul 3): \(\Var(X)=\E\big[(X-\E[X])^2\big]=\E[X^2]-(\E[X])^2\), \(\mathrm{SD}(X)=\sqrt{\Var(X)}\), \(\Var(aX+b)=a^2\Var(X)\).
Varianța sumei (Teorema 30 din Cursul 3): \(\Var(X+Y)=\Var(X)+\Var(Y)+2\Cov(X,Y)\), cu covarianța \(\Cov(X,Y)=\E[XY]-\E[X]\E[Y]\); în general, \[\Var\Big(\sum_{i=1}^nX_i\Big)=\sum_{i=1}^n\Var(X_i)+\sum_{i\ne j}\Cov(X_i,X_j).\] Dacă variabilele sunt independente, covarianțele sunt nule și varianțele se adună.
Repartiții uzuale (Secțiunea 9 din Cursul 3):
\[ \begin{array}{l|cccc} &\Bern(p)&\Bin(n,p)&\Geom(p)&\Pois(\lambda)\\ \hline \text{media}&p&np&1/p&\lambda\\ \text{varianța}&p(1-p)&np(1-p)&(1-p)/p^2&\lambda \end{array} \] iar pentru \(X\sim\HGeom(N,M,n)\): \(\E[X]=n\frac MN\) și \(\Var(X)=n\frac MN\big(1-\frac MN\big)\frac{N-n}{N-1}\).
Numere armonice: \(H_n=1+\frac12+\dots+\frac1n\approx\ln n+0.5772\); în problema colecționarului de cupoane \(\E[T]=nH_n\) (Exemplul 20 din Cursul 3). De asemenea, \(1+\frac1{2^2}+\dots+\frac1{n^2}<\frac{\pi^2}{6}\approx1.645\).
sum(x * p)șisum((x - m)^2 * p)— media și varianța unei repartiții date prin tabel (vectorul valorilorxși vectorul probabilitățilorp);mean(x),var(x),sd(x)— media aritmetică, varianța și abaterea standard ale unui eșantion simulat; pentru un număr mare \(B\) de repetări ele aproximează \(\E[X]\), \(\Var(X)\) și \(\mathrm{SD}(X)\) (interpretarea frecvențială a mediei). Funcțiavarîmparte la \(B-1\), nu la \(B\) — pentru \(B\) mare diferența este neglijabilă;cumsum(x) / seq_along(x)— mediile curente: media primelor \(n\) valori, pentru \(n=1,2,\dots\);pmax(x, a),pmin(x, a)— maximul, respectiv minimul, calculat element cu element;tapply(p, g, sum)— adună elementele luippe grupele date deg;hist(x)— histograma unui eșantion;quantile(x, 0.95)— cuantila empirică: valoarea sub care se află \(95\%\) dintre valorile simulate;rbinom,rpois,rhyper(B, M, N - M, n)șirgeom(B, p) + 1— simularea repartițiilor uzuale (R numără eșecurile dinaintea primului succes, de aceea adunăm \(1\) pentru \(\Geom(p)\) din curs);- funcții recursive: o funcție R se poate apela pe ea însăși; are nevoie de o condiție de oprire (
if (length(v) <= 1) return(...)).
2 Media și varianța din definiție. Formula de transport
Începem cu variabile care iau puține valori, pentru care media și varianța se calculează direct din tabelul de repartiție. Primul exercițiu introduce și funcția R medie_var, pe care o refolosim în toată ședința, iar al treilea arată ce se întâmplă cu simulările atunci când media nu există.
La seminar La un joc de noroc, jucătorul mizează \(1\) leu pe un număr de la \(1\) la \(6\) (să spunem pe \(6\)), apoi se aruncă trei zaruri echilibrate. Dacă numărul ales apare pe exact \(k\) zaruri, \(k\in\{1,2,3\}\), jucătorul își primește miza înapoi și câștigă în plus \(k\) lei; dacă numărul nu apare pe niciun zar, pierde miza. Fie \(X\) câștigul net al jucătorului la o partidă.
Determinați tabelul de repartiție al lui \(X\).
Calculați \(\E[X]\), \(\Var(X)\) și \(\mathrm{SD}(X)\). Este jocul corect (adică are câștigul mediu egal cu zero)? Cât pierde în medie un jucător care joacă \(1000\) de partide?
Organizatorul păstrează premiile, dar schimbă miza: jucătorul plătește \(s\) lei, pe care îi pierde dacă numărul nu apare; dacă numărul apare pe \(k\) zaruri, își primește miza înapoi și câștigă \(k\) lei. Pentru ce valoare a mizei \(s\) jocul devine corect?
În R: calculați media și varianța din tabel, simulați \(10^5\) partide și reprezentați grafic media câștigurilor din primele \(n\) partide, în funcție de \(n\).
Laborator Schelet de cod pentru (d) — completați locurile marcate cu ___ (tabelul de repartiție este dat prin doi vectori, x și p; funcția medie_var va fi folosită în toată ședința; cumsum(castig) conține câștigul total după \(1,2,3,\dots\) partide):
Al doilea exercițiu exersează aceleași calcule pe o variabilă dată direct prin tabel și pune față în față cele două moduri de a calcula \(\E[g(X)]\): prin repartiția lui \(g(X)\) și prin formula de transport.
Dacă timpul permite Numărul \(X\) de tichete (cereri de asistență) primite într-o zi de echipa de suport a unei firme mici are repartiția \[ X\sim\begin{pmatrix}0&1&2&3&4\\0.1&0.3&0.3&0.2&0.1\end{pmatrix}. \]
Calculați \(\E[X]\), \(\Var(X)\) (din definiție și cu formula \(\E[X^2]-(\E[X])^2\)) și \(\mathrm{SD}(X)\).
Costul zilnic al serviciului este \(C=100+40X\) lei (un cost fix plus \(40\) de lei pentru fiecare tichet). Calculați \(\E[C]\), \(\Var(C)\) și \(\mathrm{SD}(C)\).
Echipa poate rezolva cel mult două tichete pe zi; celelalte sunt amânate. Fie \(Y=\max(X-2,0)\) numărul de tichete amânate. Calculați \(\E[Y]\) în două moduri: determinând repartiția lui \(Y\) și cu formula de transport. Este adevărat că \(\E[Y]=\max(\E[X]-2,0)\)?
Verificați rezultatele în R, prin calcul exact și prin simulare.
Laborator Schelet de cod pentru (d) — completați locurile marcate cu ___ (funcția medie_var este cea din Exercițiul 1; pmax(x - 2, 0) calculează maximul element cu element):
x <- 0:4
p <- c(0.1, 0.3, 0.3, 0.2, 0.1)
medie_var(x, p) # (a)
medie_var(___, p) # (b): valorile lui C, aceleași probabilități
g <- ___ # (c): valorile lui Y = g(X)
tapply(p, g, sum) # repartiția lui Y
___ # E[Y] cu formula de transport
set.seed(402)
X <- sample(x, 1e5, replace = TRUE, prob = p) # 100 000 de zile
c(medie = mean(X), varianta = var(X), amanate = ___,
P_1_3 = mean(X >= 1 & X <= 3))\(\E[X]=1.9\), \(\E[X^2]=4.9\), \(\Var(X)=1.29\), \(\mathrm{SD}(X)\approx1.136\).
\(\E[C]=176\) lei, \(\Var(C)=2064\), \(\mathrm{SD}(C)\approx45.43\) lei.
\(Y\sim\begin{pmatrix}0&1&2\\0.7&0.2&0.1\end{pmatrix}\) și \(\E[Y]=0.4\) (în ambele moduri); \(\max(\E[X]-2,0)=0\ne0.4\).
R dă exact valorile de mai sus; în simulare, media și varianța empirice sunt apropiate de \(1.9\) și \(1.29\), numărul mediu de tichete amânate de \(0.4\), iar frecvența zilelor cu \(1\)–\(3\) tichete de \(0.8\).
Până acum am calculat medii care există. Următorul exercițiu verifică ce se întâmplă cu simulările, și în particular cu mediile curente, atunci când media nu există.
Pentru acasă În jocul din Exemplul 16 din Cursul 3 se aruncă o monedă echilibrată până la apariția primului cap; dacă acesta apare la aruncarea \(K\), jucătorul primește \(X=2^K\) lei. La curs s-a arătat că \(X\) nu are medie finită.
Calculați \(\E[K]\). Presupunem apoi că banca poate plăti cel mult \(2^m\) lei, deci jocul se oprește după cel mult \(m\) aruncări, iar câștigul este \(X_m=2^{\min(K,m)}\). Arătați că \(\E[X_m]=m+1\). Care este miza corectă pentru \(m=10\), \(m=20\) și \(m=30\)?
Simulați \(10^5\) partide și calculați mediile curente pentru \(K\) și pentru \(X\). Ce observați?
Repetați de \(5\) ori estimarea mediei, de fiecare dată cu câte \(10^5\) partide, pentru \(K\) și pentru \(X\). Comparați cu jocul din Exercițiul 1.
\(\E[K]=2\); \(\E[X_m]=m+1\), deci miza corectă este \(11\), \(21\), respectiv \(31\) de lei pentru \(m=10,20,30\).
Mediile curente ale lui \(K\) se apropie de \(2\); cele ale lui \(X\) nu se stabilizează, ci cresc nemărginit, aproximativ ca \(\log_2n\) (\(\log_210^5\approx16.6\)), deși mediana lui \(X\) este \(2\).
Cele cinci estimări ale lui \(\E[K]\) diferă între ele cu aproximativ \(0.01\) (ca la jocul din Exercițiul 1), pe când cele cinci „estimări” pentru \(X\) diferă mult între ele și nu se așază în jurul vreunei valori; pentru jocul cu buget \(2^{10}\), media simulată este apropiată de \(11\).
3 Media și varianța repartițiilor uzuale
În multe probleme nu este nevoie să construim tabelul de repartiție: este suficient să recunoaștem repartiția (numărăm succese în \(n\) încercări independente? așteptăm primul succes? numărăm evenimente rare? extragem fără întoarcere?) și să folosim formulele din Secțiunea 9 din Cursul 3. Abaterea standard ne spune apoi între ce limite se află variabila „de obicei”.
La seminar Un fișier este împărțit în \(n=200\) de pachete, trimise printr-o rețea fără fir. Fiecare transmisie a unui pachet eșuează (pachetul se pierde) cu probabilitatea \(q=0.2\), independent de celelalte transmisii; un pachet pierdut este retransmis până când ajunge la destinație.
Fie \(X\) numărul de pachete pierdute la prima transmisie a celor \(200\) de pachete. Recunoașteți repartiția lui \(X\) și calculați \(\E[X]\), \(\Var(X)\) și \(\mathrm{SD}(X)\). Între ce limite se află \(X\) „de obicei”?
Fie \(N\) numărul de transmisii necesare pentru un pachet fixat. Recunoașteți repartiția lui \(N\) și calculați \(\E[N]\), \(\Var(N)\) și \(\mathrm{SD}(N)\).
Fie \(S\) numărul total de transmisii necesare pentru întregul fișier. Calculați \(\E[S]\), \(\Var(S)\) și \(\mathrm{SD}(S)\).
Protocolul renunță la un pachet după trei transmisii eșuate. Fie \(M=\min(N,3)\) numărul de transmisii efectuate pentru un pachet. Determinați repartiția și media lui \(M\), precum și numărul mediu de pachete abandonate dintr-un fișier.
Verificați rezultatele în R.
Laborator Schelet de cod pentru (e) — completați locurile marcate cu ___ (funcția medie_var este cea din Exercițiul 1; repartiția geometrică are o infinitate de valori, pe care le trunchiem la \(k\le60\); dgeom și rgeom numără eșecurile dinaintea primului succes):
n <- 200; q <- 0.2; p <- 1 - q
medie_var(0:n, ___) # (a): repartiția lui X
pbinom(___, n, q) - pbinom(___, n, q) # P(medie - 2 SD <= X <= medie + 2 SD)
k <- 1:60
medie_var(k, ___) # (b): repartiția lui N
sum(pmin(k, 3) * dgeom(k - 1, p)) # (d): E[min(N, 3)]
set.seed(404)
X <- rbinom(1e5, n, q) # pachete pierdute
N <- ___ # transmisii pentru un pachet
S <- replicate(1e4, ___) # transmisii pentru întregul fișier
rbind(X = c(medie = mean(X), varianta = var(X), sd = sd(X)),
N = c(mean(N), var(N), sd(N)),
S = c(mean(S), var(S), sd(S)))
c(E_M = mean(pmin(N, 3)), P_abandon = mean(N > 3))Repartiția Poisson modelează numărul de evenimente „rare” dintr-un interval de timp (Teorema 17 din Cursul 3 și Exercițiul 10 din Seminarul 3): foarte mulți utilizatori, fiecare trimițând o cerere într-o secundă dată cu o probabilitate foarte mică. Proprietatea ei caracteristică este că media și varianța coincid.
Pentru acasă Numărul \(X\) de cereri care sosesc într-o secundă la un server web are repartiția \(\Pois(3)\), iar numerele de cereri din secunde diferite sunt independente.
Calculați \(\E[X]\), \(\Var(X)\), \(\mathrm{SD}(X)\) și \(\PP\big(|X-\E[X]|\le2\,\mathrm{SD}(X)\big)\).
Serverul poate procesa cel mult \(5\) cereri pe secundă; cererile în plus sunt respinse. Fie \(R=\max(X-5,0)\) numărul de cereri respinse într-o secundă. Calculați \(\E[R]\) cu formula de transport. Ce proporție din cereri este respinsă pe termen lung?
Fie \(Y\) numărul de cereri sosite într-un minut. Calculați \(\E[Y]\), \(\Var(Y)\) și \(\mathrm{SD}(Y)\) și comparați raportul \(\mathrm{SD}/\text{medie}\) pentru o secundă și pentru un minut.
Verificați în R și determinați cea mai mică capacitate \(c\) pentru care \(\PP(X>c)\le0.01\).
\(\E[X]=\Var(X)=3\), \(\mathrm{SD}(X)=\sqrt3\approx1.732\); \(\PP\big(|X-3|\le3.46\big)=\PP(X\le6)\approx0.966\).
\(\E[R]\approx0.1346\) cereri respinse pe secundă, adică o proporție de \(\approx4.5\%\) din cereri.
\(\E[Y]=\Var(Y)=180\), \(\mathrm{SD}(Y)\approx13.42\); raportul \(\mathrm{SD}/\text{medie}\) este \(\approx0.58\) pentru o secundă și \(\approx0.075\) pentru un minut.
\(c=8\): \(\PP(X>8)\approx0.0038\), pe când \(\PP(X>7)\approx0.0119\). Simularea dă valori apropiate de \(3\), \(3\), \(0.1346\) și \(180\), \(180\).
Ultimul exercițiu al secțiunii compară două scheme de extragere și pregătește tema principală a ședinței: scrierea unei variabile ca sumă de indicatori.
Pentru acasă Un lot de \(N=100\) de plăci de bază conține \(M=10\) plăci defecte. Un inspector alege la întâmplare \(n=20\) de plăci și le testează. Fie \(X\) numărul de plăci defecte găsite dacă extragerea se face fără întoarcere (cazul obișnuit) și \(Y\) numărul de plăci defecte găsite dacă extragerea s-ar face cu întoarcere (fiecare placă testată este pusă înapoi în lot).
Recunoașteți repartițiile lui \(X\) și \(Y\) și calculați mediile, varianțele și abaterile standard.
Scrieți \(X\) și \(Y\) ca sume de indicatori și explicați de ce mediile coincid, iar varianțele nu.
Lotul este respins dacă se găsesc cel puțin \(4\) plăci defecte. În R: calculați probabilitatea de respingere în cele două scheme și verificați (a) prin simulare.
\(X\sim\HGeom(100,10,20)\): \(\E[X]=2\), \(\Var(X)=1.8\cdot\frac{80}{99}\approx1.4545\), \(\mathrm{SD}(X)\approx1.206\); \(Y\sim\Bin(20,0.1)\): \(\E[Y]=2\), \(\Var(Y)=1.8\), \(\mathrm{SD}(Y)\approx1.342\).
În ambele scheme, numărul de plăci defecte este \(I_1+\dots+I_{20}\), cu \(\E[I_j]=0.1\), deci media este \(2\). Cu întoarcere indicatorii sunt independenți; fără întoarcere sunt negativ corelați, \(\Cov(I_i,I_j)=-\frac1{1100}\), și \(\Var(X)=1.8-\frac{380}{1100}\approx1.4545\).
Probabilitatea de respingere este \(\approx0.110\) fără întoarcere și \(\approx0.133\) cu întoarcere; în simulare, mediile sunt apropiate de \(2\), iar varianțele de \(1.45\) (fără întoarcere) și \(1.8\) (cu întoarcere).
4 Liniaritatea mediei și metoda indicatorilor
Ajungem la tehnica centrală a ședinței. Multe variabile numără ceva: perechi, potriviri, pachete, comparații. Repartiția unei astfel de variabile este de obicei greu de găsit, dar media ei se obține imediat dacă o scriem ca sumă de indicatori: \(X=\Ind_{A_1}+\dots+\Ind_{A_m}\) implică \(\E[X]=\PP(A_1)+\dots+\PP(A_m)\), fără nicio ipoteză de independență (ca în Exercițiul 6). Rețeta are trei pași: (1) alegem evenimentele \(A_i\) astfel încât \(X\) să fie numărul celor care se realizează; (2) calculăm \(\PP(A_i)\); (3) adunăm. Pentru varianță avem nevoie, în plus, de probabilitățile \(\PP(A_i\cap A_j)\).
La seminar Într-o sală se află \(n\) persoane. Presupunem, ca în Exercițiul 9 din Seminarul 1, că zilele lor de naștere sunt independente și uniform repartizate pe cele \(365\) de zile ale anului. Acolo am calculat probabilitatea ca cel puțin două persoane să fie născute în aceeași zi; acum numărăm coincidențele: fie \(X\) numărul de perechi (neordonate) de persoane născute în aceeași zi.
Scrieți \(X\) ca sumă de indicatori și calculați \(\E[X]\). Evaluați pentru \(n=23\) și \(n=50\). Care este cel mai mic \(n\) pentru care \(\E[X]\ge1\)?
Arătați că indicatorii a două perechi diferite sunt independenți și deduceți \(\Var(X)\).
În R: scrieți o funcție
perechi(n)care simulează o sală cu \(n\) persoane și întoarce numărul de perechi; pentru \(n=23\) comparați media, varianța și \(\PP(X=0)\) cu valorile teoretice.
Laborator Schelet de cod pentru (c) — completați locurile marcate cu ___ (table(z) numără câte persoane sunt născute în fiecare zi):
perechi <- function(n, zile = 365) { # nr. de perechi cu aceeași zi
z <- ___ # zilele de naștere ale celor n persoane
___ # o zi cu k persoane dă C(k, 2) perechi
}
set.seed(407)
X <- replicate(2e4, perechi(23))
rbind(simulare = c(medie = mean(X), varianta = var(X), P0 = mean(X == 0)),
teoretic = c(___, ___, # E[X] și Var(X), de la (a), (b)
prod((365 - 0:22) / 365))) # P(X = 0), probabilitatea exactă
n <- c(10, 23, 30, 40, 60)
rbind(n = n,
simulare = sapply(n, function(n) mean(replicate(2000, perechi(n)))),
teoretic = ___) # formula mediei de la (a)În exercițiul precedent, pentru varianță a contat legătura dintre indicatorii a două perechi. Problema potrivirilor pune aceeași întrebare pentru indicatorii punctelor fixe ale unei permutări.
Dacă timpul permite Cele \(n\) lucrări ale unei grupe sunt returnate la întâmplare celor \(n\) studenți (câte una fiecăruia), adică după o permutare aleatoare. Fie \(X\) numărul de studenți care își primesc propria lucrare (numărul de puncte fixe ale permutării). În Exemplul 18 din Cursul 3 s-a arătat, cu metoda indicatorilor, că \(\E[X]=1\) pentru orice \(n\).
Pentru \(n=3\) scrieți toate permutările, determinați repartiția lui \(X\) și calculați \(\E[X]\) și \(\Var(X)\).
Pentru \(n\ge2\) oarecare, calculați \(\E[X^2]\) cu ajutorul indicatorilor și deduceți că \(\Var(X)=1\).
Comparați \(\Var(X)\) cu suma varianțelor indicatorilor. Sunt indicatorii independenți?
În R: verificați prin simulare (ca în Exercițiul 10 din Seminarul 1) pentru mai multe valori ale lui \(n\), enumerați toate permutările pentru \(n=4\) și comparați repartiția lui \(X\) pentru \(n=10\) cu repartiția \(\Pois(1)\).
Laborator Schelet de cod pentru (d) — completați locurile marcate cu ___ (o permutare aleatoare a numerelor \(1,\dots,n\) se obține cu sample(n); unique(r) păstrează valorile distincte ale vectorului r):
puncte_fixe <- function(n) ___ # nr. de puncte fixe
set.seed(408)
sapply(c(2, 3, 5, 10, 52), function(n) {
X <- replicate(5e4, puncte_fixe(n))
c(n = n, medie = mean(X), varianta = var(X))
})
g <- expand.grid(1:4, 1:4, 1:4, 1:4) # toate șirurile de lungime 4
perm <- g[apply(g, 1, function(r) ___), ] # păstrăm permutările
X4 <- apply(perm, 1, function(r) ___) # punctele fixe ale fiecăreia
table(X4) # din cele 24 de permutări
c(medie = mean(X4), varianta = mean(X4^2) - mean(X4)^2)
X <- replicate(1e5, puncte_fixe(10))
rbind(simulare = table(factor(X, levels = 0:5)) / 1e5,
Poisson = ___)\(X\sim\begin{pmatrix}0&1&3\\ \frac26&\frac36&\frac16\end{pmatrix}\), \(\E[X]=1\), \(\E[X^2]=2\), \(\Var(X)=1\).
(demonstrație) \(\E[X^2]=n\cdot\frac1n+n(n-1)\cdot\frac1{n(n-1)}=2\), deci \(\Var(X)=1\).
Suma varianțelor indicatorilor este \(1-\frac1n<1=\Var(X)\); indicatorii nu sunt independenți: \(\Cov(I_i,I_j)=\frac1{n^2(n-1)}>0\).
Media și varianța simulate sunt apropiate de \(1\) pentru toate valorile lui \(n\); pentru \(n=4\), dintre cele \(24\) de permutări \(9\) nu au niciun punct fix, \(8\) au unul, \(6\) au două și una are patru (media și varianța sunt exact \(1\)); pentru \(n=10\), frecvențele relative sunt apropiate de \(0.368\), \(0.368\), \(0.184\), \(0.061\), \(0.015\), \(0.003\), valorile repartiției \(\Pois(1)\).
Următoarele două exerciții sunt aplicațiile clasice ale liniarității mediei în informatică. În primul, variabila de interes se descompune într-o sumă de variabile geometrice (ca numărul total de transmisii din Exercițiul 4); în al doilea, într-o sumă de indicatori.
La seminar Fiecare pachet de cereale conține un cupon, ales la întâmplare (uniform și independent de celelalte pachete) dintre \(n\) tipuri. Fie \(T\) numărul de pachete cumpărate până când avem toate cele \(n\) tipuri. În Exemplul 20 din Cursul 3 s-a arătat că \(\E[T]=nH_n\), unde \(H_n=1+\frac12+\dots+\frac1n\).
Reluați descompunerea \(T=T_1+\dots+T_n\) și arătați că \(\Var(T)=n^2\big(1+\frac1{2^2}+\dots+\frac1{n^2}\big)-nH_n\).
Calculați \(\E[T]\) și \(\mathrm{SD}(T)\) pentru \(n=6\) (toate fețele unui zar), \(n=50\) și \(n=365\) (toate zilele anului ca zile de naștere).
În R: scrieți o funcție
colectioneaza(n)care simulează o colecție și întoarce numărul de pachete cumpărate; reprezentați histograma lui \(T\) și comparați media și varianța empirice cu formulele.Câte pachete trebuie cumpărate pentru a avea colecția completă cu probabilitatea de cel puțin \(0.95\)? Răspundeți prin simulare.
Laborator Schelet de cod pentru (c), (d) — completați locurile marcate cu ___ (colectioneaza2 simulează \(T\) direct ca sumă de variabile geometrice, conform descompunerii de la (a), și este mult mai rapidă pentru \(n\) mare; F_T(t, n) calculează valoarea exactă \(\PP(T\le t)=\sum_{j=0}^n(-1)^j\binom nj\big(1-\frac jn\big)^t\), dată de formula lui Poincaré, Teorema 15 din Cursul 1; funcțiile colectioneaza și F_T vor fi folosite și în exercițiile pentru acasă):
colectioneaza <- function(n) { # nr. de pachete până la colecția completă
avem <- logical(n) # avem[i] = TRUE dacă avem tipul i
t <- 0
while (___) { # cât timp lipsește măcar un tip
cupon <- sample(n, 1) # cuponul din pachetul curent
___ # îl trecem în colecție
t <- t + 1
}
t
}
medie_T <- function(n) ___ # n H_n
var_T <- function(n) ___ # formula de la (a)
sapply(c(6, 50, 365), function(n)
c(n = n, medie = medie_T(n), varianta = var_T(n), sd = sqrt(var_T(n))))
colectioneaza2 <- function(n) sum(rgeom(n, ___) + 1) # parametrii p_1, ..., p_n
set.seed(409)
T6 <- replicate(1e4, colectioneaza(6))
T50 <- replicate(1e4, colectioneaza2(50))
T365 <- replicate(1e4, colectioneaza2(365))
rbind(n6 = c(medie = mean(T6), varianta = var(T6), medie_T(6), var_T(6)),
n50 = c(mean(T50), var(T50), medie_T(50), var_T(50)))
hist(T50, breaks = 50, main = "", xlab = "numărul de pachete T (n = 50)")
abline(v = medie_T(50), lwd = 2) # media
sapply(list(n6 = T6, n50 = T50, n365 = T365), quantile, probs = ___) # (d)
F_T <- function(t, n) { # P(T <= t), valoarea exactă
j <- 0:n
___
}
t6 <- ___ # valoarea găsită prin simulare pentru n = 6
c(F_T(t6 - 1, 6), F_T(t6, 6)) # verificare exactăLa seminar Algoritmul Quicksort randomizat sortează \(n\) chei distincte astfel: alege la întâmplare (uniform) una dintre chei, numită pivot, o compară cu fiecare dintre celelalte chei, separând cheile mai mici de cele mai mari decât pivotul, apoi sortează recursiv, în același mod, cele două grupe. Fie \(C_n\) numărul total de comparații. În Exercițiul 12 din Cursul 3 s-a arătat că \[ \E[C_n]=\sum_{1\le i<j\le n}\frac{2}{j-i+1}=2(n+1)H_n-4n . \]
Pentru \(n=3\) determinați direct repartiția lui \(C_3\) și verificați formula.
Explicați, pe exemplul cheilor \(1,2,\dots,8\) și al perechii \((2,5)\), de ce a \(i\)-a și a \(j\)-a cheie în ordine crescătoare sunt comparate cu probabilitatea \(\frac{2}{j-i+1}\). Scrieți \(C_n\) ca sumă de indicatori și refaceți calculul mediei.
Comparați \(\E[C_n]\) cu numărul de comparații din cazul cel mai defavorabil și cu aproximarea \(2n\ln n\), pentru \(n\in\{10,100,1000\}\).
În R: scrieți o funcție recursivă
quicksort_comp(v)care întoarce numărul de comparații efectuate la sortarea vectoruluiv; simulați pentru \(n\in\{10,50,100,200,500\}\) și comparați media empirică cu formula exactă și cu \(2n\ln n\).
Laborator Schelet de cod pentru (d) — completați locurile marcate cu ___ (funcția recursivă se apelează pe ea însăși pentru cele două grupe; condiția de oprire este dată; quicksort_comp va fi folosită și în temă):
quicksort_comp <- function(v) { # numărul de comparații
n <- length(v)
if (n <= 1) return(0) # condiția de oprire
pivot <- v[sample(n, 1)] # pivot ales la întâmplare
___ # comparațiile cu pivotul + cele din grupe
}
medie_qs <- function(n) ___ # formula exactă 2(n + 1) H_n - 4n
set.seed(410)
C3 <- replicate(1e4, quicksort_comp(sample(3)))
c(table(C3) / 1e4, medie = mean(C3)) # comparați cu (a)
n <- c(10, 50, 100, 200, 500)
sim <- sapply(n, function(n) {
C <- replicate(300, quicksort_comp(sample(n)))
c(mean(C), sd(C))
})
rbind(n = n, simulare = sim[1, ], exact = sapply(n, medie_qs),
aprox = ___, sd = sim[2, ]) # aprox: 2 n ln n5 Varianța sumei de variabile independente
Am folosit deja de mai multe ori faptul că varianțele variabilelor independente se adună (Exercițiile 4, 5 și 9) și am văzut că, fără independență, apar covarianțe (Exercițiile 6 și 8). Ultimul exercițiu al părții principale adună aceste observații în jurul celei mai importante sume din statistică: media aritmetică a \(n\) măsurători.
Dacă timpul permite Un senzor măsoară o mărime a cărei valoare reală este \(\mu=20\). Fiecare măsurătoare este afectată de o eroare: \(X_i=\mu+\varepsilon_i\), unde erorile \(\varepsilon_1,\varepsilon_2,\dots\) sunt independente și uniform repartizate pe \(\{-2,-1,0,1,2\}\). Pentru a reduce eroarea, se fac \(n\) măsurători și se raportează media lor aritmetică \(\Xbar=\frac1n(X_1+\dots+X_n)\).
Calculați media și varianța \(\sigma^2\) ale unei măsurători.
Calculați \(\E[\Xbar]\), \(\Var(\Xbar)\) și \(\mathrm{SD}(\Xbar)\). Unde se folosește independența? Câte măsurători sunt necesare pentru ca \(\mathrm{SD}(\Xbar)\le0.1\)?
Caz particular. Dacă \(X_1,\dots,X_n\) sunt independente, cu repartiția \(\Bern(p)\), regăsiți varianța repartiției \(\Bin(n,p)\) și calculați media și varianța frecvenței relative \(\frac1n(X_1+\dots+X_n)\).
Ce se întâmplă dacă măsurătorile nu sunt independente? Analizați cazul extrem în care senzorul repetă de \(n\) ori aceeași valoare, \(X_1=X_2=\dots=X_n\), și comparați cu Exercițiile 6 și 8.
În R: verificați (b) prin simulare pentru \(n\in\{1,4,16,64,256\}\).
Laborator Schelet de cod pentru (e) — completați locurile marcate cu ___ (pentru fiecare \(n\) repetăm experimentul de \(10^4\) ori; ultima linie a tabelului este frecvența cu care media se află la cel mult \(0.5\) de valoarea reală):
set.seed(411)
mu <- 20
masoara <- function(n) ___ # media a n măsurători simulate
n <- c(1, 4, 16, 64, 256)
sim <- sapply(n, function(n) {
m <- replicate(1e4, masoara(n)) # 10 000 de medii
c(mean(m), var(m), mean(abs(m - mu) <= 0.5))
})
rbind(n = n, medie = sim[1, ], var_sim = sim[2, ], var_teor = ___,
P_aproape = sim[3, ])\(\E[X_i]=20\), \(\sigma^2=\Var(X_i)=2\) (\(\sigma\approx1.414\)).
\(\E[\Xbar]=20\), \(\Var(\Xbar)=\frac2n\), \(\mathrm{SD}(\Xbar)=\sqrt{2/n}\); independența se folosește pentru varianță (varianțele se adună), nu și pentru medie; sunt necesare \(n=200\) de măsurători.
\(\E[S_n]=np\), \(\Var(S_n)=np(1-p)\); frecvența relativă are media \(p\) și varianța \(\frac{p(1-p)}n\).
Dacă \(X_1=\dots=X_n\), atunci \(\Var(\Xbar)=\sigma^2=2\), oricât de mare ar fi \(n\); în general, covarianțele pozitive măresc varianța sumei, iar cele negative o micșorează.
Media mediilor simulate este apropiată de \(20\), iar varianța lor de \(\frac2n\): \(2\), \(0.5\), \(0.125\), \(0.031\), \(0.0078\); frecvența cu care media se află la cel mult \(0.5\) de valoarea reală este apropiată de \(0.2\), \(0.6\), \(0.87\), \(0.997\) și \(1\).
Exercițiul precedent descrie mecanismul din spatele interpretării frecvențiale a mediei (și al mediilor curente din Exercițiul 1). Enunțul precis — Legea Numerelor Mari — este demonstrat în Cursul 7.
- Media și varianța unei repartiții tabelate:
sum(x * p),sum((x - m)^2 * p); pe un eșantion simulat:mean,var,sd— cu condiția ca media să existe. - \(\E[g(X)]=\sum_xg(x)\PP(X=x)\) și, în general, \(\E[g(X)]\ne g(\E[X])\).
- Liniaritatea mediei nu cere independență: \(\E\big[\sum_i\Ind_{A_i}\big]=\sum_i\PP(A_i)\).
- Varianța sumei: pentru variabile independente varianțele se adună; altfel se adaugă covarianțele \(\Cov(X_i,X_j)=\E[X_iX_j]-\E[X_i]\E[X_j]\).
- Media a \(n\) variabile independente cu aceeași repartiție are media \(\mu\) și varianța \(\sigma^2/n\).
6 Exerciții suplimentare
Exercițiile următoare, cu răspunsuri finale, folosesc aceleași tehnici — indicatori, liniaritate, varianța sumei — și sunt destinate studiului individual.
Pentru acasă Un program parcurge un vector cu \(n\) valori distincte, așezate în ordine aleatoare (toate cele \(n!\) ordini sunt egal probabile), și reține maximul: variabila maxim este actualizată de fiecare dată când elementul curent este mai mare decât toate cele dinaintea lui. Un astfel de element se numește record (primul element este întotdeauna record). Fie \(R_n\) numărul de recorduri, adică numărul de actualizări ale maximului.
Arătați că \(\E[R_n]=H_n\) și evaluați pentru \(n=100\) și \(n=10^6\).
Se poate arăta că indicatorii recordurilor de pe poziții diferite sunt independenți. Deduceți \(\Var(R_n)\).
Verificați prin simulare pentru \(n=100\).
\(\E[R_n]=H_n\): \(H_{100}\approx5.19\) și \(\E[R_{10^6}]\approx14.39\).
\(\Var(R_n)=H_n-\big(1+\frac1{2^2}+\dots+\frac1{n^2}\big)\); pentru \(n=100\), \(\Var(R_{100})\approx3.552\) și \(\mathrm{SD}(R_{100})\approx1.88\).
Media și varianța simulate sunt apropiate de \(5.19\) și \(3.55\).
Pentru acasă O funcție de dispersie (hash) trimite fiecare dintre \(m\) chei într-una dintre cele \(n\) căsuțe ale unui tabel, uniform și independent de celelalte chei (echivalent: aruncăm \(m\) bile în \(n\) cutii).
Calculați numărul mediu de căsuțe goale și numărul mediu de căsuțe ocupate.
Spunem că o cheie produce o coliziune dacă ajunge într-o căsuță deja ocupată. Calculați numărul mediu de coliziuni și numărul mediu de perechi de chei aflate în aceeași căsuță.
Evaluați pentru \(n=1000\) și \(m=500\) și verificați prin simulare. Ce legătură există cu Exercițiile 7 și 9?
\(\E[\text{căsuțe goale}]=n\big(1-\frac1n\big)^m\), \(\E[\text{căsuțe ocupate}]=n\big[1-\big(1-\frac1n\big)^m\big]\).
\(\E[\text{coliziuni}]=m-n\big[1-\big(1-\frac1n\big)^m\big]\); numărul mediu de perechi este \(\binom m2\cdot\frac1n\).
Pentru \(n=1000\), \(m=500\): în medie \(606.4\) căsuțe goale, \(393.6\) ocupate, \(106.4\) coliziuni și \(124.75\) perechi; mediile simulate sunt apropiate de aceste valori. Cu \(n=365\) căsuțe, numărul mediu de perechi este \(\binom m2/365\), ca în Exercițiul 7; numărul mediu de căsuțe ocupate este numărul mediu de tipuri distincte de cupoane după \(m\) pachete (pentru \(n=50\), \(m=225\): \(\approx49.5\)).
Pentru acasă O monedă care arată cap cu probabilitatea \(p\) este aruncată de \(n\) ori. O serie este un bloc maximal de rezultate identice consecutive; de exemplu, șirul CCPCPPP are \(4\) serii: CC, P, C, PPP. Fie \(N\) numărul de serii.
Scrieți \(N\) cu ajutorul unor indicatori și calculați \(\E[N]\). Evaluați pentru \(n=100\), cu \(p=0.5\) și cu \(p=0.8\).
Calculați \(\Var(N)\). Pentru ce valoare a lui \(p\) indicatorii sunt necorelați?
Verificați prin simulare.
\(N=1+D_2+\dots+D_n\), cu \(D_i=\Ind_{\{X_i\ne X_{i-1}\}}\); \(\E[N]=1+2(n-1)pq\): \(50.5\) pentru \(p=0.5\) și \(32.68\) pentru \(p=0.8\) (\(n=100\)).
\(\Var(N)=2(n-1)\,pq\,(1-2pq)+2(n-2)\,pq\,(1-4pq)\); indicatorii sunt necorelați pentru \(p=\frac12\). Pentru \(n=100\): \(\Var(N)=24.75\) (\(p=0.5\)) și \(\approx32.83\) (\(p=0.8\)).
Mediile și varianțele simulate sunt apropiate de \(50.5\) și \(24.75\), respectiv \(32.68\) și \(32.83\).
Pentru acasă Fie \(X\) o variabilă aleatoare cu valori în \(\N=\{0,1,2,\dots\}\).
Arătați că \(X=\sum_{k\ge1}\Ind_{\{X\ge k\}}\) și deduceți formula \(\E[X]=\sum_{k\ge1}\PP(X\ge k)\).
Regăsiți cu această formulă media repartiției \(\Geom(p)\) și media variabilei \(M=\min(N,3)\) din Exercițiul 4.
Se aruncă trei zaruri echilibrate și se notează cu \(Z\) cel mai mare dintre cele trei numere. Calculați \(\E[Z]\).
În R: verificați (c) prin enumerare și regăsiți, cu funcția
F_Tdin Exercițiul 9, media \(\E[T]=14.7\) pentru colecționarul cu \(n=6\) tipuri.
(demonstrație) \(\E[X]=\sum_{k\ge1}\PP(X\ge k)\).
\(\E[N]=\sum_{k\ge1}q^{k-1}=\frac1p\); \(\E[M]=1+q+q^2=1.24\).
\(\E[Z]=6-\frac{225}{216}\approx4.958\).
Enumerarea dă \(\E[Z]\approx4.958\), iar suma probabilităților cozii, \(\sum_{t\ge0}\big(1-F_T(t)\big)\), dă \(14.7\).
7 Temă
La ruleta europeană (\(37\) de numere: \(0,1,\dots,36\), dintre care \(18\) roșii) un jucător mizează \(1\) leu. Dacă mizează pe un număr și acesta iese, câștigă \(35\) de lei; dacă mizează pe „roșu” și iese un număr roșu, câștigă \(1\) leu; altfel pierde miza. Calculați media și abaterea standard a câștigului net pentru fiecare dintre cele două pariuri și simulați în R câte \(10^5\) partide. Ce au în comun și prin ce diferă cele două pariuri?
Răspuns: media este \(-\frac1{37}\approx-0.027\) în ambele cazuri; abaterea standard este \(\approx5.84\) pentru pariul pe un număr și \(\approx1.00\) pentru pariul pe roșu.
Fie \(X\sim\Unif(\{-2,-1,0,1,2\})\). Calculați \(\E[X]\) și \(\Var(X)\), determinați repartiția lui \(Y=X^2\) și calculați \(\E[Y]\) și \(\Var(Y)\). Calculați \(\E[2^X]\) cu formula de transport și comparați cu \(2^{\E[X]}\).
Răspuns: \(\E[X]=0\), \(\Var(X)=2\); \(Y\sim\begin{pmatrix}0&1&4\\ \frac15&\frac25&\frac25\end{pmatrix}\), \(\E[Y]=2\), \(\Var(Y)=2.8\); \(\E[2^X]=1.55\ne1=2^{\E[X]}\).
Variabila \(X\) cu \(\PP(X=k)=\frac{1}{k(k+1)}\), \(k\ge1\), nu are medie finită (Exercițiul 3 din Cursul 3). Simulați în R \(10^5\) valori ale lui \(X\) și reprezentați grafic mediile curente; repetați de câteva ori și comentați.
Indicație: \(\PP(X>n)=\frac{1}{n+1}\), deci \(X\) se poate simula prin
floor(1 / runif(B)), underunif(B)generează \(B\) numere aleatoare uniforme în \((0,1)\). Mediile curente se calculează cucumsum(x) / seq_along(x); ele nu se stabilizează, ca în Exercițiul 3.Fie \(X\sim\Bin(10,0.3)\) și \(Y\sim\Pois(2)\) independente. Calculați \(\E[2X-3Y+5]\), \(\Var(2X-3Y+5)\), \(\E[XY]\), \(\E[X^2]\) și \(\E[(X-Y)^2]\).
Răspuns: \(5\); \(4\cdot2.1+9\cdot2=26.4\); \(6\); \(2.1+3^2=11.1\); \(\Var(X-Y)+(\E[X-Y])^2=4.1+1=5.1\).
Numărul de greșeli de tipar de pe o pagină a unei cărți are repartiția \(\Pois(0.5)\), independent de la o pagină la alta; cartea are \(200\) de pagini. Calculați media și abaterea standard a numărului total de greșeli, precum și media și abaterea standard a numărului de pagini fără nicio greșeală.
Răspuns: totalul are media \(100\) și abaterea standard \(10\); numărul de pagini fără greșeli este \(\Bin(200,e^{-0.5})\), cu media \(\approx121.3\) și abaterea standard \(\approx6.91\).
Zece persoane urcă într-un lift la parterul unei clădiri cu \(8\) etaje; fiecare coboară la un etaj ales la întâmplare, independent de ceilalți. Calculați numărul mediu de opriri ale liftului și verificați prin simulare în R.
Indicație: indicatorul evenimentului „liftul oprește la etajul \(j\)”, ca în Exercițiul 13. Răspuns: \(8\big[1-\big(\frac78\big)^{10}\big]\approx5.90\); în R,
mean(replicate(1e4, length(unique(sample(8, 10, replace = TRUE))))).În problema colecționarului de cupoane (Exercițiul 9), fie \(T_{(k)}\) numărul de pachete cumpărate până la obținerea a \(k\) tipuri distincte. Calculați \(\E[T_{(k)}]\) și evaluați pentru \(n=6\), \(k=3\) și pentru \(n=50\), \(k=25\). Modificați funcția
colectioneazapentru a verifica prin simulare.Răspuns: \(\E[T_{(k)}]=\sum_{i=1}^k\frac{n}{n-i+1}=n\,(H_n-H_{n-k})\); \(1+\frac65+\frac64=3.7\), respectiv \(50\,(H_{50}-H_{25})\approx34.16\): prima jumătate a colecției se obține repede. În funcție se înlocuiește condiția
!all(avem)cusum(avem) < k.Modificați funcția
quicksort_compdin Exercițiul 10 astfel încât pivotul să fie întotdeauna primul element al vectorului. Comparați numărul de comparații pentru un vector deja sortat (1:n) cu numărul mediu de comparații pentru o permutare aleatoare (sample(n)), pentru \(n\in\{50,100,200\}\).Indicație: se înlocuiește
v[sample(n, 1)]cuv[1]. Pentru vectorul sortat se obțin \(\frac{n(n-1)}{2}\) comparații (cazul cel mai defavorabil), iar pentru o permutare aleatoare media rămâne \(2(n+1)H_n-4n\) — de aceea pivotul se alege la întâmplare.