Bernoullis lov
Bernoullis lov
|
|
|
|
Innstillinger
|
s∈[0,1]{\ displaystyle p \ in [0,1]} q=1-s{\ displaystyle q = 1-p}
|
---|
Brukerstøtte
|
k∈{0,1}{\ displaystyle k \ in \ {0,1 \}}
|
---|
Massefunksjon
|
{qtil k=0stil k=1{\ displaystyle \ left \ {{\ begin {array} {ll} q & {\ mbox {for}} k = 0 \\ p & {\ mbox {for}} k = 1 \ end {array}} \ right .}
|
---|
Distribusjonsfunksjon
|
{0til k<0qtil 0≤k<11til k≥1{\ displaystyle \ left \ {{\ begin {array} {ll} 0 & {\ mbox {for}} k <0 \\ q & {\ mbox {for}} 0 \ leq k <1 \\ 1 & { \ mbox {for}} k \ geq 1 \ end {array}} \ høyre.}
|
---|
Håp
|
s{\ displaystyle p}
|
---|
Median
|
{0hvis s<1/2[0,1]hvis s=1/21hvis s>1/2{\ displaystyle \ left \ {{\ begin {array} {ll} 0 & {\ text {si}} p <1/2 \\\ left [0,1 \ right] & {\ text {si}} p = 1/2 \\ 1 & {\ text {si}} p> 1/2 \ end {array}} \ høyre.}
|
---|
Mote
|
{0hvis s<q0,1hvis s=q1hvis s>q{\ displaystyle \ left \ {{\ begin {array} {ll} 0 & {\ text {si}} p <q \\ 0.1 & {\ text {si}} p = q \\ 1 & {\ text { si}} p> q \ end {array}} \ høyre.}
|
---|
Forskjell
|
sq{\ displaystyle pq}
|
---|
Asymmetri
|
q-ssq{\ displaystyle {\ frac {qp} {\ sqrt {pq}}}}
|
---|
Normalisert kurtose
|
1-6sqsq{\ displaystyle {\ frac {1-6pq} {pq}}}
|
---|
Entropi
|
-qln(q)-sln(s){\ displaystyle -q \ ln (q) -p \ ln (p)}
|
---|
Moment-genererende funksjon
|
q+set{\ displaystyle q + pe ^ {t}}
|
---|
Karakteristisk funksjon
|
q+seJegt{\ displaystyle q + pe ^ {it}}
|
---|
Sannsynlighetsgeneratorfunksjon
|
q+st{\ displaystyle q + pt}
|
---|
I matematikk og mer presist i sannsynlighetsteori , Bernoullis lov , oppkalt etter den sveitsiske matematikeren Jacques Bernoulli , angir sannsynligheten lov av en diskret tilfeldig variabel som tar verdien 1 med sannsynligheten p og 0 med sannsynligheten Q = 1 - p .
Eksempel
For eksempel, i et myntkast er kastet av en velbalansert mynt haler med sannsynlighet 1/2 og hoder med sannsynlighet 1/2. En mynt er kanskje ikke balansert, og i dette tilfellet får vi hoder med sannsynlighet p ≠ 1/2 og hoder med sannsynlighet q = 1 - p ≠ 1/2. Ved å betegne hoder med 1 og hode etter 0, får vi en Bernouilli-fordeling.
Som regel. Bernoullis lov er loven for den tilfeldige variabelen som koder resultatet av en test som kun innrømmer to utfall ( Bernoulli-test ): 1 for "suksess", 0 for "fiasko", eller hva som helst navnet. Som vi gir til de to utfallene av et slikt tilfeldig eksperiment.
Definisjon
En tilfeldig variabel etter Bernoullis lov kalles en Bernoulli-variabel. Mer formelt følger en tilfeldig variabel X Bernoullis sannsynlighetslov p if
P(X=x)={shvis x=1,1-shvis x=0,0Hvis ikke.{\ displaystyle \ mathbb {P} (X = x) = \ left \ {{\ begin {array} {ll} p & \ quad {\ mbox {si}} x = 1, \\ 1-p & \ quad {\ mbox {si}} x = 0, \\ 0 & \ quad {\ mbox {ellers.}} \ end {array}} \ right.}eller, ekvivalent
P(X=x)=sx(1-s)1-x,x∈{0,1}{\ displaystyle \ mathbb {P} (X = x) = p ^ {x} (1-p) ^ {1-x}, x \ in \ {0,1 \}}
Eiendommer
Den matematiske forventningen til en tilfeldig variabel i Bernoulli er p og variansen er p (1 - p ).
Den kurtosis har en tendens til uendelig for høye og lave verdier av p , men for p = 1/2 Bernoulli fordelingen har et lavere kurtose enn noen annen fordeling, det vil si en.
Mer generelt er ethvert målbart kart med en verdi i {0,1} en Bernoulli-variabel. Med andre ord følger en indikatorfunksjon av en hendelse en Bernoulli-lov.
Omvendt, for alle Bernoulli-variabler X definert på (Ω, A , P), kan vi finne et målbart sett B slik at X og indikatorfunksjonen til B er nesten helt like: enhver Bernoulli-variabel er nesten helt lik en funksjonsindikator.
Bundne distribusjoner
Hvis X 1 , X 2 ,…, X n er Bernoulli tilfeldige variabler av parameter p , uavhengige og identisk fordelt, så er summen N også en tilfeldig variabel som følger binomialoven :
IKKE=∑k=1ikkeXk∼B(ikke,s).{\ displaystyle N = \ sum _ {k = 1} ^ {n} X_ {k} \ sim {\ mathcal {B}} (n, p).}
Spesielt følger en tilfeldig Bernouilli-variabel med parameter p en binomialfordeling B(1,s).{\ displaystyle {\ mathcal {B}} (1, s).}
La X 1, n , X 2, n , ..., X a n , n være en rekke uavhengige Bernoulli tilfeldige variabler, med respektive parametere p k , n . Vi merker det
Sikke=∑k=1påikkeXk,ikkeogλikke = E[Sikke]=∑k=1påikkesk,ikke. {\ displaystyle S_ {n} = \ sum _ {k = 1} ^ {a_ {n}} \, X_ {k, n} \ quad {\ text {and}} \ quad \ lambda _ {n} \ = \ \ mathbb {E} [S_ {n}] = \ sum _ {k = 1} ^ {a_ {n}} \, p_ {k, n}. \}
Ulikhet i Le Cam - For ethvert sett A med naturlige tall,
|P(Sikke∈PÅ)-∑k∈PÅλikkeke-λikkek!| ≤ ∑k=1påikkesk,ikke2.{\ displaystyle \ left | \ mathbb {P} \ left (S_ {n} \ in A \ right) - \ sum _ {k \ in A} \, {\ frac {\ lambda _ {n} ^ {k} \, e ^ {- \ lambda _ {n}}} {k!}} \ right | \ \ leq \ \ sum _ {k = 1} ^ {a_ {n}} \, p_ {k, n} ^ {2}.}
Spesielt hvis følgende to betingelser er oppfylt:
- limikkeλikke=λ>0, {\ displaystyle \ lim _ {n} \ lambda _ {n} \, = \, \ lambda> 0, \}
- limikke∑k=1påikkesk,ikke2=0, {\ displaystyle \ lim _ {n} \ sum _ {k = 1} ^ {a_ {n}} \, p_ {k, n} ^ {2} \, = \, 0, \}
deretter konvergerer S n i lov mot Poisson-loven til parameter λ .
De to forholdene ovenfor forårsaker det
- limikkemaks1≤k≤påikkesk,ikke=0, {\ displaystyle \ lim _ {n} \ max _ {1 \ leq k \ leq a_ {n}} \, p_ {k, n} \, = \, 0, \}
- limikkepåikke=+∞. {\ displaystyle \ lim _ {n} a_ {n} \, = \, + \ infty. \}
Konsekvens: Poisson-paradigme - Summen S n av et stort antall uavhengige Bernoulli-variabler med liten parameter følger omtrent Poisson-fordelingen av parameterE[Sikke]. {\ displaystyle \ mathbb {E} [S_ {n}]. \}
Poissons lov kommer ofte inn når man teller sjeldne hendelser som selvmord på barn, ankomst av båter i en havn eller ulykker på grunn av hestespark i hærer (studie av Ladislaus Bortkiewicz ). Antallet sjeldne hendelser gjøres ofte gjennom en sum av Bernoulli-variabler , og sjeldenhetene til hendelser betyr at parametrene til disse Bernoulli-variablene er små (sannsynligheten for at hver hendelse inntreffer er derfor liten.)
Merknader:
- Et kjent, spesielt tilfelle av Poisson-paradigmet er konvergensen av binomialoven til parametrene n og λ / n mot Poisson-loven til parameteren λ, som i Le Cams ulikhet tilsvarer valgene a n = n , p k, n = λ / n , λ n = λ.
- Dette paradigmet forblir relevant under visse forhold hvis vi slapper av uavhengighetshypotesen.
- Det spesielle tilfellet a n = n , p k, n = λ / n , λ n = λ av ulikheten til Le Cam spesifiserer hastigheten på konvergens av binomiloven til parametrene n og λ / n mot Poisson-loven til parameteren λ : Le Cam-ulikheten gir da en økning i feilen med λ 2 / n .
Måleprogrammer
Å skrive en tilfeldig variabel N , som teller et antall hendelser i en gitt situasjon, for eksempel summen av en familie av Bernoulli-variabler, gjør det ofte mulig å bare beregne forventningen til N , som summen av parametrene til disse variablene av Bernoulli:
{IKKE=∑Jeg∈JegXJeg}⇒{E[IKKE]=∑Jeg∈JegP(XJeg=1)}.{\ displaystyle \ left \ {N = \ sum _ {i \ i I} X_ {i} \ right \} \ quad \ Rightarrow \ quad \ left \ {\ mathbb {E} [N] = \ sum _ {i \ i I} \ mathbb {P} (X_ {i} = 1) \ høyre \}.}
Vi bruker det faktum at for en Bernoulli-variabel er parameteren p både forventning og sannsynlighet for verdien 1:
E[XJeg] = P(XJeg=1).{\ displaystyle \ mathbb {E} [X_ {i}] \ = \ \ mathbb {P} (X_ {i} = 1).}
Denne metoden forenkler også beregningen av variansen til N , i noen tilfeller:
Var(IKKE)=∑(Jeg,j)∈Jeg2(P(XJeg=1 et Xj=1)-P(XJeg=1)P(Xj=1)),{\ displaystyle {\ textrm {Var}} (N) = \ sum _ {(i, j) \ i I ^ {2}} {\ big (} \ mathbb {P} (X_ {i} = 1 \ mathrm {~ og ~} X_ {j} = 1) - \ mathbb {P} (X_ {i} = 1) \ mathbb {P} (X_ {j} = 1) {\ big)},}
og når jeg blir bestilt, takket være symmetriegenskapen til kovarians ,
Var(IKKE)=∑Jeg∈JegP(XJeg=1)(1-P(XJeg=1))+2∑(Jeg<j)∈Jeg2(P(XJeg=1 et Xj=1)-P(XJeg=1)P(Xj=1)).{\ displaystyle {\ textrm {Var}} (N) = \ sum _ {i \ i I} \ mathbb {P} (X_ {i} = 1) (1- \ mathbb {P} (X_ {i} = 1)) + 2 \ sum _ {(i <j) \ i I ^ {2}} {\ big (} \ mathbb {P} (X_ {i} = 1 \ mathrm {~ og ~} X_ {j} = 1) - \ mathbb {P} (X_ {i} = 1) \ mathbb {P} (X_ {j} = 1) {\ big)}.}
Nedenfor er noen av de mest representative eksemplene på denne mye brukte tellemetoden.
undersøkelse
Her teller vi for eksempel antall N med "ja" -svar i et utvalg av befolkningen, under en undersøkelse, for å utlede andelen "ja". En serie med n tilfeldige tegninger er laget av en populasjon. Det samme spørsmålet blir stilt til hver av de n individene som er trukket tilfeldig. Målet er å estimere andelen p av individer av den totale befolkningen som ville ha svart "ja" (hvis de hadde blitt stilt spørsmålet) ved å bruke antall N individer som faktisk svarte "ja" blant de n personene som ble intervjuet. Vi merker at N kan skrives
IKKE=∑k=1ikkeXk,{\ displaystyle N = \ sum _ {k = 1} ^ {n} X_ {k},}
hvor X 1 , X 2 , ..., X n er definert av
Xk=11lpå re´soikkese du k-e``me JegikkedJegvJegdu est ouJeg,{\ displaystyle X_ {k} \, = \, 1 \! \! \! 1 _ {\ mathrm {la ~ r {\ acute {e}} respons ~ du} \ k \ mathrm {- {\ grave {e }} meg ~ individ ~ er} \ ja},}
dvs. at X k er lik 1 eller 0, avhengig av om svaret til det k- th individet er "ja" eller "nei". X k er en indikatorfunksjon og er derfor en Bernoulli-variabel. Parameteren er "sannsynligheten for å svare" ja "", nemlig andelen "ja" i den totale befolkningen, det vil si p . Så det har vi gjort
E[IKKE]=∑1≤Jeg≤ikkeP(XJeg=1) = ikkes,ogE[IKKE/ikke]=s.{\ displaystyle \ mathbb {E} [N] = \ sum _ {1 \ leq i \ leq n} \ mathbb {P} (X_ {i} = 1) \ = \ np, \ qquad {\ text {and} } \ qquad \ mathbb {E} [N / n] = s.}
Derav ideen, foreslått av Bernoulli i sitt banebrytende arbeid Ars Conjectandi , om å estimere denne andelen p a priori ukjent ved å bruke N / n- andelen "ja" i utvalget, som er kjent . For å bestemme nøyaktigheten av dette estimatet, foreslo Bernoulli i det samme arbeidet de første ulikhetene i konsentrasjon (for binomialoven). En enklere tilnærming (men å produsere grovere ulikheter i konsentrasjon) enn Bernoullis, ville være å beregne variansen til N , i ideen om å anvende ulikheten til Bienaymé-Tchebychev . På dette punktet er det nødvendig å spesifisere
- hvis trekningene fant sted med rabatt (dvs. det er mulig at den samme personen blir avhørt flere ganger), noe som innebærer uavhengighet av X k , og gir
Var(IKKE)=∑1≤Jeg≤ikkeVar(XJeg) = ikkes(1-s).{\ displaystyle {\ text {Var}} (N) = \ sum _ {1 \ leq i \ leq n} {\ text {Var}} (X_ {i}) \ = \ np (1-p).}
I saken "med erstatning" følger N binomialoven.
- hvis trekningene skjedde uten erstatning (dvs. ved å unngå å avhøre den samme personen to ganger), i hvilket tilfelle X k ikke er uavhengig. Så
Var(IKKE)=∑1≤Jeg≤ikkeVar(XJeg) +2∑1≤Jeg<j≤ikkeCov(XJeg,Xj).{\ displaystyle {\ text {Var}} (N) = \ sum _ {1 \ leq i \ leq n} {\ text {Var}} (X_ {i}) \ +2 \ sum _ {1 \ leq i <j \ leq n} {\ text {Cov}} (X_ {i}, X_ {j}).}
I dette tilfellet følger N den
hypergeometriske loven , og beregningene krever å vite den totale størrelsen på populasjonen, som vil bli betegnet med T nedenfor. Vi har
Cov(XJeg,Xj)=E[XJegXj]-E[XJeg]E[Xj]=P(XJegXj=1)-s2.{\ displaystyle {\ text {Cov}} (X_ {i}, X_ {j}) = \ mathbb {E} [X_ {i} X_ {j}] - \ mathbb {E} [X_ {i}] \ mathbb {E} [X_ {j}] = \ mathbb {P} (X_ {i} X_ {j} = 1) -p ^ {2}.}
Faktisk er variabelen Z = X i X j verdt 0 eller 1, og er derfor en Bernoulli-variabel. For i <j har vi da
P(XJegXj=1)=sTTsT-1T-1ogCov(XJeg,Xj)=-s(1-s)T-1,{\ displaystyle \ mathbb {P} (X_ {i} X_ {j} = 1) \, = \, {\ frac {pT} {T}} \, {\ frac {pT-1} {T-1} } \, \ quad {\ text {and}} \ quad {\ text {Cov}} (X_ {i}, X_ {j}) = - {\ frac {p (1-p)} {T-1} },}
deretter bruker du egenskapene til variansen,
Var(IKKE) = s(1-s)ikke(T-ikke)T-1.{\ displaystyle {\ text {Var}} (N) \ = \ {\ frac {p (1-p) n (Tn)} {T-1}}.}
I de to tilfellene som er vurdert ovenfor, er loven om N kjent eksplisitt. Å beregne forventningen om N ved å bruke nedbrytningen av N til summen av Bernoulli-variabler, presentert ovenfor, er imidlertid enklere enn å beregne forventningen om N ved hjelp av overføringssatsen :
E[IKKE]=∑1≤k≤ikke kP(IKKE=k).{\ displaystyle \ mathbb {E} [N] = \ sum _ {1 \ leq k \ leq n} \ k \, \ mathbb {P} (N = k).}
Den samme merknaden gjelder beregningen av variansen.
Her teller vi antallet N av elementene mindre enn det reelle tallet x i et utvalg av tilfeldige tall, for å utlede andelen av slike tall, som kalles den empiriske fordelingsfunksjonen . I statistikk , den empiriske fordelingsfunksjonen tilknyttet en n - prøven er fordelingsfunksjonen av sannsynlighets lov som tildeler den sannsynlighet 1 / n for hver av de n tallene i denne prøven.
La være et utvalg av variable IID med verdier som har til felles fordelingsfunksjonen F ( x ): den empiriske fordelingsfunksjonen tilknyttet prøven er en trinnfunksjon definert av
X1,X2,...,Xikke {\ displaystyle \ X_ {1}, X_ {2}, \, \ dots \ ,, X_ {n} \} R {\ displaystyle \ \ mathbb {R} \}
Fikke(x) {\ displaystyle \ F_ {n} (x) \} X1,X2,...,Xikke {\ displaystyle \ X_ {1}, X_ {2}, \, \ dots \ ,, X_ {n} \}
Fikke(x) = ikkeombre d′e´le´meikkets Jegikkefe´rJegeurs på`` x dpåikkes l′e´vs.hpåikketJeglloikkeikke = 1ikke ∑Jeg=1ikke 11XJeg≤x.{\ displaystyle F_ {n} (x) \ = \ {\ frac {\ mathrm {number ~ of {\ acute {e}} {\ acute {e}} elementene ~ inf {\ acute {e}} ler ~ {\ grave {a}}} \ x \ \ mathrm {i ~ {\ acute {e}} eksemplet}} {n}} \ = \ {\ frac {1} {n}} \ \ sum _ {i = 1} ^ {n} \ 1 \! \! 1_ {X_ {i} \ leq x}.}
For en fast x er variabelen en Bernoulli-variabel, med parameteren p = F ( x ). Derfor fordeles variabelen i henhold til en binomial fordeling, med gjennomsnittet nF ( x ) og variansen nF ( x ) (1 - F ( x )).
11XJeg≤x {\ displaystyle \ 1 \! \! 1_ {X_ {i} \ leq x} \} IKKE=ikkeFikke(x) {\ displaystyle \ N = nF_ {n} (x) \}
For forskjellige betydninger av ordet " konvergens " konvergerer den empiriske fordelingsfunksjonen til fordelingsfunksjonen F av når prøvestørrelsen øker. For eksempel, ved å beregne variansen til F n ( x ), har vi for alle reelle x ,
XJeg, {\ displaystyle \ X_ {i}, \}
E[(Fikke(x)-F(x))2] = F(x)(1-F(x))ikke ⟶ 0,{\ displaystyle \ mathbb {E} \ left [\ left (F_ {n} (x) -F (x) \ right) ^ {2} \ right] \ = \ {\ frac {F (x) (1- F (x))} {n}} \ \ longrightarrow \ 0,}
som beviser konvergensen til F n ( x ) mot F ( x ), i L 2 .
Den oppholdstiden (eller antall passeringer ) av en Markov-kjeden i en tilstand er en stokastisk variabel med verdiene definert av
X=(Xikke)ikke≥0{\ displaystyle \ scriptstyle \ X = (X_ {n}) _ {n \ geq 0} \ quad} Jeg {\ displaystyle \ scriptstyle \ i \} S(Jeg) {\ displaystyle \ scriptstyle \ S (i) \} IKKE¯=IKKE∪{+∞}, {\ displaystyle \ scriptstyle \ {\ overline {\ mathbb {N}}} = \ mathbb {N} \ cup \ {+ \ infty \}, \}
S(Jeg) = ∑k≥011Xk=Jeg.{\ displaystyle S (i) \ = \ \ sum _ {k \ geq 0} 1 \! \! 1_ {X_ {k} = i}.}
Staten sies å være forbigående eller tilbakevendende, avhengig av om den er 0 eller 1, eller avhengig av om den gjennomsnittlige oppholdstiden i i , fra og med i , er endelig eller uendelig. Som det er en (uendelig) sum av Bernoulli-variabler, betyr det å diskutere dette siste punktet å diskutere konvergensen i serien
Jeg {\ displaystyle \ scriptstyle \ i \} PJeg(S(Jeg)=+∞){\ displaystyle \ scriptstyle \ \ mathbb {P} _ {i} \ left (S (i) = + \ infty \ right)} EJeg[S(Jeg)],{\ displaystyle \ scriptstyle \ \ mathbb {E} _ {i} \ left [S (i) \ right],} S(Jeg) {\ displaystyle \ scriptstyle \ S (i) \}
EJeg[S(Jeg)]=∑k≥0sJeg,Jeg(k),{\ displaystyle \ \ mathbb {E} _ {i} \ left [S (i) \ right] = \ sum _ {k \ geq 0} p_ {i, i} ^ {(k)},}
hvor er parameteren til den berørte Bernoulli-variabelen, dvs.
sJeg,Jeg(k){\ displaystyle \ scriptstyle \ p_ {i, i} ^ {(k)}}
sJeg,Jeg(k)=PJeg(Xk=Jeg),{\ displaystyle \ p_ {i, i} ^ {(k)} = \ mathbb {P} _ {i} (X_ {k} = i),}
hvilken parameter er også en diagonal term for kraften k- th av overgangsmatrisen til Markov-kjeden som er vurdert.
sJeg,Jeg(k){\ displaystyle \ scriptstyle \ p_ {i, i} ^ {(k)}}
Tildelingsproblemer: bokser og baller
Vi teller her antall N tomme bokser, i et tilfeldig eksperiment med bokser og kuler, med mange tolkninger. Vi kaster m baller tilfeldig i n bokser, et sannsynlig eksperiment der en elementær hendelse ω er en anvendelse av i : ω ( k ) er nummeret på boksen der ballnummeret k er lagret . Således ω ( k ) er tilfeldige variabler uavhengig og ensartet på A . Kartet N , som til en fordeling ω av m baller i n bokser assosierer antall N ( ω ) av tomme bokser ved enden av denne fordeling ω , kan betraktes som en sum av Bernoulli-variabler: ja,
B=[[1,m]] {\ displaystyle \ scriptstyle \ B = [\! [1, m] \!] \} PÅ=[[1,ikke]] {\ displaystyle \ scriptstyle \ A = [\! [1, n] \!] \}
IKKE=∑k=1ikkeXk,{\ displaystyle N = \ sum _ {k = 1} ^ {n} X_ {k},}
hvor X 1 , X 2 ,…, X n er definert av
Xk=11lpå k-e``me boJegte est vJegde,{\ displaystyle X_ {k} \, = \, 1 \! \! 1 _ {\ mathrm {la} \ k \ mathrm {- {\ grave {e}} meg ~ boks ~ er} \ tom},}
dvs. X k er 1 eller 0, avhengig av om k- th-boksen er tom eller ikke. Å være en hendelsesindikatorfunksjon, er X k derfor en Bernoulli-variabel. Dens parameter er “sannsynligheten for å være tom”, dvs. sannsynligheten for at hver av de m ballene har unngått boksen n ° k . Hver av m- ballene har en sannsynlighet 1 / n for å falle i boksen n ° k , og tildelingen av m- ballene er uavhengige, vi oppnår
E[Xk]=P(Xk=1) = (1-1ikke)m,{\ displaystyle \ mathbb {E} [X_ {k}] = \ mathbb {P} (X_ {k} = 1) \ = \ \ left (1 - {\ tfrac {1} {n}} \ right) ^ {m},}
deretter
E[IKKE]=∑1≤k≤ikkeP(Xk=1) = ikke(1-1ikke)m.{\ displaystyle \ mathbb {E} [N] = \ sum _ {1 \ leq k \ leq n} \ mathbb {P} (X_ {k} = 1) \ = \ n \ left (1 - {\ tfrac { 1} {n}} \ høyre) ^ {m}.}
Takket være denne nedbrytningen i sum av Bernoulli-variabler, kan man oppnå en presis ulikhet i konsentrasjon for N , ved å bruke ulikheten til Azuma . Denne ulikheten i konsentrasjon gjør det mulig å rettferdiggjøre en tilnærmet statistisk tellemetode basert på N- statistikken , og som for eksempel kan brukes til å oppdage et datavirusangrep.
Merk: Sannsynloven til N uttrykkes eksplisitt i form av Stirling-tall av den andre typen, men de oppnådde uttrykkene er ikke særlig gunstige for numerisk beregning, derav behovet for en tilnærming via Azuma-ulikheten .
Vi kaster n ball nummerert tilfeldig i n nummererte bokser, hver av disse boksene inneholder maksimalt en ball, et sannsynlig eksperiment der en elementær hendelse er en permutasjon av elementene til : er, her igjen, nummeret på boksen der lagres ballnummer k . Vi antar at de forskjellige mulige fordelingene (permutasjonene) er like sannsynlige. Søknaden N , som til en fordeling av n kuler i n bokser knytter antall kuler som har samme nummer som boksen der de er lagret i på slutten av denne fordelingen, kan sees på som en sum av Bernoulli-variabler: i virkeligheten,
ω{\ displaystyle \ omega}[[1,ikke]]{\ displaystyle [\! [1, n] \!]}ω(k){\ displaystyle \ omega (k)}ω{\ displaystyle \ omega}IKKE(ω){\ displaystyle N (\ omega)}ω{\ displaystyle \ omega}
IKKE=∑k=1ikkeXk{\ displaystyle N = \ sum _ {k = 1} ^ {n} X_ {k}},
hvor X 1 , X 2 ,…, X n er definert av
Xk=11k er et fast punkt av ω{\ displaystyle X_ {k} \, = \, 1 \! \! 1_ {k {\ text {er et fast punkt på}} \ omega}},
dvs. X k er 1 eller 0, avhengig av om k- th-boksen inneholder k- th-ballen eller ikke. Å være en hendelsesindikatorfunksjon, er X k derfor en Bernoulli-variabel. Parameteren er 1 / n . Vi får det
E[IKKE]=∑1≤k≤ikke 1ikke = 1{\ displaystyle \ mathbb {E} [N] = \ sum _ {1 \ leq k \ leq n} \ {\ tfrac {1} {n}} \ = \ 1}.
Ved å følge en tilnærming som den som ble fulgt for en undersøkelse (sak uten erstatning) , finner vi det
P(XJegXj=1)=1ikke(ikke-1),Cov(XJeg,Xj)=1ikke2(ikke-1),deretterVar(IKKE) = 1{\ displaystyle \ mathbb {P} (X_ {i} X_ {j} = 1) \, = \, {\ tfrac {1} {n (n-1)}}, \ quad {\ text {Cov}} (X_ {i}, X_ {j}) = {\ tfrac {1} {n ^ {2} (n-1)}}, \ quad {\ text {deretter}} \ quad {\ text {Var}} (N) \ = \ 1}.
Den inklusjons utelukkelse prinsipp gjør det mulig å beregne nøyaktig lov av N , og å merke seg at denne loven konvergerer, når n har en tendens til uendelig, mot Poisson lov av parameter 1 (som for øvrig har 1 til forventningene, og har også 1 for avvik). Dette eksemplet er representativt: generelt er Poisson-loven til parameteren en god tilnærming til loven til summen N av et stort antall Bernoulli-variabler med liten parameter og lite korrelert. Igjen, en fordel med å skrive N som en sum av Bernoulli-variabler, er å tillate en beregning av forventningen og avviket til N raskere enn fra det eksplisitte uttrykket for lov nr .
E[IKKE]{\ displaystyle \ mathbb {E} [N]}
Antall forekomster av et ord i en tekst (å skrive monkey paradox )
Vi betrakter en tekst ω = ω 1 ω 2 ω 3 ... ω m bestående av m blokkbokstaver, bemerket ω i , 1 ≤ i ≤ m , hvilke blokkbokstaver alle er tegnet tilfeldig, med erstatning, fra en pose som inneholder hver utskriftstype nøyaktig en gang. Vi betegner settet med trykte tegn, n kardinalen i La en sekvens a = a 1 a 2 a 3 ... a r tegn, for eksempel et ord, som Wikipedia ( r = 9 i dette spesielle tilfellet). Kartet N , som til en tekst ω assosierer antallet N ( ω ) forekomster av sekvensen a i teksten ω kan sees på som en sum av Bernoulli-variabler: faktisk,
PÅ {\ displaystyle \ scriptstyle \ {\ mathcal {A}} \} PÅ. {\ displaystyle \ scriptstyle \ {\ mathcal {A}}. \} PÅ, {\ displaystyle \ scriptstyle \ {\ mathcal {A}}, \}
IKKE=∑k=1m-r+1Xk,{\ displaystyle N = \ sum _ {k = 1} ^ {m-r + 1} X_ {k},}
hvor X 1 , X 2 ,…, X m - r +1 er definert av
Xk=11ωkωk+1ωk+2...ωk+r-1=på,{\ displaystyle X_ {k} \, = \, 1 \! \! 1 _ {\ omega _ {k} \ omega _ {k + 1} \ omega _ {k + 2} \ dots \ omega _ {k + r -1} = a},}
dvs. X k er lik 1 eller 0, avhengig av om sekvensen a vises i teksten ω , like etter ( k - 1) -te tegnet i denne teksten ω , eller ikke. Å være en hendelsesindikatorfunksjon, er X k derfor en Bernoulli-variabel. Parameteren er
P(ωkωk+1ωk+2...ωk+r-1=på) = 1ikker.{\ displaystyle \ mathbb {P} (\ omega _ {k} \ omega _ {k + 1} \ omega _ {k + 2} \ prikker \ omega _ {k + r-1} = a) \ = \ { \ frac {1} {n ^ {r}}}.}
Så
E[IKKE]=∑1≤k≤m-r+1 P(Xk=1) = m-r+1ikker.{\ displaystyle \ mathbb {E} [N] = \ sum _ {1 \ leq k \ leq m-r + 1} \ \ mathbb {P} (X_ {k} \, = \, 1) \ = \ {\ frac {mr + 1} {n ^ {r}}}.}
Intuisjonen er da at en tekst ω med en lengde på minst m = n r er nødvendig for at hendelsen (med andre ord hendelsen “ordet a vises minst en gang i teksten ω ”) blir sannsynlig. Faktisk Markov ulikhet innebærer at
{IKKE≥1} {\ displaystyle \ scriptstyle \ \ {N \ geq 1 \} \}
P(IKKE≥1)≤E[IKKE].{\ displaystyle \ mathbb {P} (N \ geq 1) \ leq \ mathbb {E} [N].}
Den typing ape paradoks , populært med Émile Borel , utnytter egenskapene til N når lengden r av tegnrekken en er meget stor. I eksemplet gitt av Émile Borel er sekvensen a en klassisk tekst i fransk litteratur, for eksempel hele teksten til La Comédie humaine . Den samme tilnærmingen fører til at den samme Émile Borel demonstrerer det normale tallsetningen .
Den statistiske analysen av sekvenser av tegn tegnet tilfeldig uavhengig , eller tegnet tilfeldig i henhold til mer sofistikerte modeller, har mange anvendelser, for eksempel analysen av ytelsen til forskjellige datakomprimeringsmetoder , eller studiet av genomet , og er i opprinnelsen til formaliseringen, av Andreï Markov , av forestillingen om Markov-kjeden .
Antall poster og antall sykluser av permutasjoner
Definisjon - I en sekvens u = ( u k ) 1 ≤k≤n , registreres det ned (resp. Opp ) for å rangere k hvis u k er strengt mindre (resp. Strengt større) enn hvert begrep u i slik at jeg < k , det vil si strengere mindre (resp. strengt større) enn hvert av begrepene som går foran det.
Eksempel. Postene ned fra suiten ω nedenfor er i fet skrift og understreket:
ω = (1. 3_,14,11_,15,7_,9,4_,5,12,3_,1_,6,10,8,2).{\ displaystyle \ \ omega \ {=} \ ({\ understreket {\ textbf {13}}}, 14, {\ understreket {\ textbf {11}}}, 15, {\ understreket {\ textbf {7}} }, 9, {\ understreket {\ textbf {4}}}, 5,12, {\ understreket {\ textbf {3}}}, {\ understreket {\ textbf {1}}}, 6,10,8, 2).}
La B ( k ) (resp. H ( k )) være hendelsen "det er en rekord nede (resp. Opp) på rang k ". Med andre ord, B ( k ) er det sett av permutasjoner w av for hvilket sekvensen ( ω (1), ω (2), ω (3), ..., co ( n )) oppviser en nedadrettet plate ved rad k . Dermed blir tallet N b ( ω ) (resp. N h ( ω )) for poster ned (resp. Opp) av permutasjonen ω skrevet som en sum av Bernoulli-variabler:
Sikke {\ displaystyle \ scriptstyle \ {\ mathfrak {S}} _ {n} \}
IKKEb(ω)=∑1≤k≤ikke 11B(k)(ω)ogIKKEb(ω)=∑1≤k≤ikke 11H(k)(ω).{\ displaystyle N_ {b} (\ omega) = \ sum _ {1 \ leq k \ leq n} \ 1 \! \! 1_ {B (k)} (\ omega) \ quad {\ text {and}} \ quad N_ {b} (\ omega) = \ sum _ {1 \ leq k \ leq n} \ 1 \! \! 1_ {H (k)} (\ omega).}
I kraft av de statistiske egenskapene til Lehmer-koden har disse Bernoulli-variablene de respektive parametrene 1 / k :
P(B(k))=P(H(k))=1k.{\ displaystyle \ mathbb {P} (B (k)) = \ mathbb {P} (H (k)) = {\ tfrac {1} {k}}.}
Så
E[IKKEb]=E[IKKEh]=∑k=1ikke1k=Hikke≃lnikke,{\ displaystyle \ mathbb {E} [N_ {b}] = \ mathbb {E} [N_ {h}] = \ sum _ {k = 1} ^ {n} {\ frac {1} {k}} = H_ {n} \ simeq \ ln n,}
hvor H n betegner den n- te harmoniske nummer . Siden berørte Bernoulli-variabler fremdeles i kraft av de statistiske egenskapene til Lehmer-koden er uavhengige, har vi også
Var(IKKEb)=Var(IKKEh)=∑1≤k≤ikke Var(11B(k))=Hikke-Hikke(2)≃lnikke,{\ displaystyle {\ text {Var}} (N_ {b}) = {\ text {Var}} (N_ {h}) = \ sum _ {1 \ leq k \ leq n} \ {\ text {Var} } \ left (1 \! \! 1_ {B (k)} \ right) = H_ {n} -H_ {n} ^ {(2)} \ simeq \ ln n,}
hvor H n (2) er det harmoniske tallet definert av
Hikke(2)=∑k=1ikke1k2,{\ displaystyle H_ {n} ^ {(2)} = \ sum _ {k = 1} ^ {n} {\ frac {1} {k ^ {2}}},}
og konvergerer til £ (2) , det vil si for å væreTI 2 / til 6 .
Den grunnleggende korrespondansen til Foata gjør det mulig å vise at følgende to applikasjoner:
- antallet N b ( ω ) av postene for en permutasjon ω tegnet tilfeldig,
- antall C ( ω ) av sykluser for spaltning av en permutasjon ω trukket tilfeldig,
er to tilfeldige variabler med samme lov om sannsynlighet. Denne loven om sannsynlighet uttrykkes i form av Stirling-tall av første art , bemerket :
[ikkek] {\ displaystyle \ left [{\ begin {matrix} \ scriptstyle n \\\ scriptstyle k \ end {matrix}} \ right] \}
P(IKKEb=k)=1ikke! [ikkek],P(x≤IKKEb≤y)=∑k=xy1ikke! [ikkek],{\ displaystyle {\ begin {array} {rcl} \ mathbb {P} \ left (N_ {b} = k \ right) & = & {\ tfrac {1} {n!}} \ \ left [{\ begin {matrix} n \\ k \ end {matrix}} \ right], \\\ mathbb {P} \ left (x \ leq N_ {b} \ leq y \ right) & = & \ sum _ {k = x } ^ {y} {\ tfrac {1} {n!}} \ \ left [{\ begin {matrix} n \\ k \ end {matrix}} \ right], \ end {array}}}
som gir en eksakt formel, men ikke veldig eksplisitt, for en eksakt formel som det da er vanskelig å utlede en effektiv beregning av den aktuelle sannsynligheten for.
P(|IKKEb-ln(ikke)|≤påln(ikke)), {\ displaystyle \ scriptstyle \ \ mathbb {P} \ left (\ left | N_ {b} - \ ln (n) \ right | \ leq a {\ sqrt {\ ln (n)}} \ right), \}
På den annen side, skriving N b som en sum av Bernoulli-variabler tillater den sentrale grensesetningen som skal anvendes på N b . Dermed ser vi at antall sykluser av en permutasjon trukket tilfeldig, i likhet med antall poster, er veldig konsentrert rundt deres forventning, som er omtrent lik ln n . Mer presist :
limikkeP(|IKKEb-ln(ikke)|≤påln(ikke))=∫-påpå12πe-x2/2dx=0,999{\ displaystyle {\ begin {array} {rcl} \ lim _ {n} \, \ mathbb {P} \ left (\ left | N_ {b} - \ ln (n) \ right | \ leq a {\ sqrt {\ ln (n)}} \ right) & = & \ int _ {- a} ^ {a} \, {\ tfrac {1} {\ sqrt {2 \ pi}}} \, e ^ {- x ^ {2} / 2} \, {\ rm {d}} x \\ & = & 0 {,} 999 \ end {array}}}
for a = 3,3.
Gjennomsnittlig kostnad for hurtig sorteringsalgoritmen
Den raske sorteringsalgoritmen , også kalt Quicksort, er en av de mest brukte algoritmene for å sortere , i stigende rekkefølge, en uordnet liste x = ( x 1 , x 2 , x 3 ,…, x n ) av n elementer, ved hjelp av en liten antall to til to sammenligninger. Quicksort er kjent for å være både enkel og effektiv. Quicksort fungerer som følger:
- vi sammenligner x 1 med hvert av elementene i listen ( x 2 , x 3 , ..., x n ), som gjør det mulig å utgjøre 2 underlister, listen over ω 1 - 1 mindre elementer (resp. av n - ω 1 elementer større) enn x 1 . Dette gir rangeringen ω 1 som x 1 vil oppta i listen når den er ryddig.
- vi sammenligner x 2 med hvert av elementene i underlisten, noe som gjør det mulig å finne rangeringen av x 2 i denne underlisten, og til slutt rangeringen ω 2 som x 2 vil okkupere i den komplette listen når denne er ryddig. I tillegg deler dette en av de to sublistene som ble laget i forrige trinn i to, og utgjorde dermed 3 sublister, hvorav noen muligens kan være tomme (hvis x 1 eller x 2 er ekstreme elementer i deres (underlister).) oppføring).
- vi sammenligner x 3 , etc.
En konkret implementering av denne abstrakte algoritmen er beskrevet av Donald Knuth i The Art of Computer Programming .
Ytelsen til Quicksort er i verste fall (i verste fall som tilsvarer en allerede godt ordnet liste, i stigende eller synkende rekkefølge) i størrelsesorden n 2 to til to sammenligninger. Av denne grunn vil en liste som består av sammenkoblinger av velordnede lister (en hyppig konfigurasjon i praksis) være kostbar å organisere, når det gjelder antall sammenligninger. Det ofte adopterte middelet for å overvinne denne svakheten Quicksort kunstner opp listen over før prosessen: det er ω = ( ω (1), ω (2), ω (3), ..., ω ( n )) rangerer respektive elementer ( x 1 , x 2 , x 3 ,…, x n ) til den tidligere uordnede listen når disse elementene er ordnet i en økende liste ( y 1 < y 2 < y 3 <... < y n ), slik at x i = y ω ( i ) . Vi antar derfor at listen er ferdigbehandlet slik at ω er en permutasjon tegnet tilfeldig med ekviprobabilitet blant n ! permutasjoner mulig. Vi betegner med N ( ω ) antall sammenligninger gjort av algoritmen. Så
IKKE(ω)=∑1≤Jeg<j≤ikke 11PÅ(Jeg,j)(ω),{\ displaystyle N (\ omega) = \ sum _ {1 \ leq i <j \ leq n} \ 1 \! \! 1_ {A (i, j)} (\ omega),}
der A (i, j) er hendelsen " y i og y j sammenlignes en gang i løpet av algoritmen". Dette resulterer i en elementær analyse av den gjennomsnittlige kostnaden for Quicksort, enklere enn den klassiske metoden ved hjelp av en gjentakelsesformel og en beregning av generatorfunksjonen .
Forslag - Vi har
P(PÅ(Jeg,j)) = 2j-Jeg+1,{\ displaystyle \ mathbb {P} \ left (A (i, j) \ right) \ = \ {\ frac {2} {j-i + 1}},}
og
E[IKKE] = 2(ikke+1)Hikke-4ikke ≃ 2ikkeln(ikke).{\ displaystyle \ mathbb {E} [N] \ = \ 2 (n + 1) \, H_ {n} \, - \, 4n \ \ simeq \ 2n \, \ ln (n).}
Demonstrasjon
Det er to muligheter:
- hvis begrepet, si z , fra listen L = ( y i < y i +1 <… < y j –1 < y j ) som vises først i listen ( x 1 , x 2 , x 3 ,…, x n ) er strengt mellom y i og y j , så rett før vi begynner å sammenligne z med elementene i underlisten, inneholder denne underlisten listen L , og ingen av elementene i L n 'ble igjen sammenlignet med et annet element i L (siden z er den første ). Etter at vi har sammenlignet z med alle de andre elementene i L , plasseres y i og y j i to forskjellige underlister (siden y i <z <y j ) og vil aldri bli sammenlignet igjen:
11PÅ(Jeg,j)(ω)=0.{\ displaystyle 1 \! \! 1_ {A (i, j)} (\ omega) = 0.}
- hvis z er ett av de to elementene y i og y j i listen L , når vi sammenligner z med alle de andre elementene i underlisten, som helt inneholder listen L , vil z spesielt bli sammenlignet med den andre element av paret (y i , y j ) :
11PÅ(Jeg,j)(ω)=1 .{\ displaystyle 1 \! \! 1_ {A (i, j)} (\ omega) = 1 \.}
Fordelingen av j - i + 1-elementer fra liste L i liste x er enhetlig tilfeldig , så sannsynligheten for at et bestemt element z fra liste L vises først i liste x er 1 / ( j - i + 1). Så
P(PÅ(Jeg,j))=P(le 1er e´le´meikket de lpå lJegste L dpåikkes lpå lJegste x est soJegt yJeg, er yj)=2j-Jeg+1,{\ displaystyle {\ begin {array} {rl} \ mathbb {P} \ left (A (i, j) \ right) = & \ mathbb {P} \ left (\ mathrm {the ~ 1st ~ {\ acute { e}} l {\ acute {e}} ment ~ of ~ the ~ list} \ L \ \ mathrm {in ~ the ~ list} \ x \ \ mathrm {is ~ either} \ y_ {i}, \ {\ tekst {enten}} \ y_ {j} \ right) \\ = & {\ frac {2} {ji + 1}}, \ end {array}}}
og
E[IKKE]=∑1≤Jeg<j≤ikke P(PÅ(Jeg,j))=∑1≤Jeg<j≤ikke 2j-Jeg+1=2∑1≤Jeg≤ikke-1 (∑Jeg+1≤j≤ikke1j-Jeg+1)=2∑1≤Jeg≤ikke-1 (∑2≤ℓ≤ikke-Jeg+11ℓ)=2∑2≤m≤ikke (∑2≤ℓ≤m1ℓ)=2∑2≤ℓ≤ikke 1ℓ(∑ℓ≤m≤ikke1)=2 ∑2≤ℓ≤ikke ikke+1-ℓℓ=2(ikke+1) ∑2≤ℓ≤ikke 1ℓ- 2 ∑2≤ℓ≤ikke ℓℓ=2((ikke+1)(Hikke-1)-(ikke-1))=2(ikke+1)Hikke-4ikke≃2ikkeln(ikke).{\ displaystyle {\ begin {array} {rl} \ mathbb {E} [N] & = \ sum _ {1 \ leq i <j \ leq n} \ \ mathbb {P} \ left (A (i, j ) \ høyre) \\ & = \ sum _ {1 \ leq i <j \ leq n} \ {\ frac {2} {ji + 1}} \\ & = 2 \ sum _ {1 \ leq i \ leq n-1} \ \ left (\ sum _ {i + 1 \ leq j \ leq n} {\ frac {1} {ji + 1}} \ right) \\ & = 2 \ sum _ {1 \ leq i \ leq n-1} \ \ left (\ sum _ {2 \ leq \ ell \ leq ni + 1} {\ frac {1} {\ ell}} \ right) \\ & = 2 \ sum _ {2 \ leq m \ leq n} \ \ left (\ sum _ {2 \ leq \ ell \ leq m} {\ frac {1} {\ ell}} \ right) \\ & = 2 \ sum _ {2 \ leq \ ell \ leq n} \ {\ frac {1} {\ ell}} \ left (\ sum _ {\ ell \ leq m \ leq n} \, 1 \ right) \\ & = 2 \ \ sum _ {2 \ leq \ ell \ leq n} \ {\ frac {n + 1- \ ell} {\ ell}} \\ & = 2 (n + 1) \ \ sum _ {2 \ leq \ ell \ leq n} \ {\ frac {1} {\ ell}} - \ 2 \ \ sum _ {2 \ leq \ ell \ leq n} \ {\ frac {\ ell} {\ ell}} \\ & = 2 \ left (( n + 1) (H_ {n} -1) - (n-1) \ høyre) \\ & = 2 (n + 1) \, H_ {n} \, - \, 4n \ \ & \ simeq 2n \ , \ ln (n). \ end {array}}}
hvor H n betegner den n- te harmoniske nummer . Den 4 th lik kommer fra den endring av de variable de fem e tilsvare kommer fra den endring av de variable og 6 e likhet følger en reversering av rekkefølgen av summeringen mellom variablene m og ℓ=j-Jeg+1,{\ displaystyle \ scriptstyle \ \ ell = j-i + 1,} m=ikke-Jeg+1,{\ displaystyle \ scriptstyle \ m = n-i + 1,} ℓ.{\ displaystyle \ scriptstyle \ \ ell.}
Dermed gjør randomiseringen av listen som er gitt som inngang det mulig å redusere kostnaden for algoritmen, fra n 2 til 2 n ln ( n ). Videre analyse viser at N er veldig konsentrert rundt gjennomsnittet 2n ln ( n ). Mer spesifikt, variansen av N er asymptotisk (7 - (2π 2 /3)) n 2 , fra hvilken det følger at standardavviket til N er av størrelsesorden n , det vil si neglisjerbar forventet N . Merk at kostnaden (gjennomsnittlig kostnad eller kostnad i verste fall) for en hvilken som helst sorteringsalgoritme som bruker 2 til 2 sammenligninger, reduseres med ln ( n !) / Ln (2), som ifølge formelen til Stirling er omtrent 1,4 n ln ( n ).
Merknader og referanser
-
(in) L. Le Cam , " An Approximation Theorem for the Binomial Distribution Poisson " , Pacific Journal of Mathematics , vol. 10, n o 4,1960, s. 1181-1197 ( les online , konsultert 13. mai 2009 )
-
(in) AD Barbour , L. Holst og S. Janson , Poisson-tilnærming , Oxford, Clarendon Press, Oxford University Press, koll. "Oxford Studies in Probability",1992, 277 s. ( ISBN 0-19-852235-5 ).
-
(i) Stephen M. Stigler , Historien om statistikk: Måling av usikkerhet før 1900 , Harvard Belknap Press fra Harvard University Press,1 st mars 1990, 1 st ed. , 432 s. ( ISBN 978-0-674-40341-3 , leses online ) , kap. 2 (“Probabilists and måling av usikkerhet”) , s. 65-70.
-
se (i) Galen R. Shorack og Jon A. Wellner , Empiriske prosesser med applikasjoner til statistikk , Society for Industrial & Applied Mathematics,4. september 2009, 998 s. ( ISBN 978-0-89871-684-9 , les online ), eller til og med Glivenko-Cantelli-teoremet .
-
(en) Rajeev Motwani og Prabhakar Raghavan , Randomized Algorithms , Cambridge; New York, Cambridge University Press ( repr. 1997, 2000) ( 1 st ed. 1995), 476 s. ( ISBN 9780521474658 ) , kap. 4 (“Tail inequalities”) , s. 94-95, Teorem 4.18.
-
foreslo (in) Kyu-Young Whang og Ravi Krishnamurthy , " Query optimization in a memory-resident relational domain calculus database system " , ACM Transactions on Database Systems (TODS) , New York, NY, USA, ACM, vol. 15, n o 1,Mars 1990, s. 67-95 ( ISSN 0362-5915 , les online ).
-
Se Émile Borel, “ Statistical Mechanics and Irreversibility ”, J. Phys. 5 th serie , vol. 3,1913, s. 189-196.
-
(i) Donald E. Knuth , The Art of Computer Programming , Vol. 3: Sortering og søk ,1998, 2 nd ed. [ detalj av utgaven ], s. 13 .
-
Knuth 1998 , kap. 5.2.2 (“Sortering etter bytte”).
-
(i) Michael Mitzenmacher og Eli Upfal , Sannsynlighet og Computing: randomisert Algoritmer og Probabilistic analyse , Cambridge, Cambridge University Press ,April 2005, 1 st ed. , 368 s. ( ISBN 978-0-521-83540-4 , leses online ) , kap. 2 (“Diskrete tilfeldige variabler og forventning, avsnitt 2.5”) , s. 34-37.
Se også
Relaterte artikler