En Teoria de la probabilitat i Estadística, la distribució uniforme discreta és una distribució de probabilitat sobre un conjunt finit que assigna la mateixa probabilitat a cadascun dels elements del conjunt. Correspon a la definició de Laplace de probabilitat en un experiment aleatori equiprobable (igual probabilitat) i és un model matemàtic de l'expressió "escollir a l'atzar".
Un exemple senzill és el resultat del llançament d'un dau. Els valors possibles són 1, 2, 3, 4, 5, 6, i cada vegada que es llança el dau la probabilitat d'una puntuació determinada és 1/6. Si es llancen dos daus i es sumen els seus valors, la distribució resultant ja no és uniforme perquè no totes les sumes tenen la mateixa probabilitat.
En aquest article ens centrarem en la distribució uniforme discreta sobre un conjunt finit de nombres reals, però també es consideren distribucions uniformes discretes sobre altres tipus de conjunts. Per exemple, una permutació aleatòria és una permutació generada de manera uniforme a partir de les permutacions d'una longitud determinada, i un arbre allargant uniforme és un arbre d'expansió generat uniformement entre els arbres d'expansió d'un gràfic donat.[1][2]
Es diu que una variable aleatòria X {\displaystyle X} té una distribució uniforme discreta o distribució rectangular discreta [3][4] sobre el conjunt { x 1 , … , x n } ⊂ R {\displaystyle \{x_{1},\dots ,x_{n}\}\subset \mathbb {R} } si P ( X = x 1 ) = ⋯ = P ( X = x n ) = 1 n . {\displaystyle P(X=x_{1})=\cdots =P(X=x_{n})={\frac {1}{n}}.} Escriurem X ∼ U ( { x 1 , … , x n } ) . {\displaystyle X\sim {\mathcal {U}}(\{x_{1},\dots ,x_{n}\}).}
L'esperança de X {\displaystyle X} és E ( X ) = 1 n ∑ j = 1 n x j . {\displaystyle E(X)={\frac {1}{n}}\sum _{j=1}^{n}x_{j}.} En general, el moment d'ordre k {\displaystyle k} és E ( X k ) = 1 n ∑ j = 1 n x j k . {\displaystyle E(X^{k})={\frac {1}{n}}\sum _{j=1}^{n}x_{j}^{k}.} La variància és Var ( X ) = 1 n ∑ j = 1 n ( x j − E ( X ) ) 2 = 1 n ∑ j = 1 n x j 2 − ( 1 n ∑ j = 1 n x j ) 2 . {\displaystyle {\text{Var}}(X)={\frac {1}{n}}\sum _{j=1}^{n}{\big (}x_{j}-E(X))^{2}={\frac {1}{n}}\sum _{j=1}^{n}x_{j}^{2}-{\Big (}{\frac {1}{n}}\sum _{j=1}^{n}x_{j}{\Big )}^{2}.} La funció generatriu de moments és M X ( t ) = 1 n ∑ j = 1 n e t x j , t ∈ R . {\displaystyle M_{X}(t)={\frac {1}{n}}\sum _{j=1}^{n}e^{tx_{j}},\ t\in \mathbb {R} .} La funció característica és φ X ( t ) = 1 n ∑ j = 1 n e i t x j , t ∈ R . {\displaystyle \varphi _{X}(t)={\frac {1}{n}}\sum _{j=1}^{n}e^{itx_{j}},\ t\in \mathbb {R} .}
Començarem estudiant la distribució sobre el conjunt { 1 , 2 , … , n } {\displaystyle \{1,2,\dots ,n\}} i després veurem el cas general.
Sigui X ∼ U ( { 1 , … , n } ) {\displaystyle X\sim {\mathcal {U}}(\{1,\dots ,n\})} . La funció de distribució és F X ( x ) = { 0 , si x < 1 , 1 n , si x ∈ [ 1 , 2 ) , ⋮ n − 1 n , si x ∈ [ n − 1 , n ) , 1 , si x ≥ n . {\displaystyle F_{X}(x)={\begin{cases}0,&{\text{si}}\ x<1,\\{\frac {1}{n}},&{\text{si}}\ x\in [1,2),\\\ \vdots \\{\frac {n-1}{n}},&{\text{si}}\ x\in [n-1,n),\\1,&{\text{si}}\ x\geq n.\end{cases}}}
Es pot escriure de forma compacta F X ( x ) = { 0 , si x < 1 , ⌊ x ⌋ n , si x ∈ [ 1 , n ) , 1 , si x ≥ n , {\displaystyle F_{X}(x)={\begin{cases}0,&{\text{si}}\ x<1,\\\\{\dfrac {\lfloor x\rfloor }{n}},&{\text{si}}\ x\in [1,n),\\\\1,&{\text{si}}\ x\geq n,\end{cases}}} on ⌊ x ⌋ {\displaystyle \lfloor x\rfloor } és la part entera de x {\displaystyle x} .
Per la fórmula de la suma d'una progressió aritmètica, E ( X ) = n + 1 2 . {\displaystyle E(X)={\frac {n+1}{2}}.} Anàlogament, per la fórmula de la suma dels quadrats dels primers nombres naturals, E ( X 2 ) = ( n + 1 ) ( 2 n + 1 ) 6 . {\displaystyle E(X^{2})={\frac {(n+1)(2n+1)}{6}}.} Llavors, Var ( X ) = n 2 − 1 12 . {\displaystyle {\text{Var}}(X)={\frac {n^{2}-1}{12}}.} A partir de la fórmula de la suma d'una progressió geomètrica deduïm que la funció generatriu de probabilitats és G X ( s ) = E [ s X ] = 1 n ∑ j = 1 n s j = s − s n + 1 n ( 1 − s ) , s ∈ ( − 1 , 1 ) . {\displaystyle G_{X}(s)=E{\big [}s^{X}{\big ]}={\frac {1}{n}}\sum _{j=1}^{n}s^{j}={\frac {s-s^{n+1}}{n(1-s)}},\ s\in (-1,1).} D'aquí, la funció generatriu de moments és M X ( t ) = E ( e t X ) = G ( e t ) = e t − e t ( n + 1 ) ) n ( 1 − e t ) , t ∈ R . {\displaystyle M_{X}(t)=E{\big (}e^{tX}{\big )}=G(e^{t})={\frac {e^{t}-e^{t(n+1)})}{n(1-e^{t})}},\ t\in \mathbb {R} .} La funció característica val φ X ( t ) = E ( e i t X ) = G ( e i t ) = e i t − e i t ( n + 1 ) ) n ( 1 − e i t ) , t ∈ R . {\displaystyle \varphi _{X}(t)=E{\big (}e^{itX}{\big )}=G(e^{it})={\frac {e^{it}-e^{it(n+1)})}{n(1-e^{it})}},\ t\in \mathbb {R} .} Aquesta distribució és una distribució simètrica.
Considerem dos nombres enters a , b ∈ Z {\displaystyle a,b\in \mathbb {Z} } , a < b {\displaystyle a<b} i sigui Y ∼ U ( { a , a + 1 , … , b } ) {\displaystyle Y\sim {\mathcal {U}}(\{a,a+1,\dots ,b\})} .[5] Sigui n = b − a + 1 {\displaystyle n=b-a+1} el nombre d'elements del conjunt { a , a + 1 , … , b } {\displaystyle \{a,a+1,\dots ,b\}} . Llavors,
F Y ( x ) = { 0 , si x < a , ⌊ x ⌋ − a + 1 b − a + 1 , si x ∈ [ a , b ) , 1 , si x ≥ b . {\displaystyle F_{Y}(x)={\begin{cases}0,&{\text{si}}\ x<a,\\\\{\dfrac {\lfloor x\rfloor -a+1}{b-a+1}},&{\text{si}}\ x\in [a,b),\\\\1,&{\text{si}}\ x\geq b.\end{cases}}} L'esperança de Y {\displaystyle Y} és E [ Y ] = a + b 2 . {\displaystyle E[Y]={\frac {a+b}{2}}.} La variància és Var ( Y ) = n 2 − 1 12 = ( b − a ) ( b − a + 2 ) 12 . {\displaystyle {\text{Var}}(Y)={\frac {n^{2}-1}{12}}={\frac {(b-a)(b-a+2)}{12}}.} La funció generatriu de probabilitats és G Y ( s ) = s a − s b + 1 n ( 1 − s ) , s ∈ ( − 1 , 1 ) {\displaystyle G_{Y}(s)={\frac {s^{a}-s^{b+1}}{n(1-s)}},\ s\in (-1,1)} i la funció generatriu de moments M Y ( t ) = e t a − e t ( b + 1 ) n ( 1 − e t ) , t ∈ R . {\displaystyle M_{Y}(t)={\frac {e^{ta}-e^{t(b+1)}}{n(1-e^{t})}},\ t\in \mathbb {R} .} Aquestes propietats poden demostrar-se directament o, alternativament, utilitzant que si X ∼ U ( { 1 , … , n } ) {\displaystyle X\sim {\mathcal {U}}(\{1,\dots ,n\})} aleshores Y = X + a − 1 ∼ U ( { a , a + 1 , … , b } ) . {\displaystyle Y=X+a-1\sim {\mathcal {U}}(\{a,a+1,\dots ,b\}).} Així, per exemple, la funció generatriu de probabilitats G Y {\displaystyle G_{Y}} es pot deduir G Y {\displaystyle G_{Y}} de la següent manera: G Y ( s ) = E [ s Y ] = E [ s X + a − 1 ] = s a − 1 E [ e X ] = s a − 1 G X ( s ) = s a − s b + 1 n ( 1 − s ) , s ∈ ( − 1 , 1 ) . {\displaystyle G_{Y}(s)=E[s^{Y}]=E[s^{X+a-1}]=s^{a-1}E[e^{X}]=s^{a-1}G_{X}(s)={\frac {s^{a}-s^{b+1}}{n(1-s)}},\ s\in (-1,1).} Aquesta distribució també és una distribució simètrica.
Johnson et al. [6] consideren la següent situació: fixem dos números r , s ∈ R {\displaystyle r,s\in \mathbb {R} } , r < s {\displaystyle r<s} , i i dividim el segment [ r , s ] {\displaystyle [r,s]} en n {\displaystyle n} parts iguals de longitud h = ( s − r ) / n {\displaystyle h=(s-r)/n} ; llavors consideren la distribució uniforme sobre el conjunt de punts equidistants { r , r + h , r + 2 h , … , r + ( n − 1 ) h , s } {\displaystyle \{r,r+h,r+2h,\dots ,r+(n-1)h,s\}} ; notem que aquest conjunt té n + 1 {\displaystyle n+1} punts.
Exemple.
Tal com s'ha comentat a la introducció, la suma dels resultats de dos daus no segueix una distribució uniforme. Concretament, si designem per X ∼ U ( { 1 , 2 , … , 6 } ) {\displaystyle X\sim {\mathcal {U}}(\{1,2,\dots ,6\})} el resultat del primer dau i per Y ∼ U ( { 1 , 2 , … , 6 } ) {\displaystyle Y\sim {\mathcal {U}}(\{1,2,\dots ,6\})} el resultat del segon dau, que òbviament són independents, i designem per S = X + Y {\displaystyle S=X+Y} la seva suma, veiem que P ( S = 2 ) = P ( X = 1 , Y = 1 ) = P ( X = 1 ) P ( Y = 2 ) = 1 36 {\displaystyle P(S=2)=P(X=1,\ Y=1)=P(X=1)\,P(Y=2)={\frac {1}{36}}} i P ( S = 3 ) = P ( X = 1 , Y = 2 ) + P ( X = 2 , Y = 1 ) = 2 36 . {\displaystyle P(S=3)=P(X=1,Y=2)+P(X=2,Y=1)={\frac {2}{36}}.} Anàlogament, es completa la taula
El problema de De Moivre. Siguin X 1 , … , X m {\displaystyle X_{1},\dots ,X_{m}} variables aleatòries independents, totes amb distribució uniforme discreta en el conjunt { 1 , 2 , … , k } {\displaystyle \{1,2,\dots ,k\}} . Volem estudiar la distribució de la suma S m = X 1 + ⋯ + X m . {\displaystyle S_{m}=X_{1}+\cdots +X_{m}.} Aquest problema va ser resolt amb tota generalitat per De Moivre [7] (Feller)[8] mitjançant funcions generatrius de probabilitat: per a ℓ = m , m + 1 , … , k m , {\displaystyle \ell =m,\,m+1,\dots ,km,} P { S m = ℓ } = 1 k m ∑ i = 0 ℓ ∗ ( − 1 ) i ( m i ) ( ℓ − k i − 1 m − 1 ) , {\displaystyle P\{S_{m}=\ell \}={\frac {1}{k^{m}}}\sum _{i=0}^{\ell ^{*}}(-1)^{i}{\binom {m}{i}}{\binom {\ell -ki-1}{m-1}},} on ℓ ∗ = ⌊ ℓ − m k ⌋ . {\displaystyle \ell ^{*}={\Big \lfloor }{\frac {\ell -m}{k}}{\Big \rfloor }.} També es demostra que per a ℓ = m , m + 1 , … , k m {\displaystyle \ell =m,m+1,\dots ,km} , P { S m ≤ ℓ } = 1 k m ∑ i = 0 ℓ ∗ ( − 1 ) i ( m i ) ( ℓ − k i m ) . {\displaystyle P\{S_{m}\leq \ell \}={\frac {1}{k^{m}}}\sum _{i=0}^{\ell ^{*}}(-1)^{i}{\binom {m}{i}}{\binom {\ell -ki}{m}}.} Vegeu Funció generatriu de probabilitat per a la demostració.
Un dels exemples que dóna De Moivre és el següent: tirem 6 daus ordinaris 6 vegades això és, m = k = 6 {\displaystyle m=k=6} . Llavors, la probabilitat d'obtenir una suma de 15 punts és P ( S 6 = 15 ) = 1 6 6 ∑ i = 0 1 ( − 1 ) i ( 6 i ) ( 15 − 6 i − 1 6 − 1 ) = 1 6 6 ( ( 14 5 ) − 6 ( 8 5 ) ) = 0 ′ 036. {\displaystyle P(S_{6}=15)={\frac {1}{6^{6}}}\sum _{i=0}^{1}(-1)^{i}{\binom {6}{i}}{\binom {15-6i-1}{6-1}}={\frac {1}{6^{6}}}{\Bigg (}{\binom {14}{5}}-6{\binom {8}{5}}{\Bigg )}=0'036.}
Un altre exemple.
Del resultat anterior es dedueix que la suma de distribucions uniformes independents amb el mateix suport no té distribució uniforme. En aquest exemple veurem que la suma de distribucions uniformes independents amb diferent suport pot donar una distribució uniforme.
Considerem dos daus de 10 cares cadascun, el primer numerat amb les desenes 00, 10, 20, ... 90 i l'altre amb les unitats 0,1,...,9. Llavors la suma dels resultats segueix una llei de l'uniforme discreta amb suport els números de 0 al 99 i equival a tirar un dau de 100 cares numerat del 0 al 99. Formalment, si X ∼ U ( { 0 , 10 , 20 , … , 90 } ) {\displaystyle X\sim {\mathcal {U}}(\{0,10,20,\dots ,90\})} és el resultat del dau en desenes i Y ∼ U ( { 0 , 1 , … , 9 } ) {\displaystyle Y\sim {\mathcal {U}}(\{0,1,\dots ,9\})} el resultat del dau en unitats, les funcions generatrius de probabilitat són G X ( s ) = 1 10 ( 1 + s 10 + ⋯ + s 90 ) = s 100 − 1 10 ( s 10 − 1 ) , {\displaystyle G_{X}(s)={\frac {1}{10}}{\big (}1+s^{10}+\cdots +s^{90}{\big )}={\frac {s^{100}-1}{10(s^{10}-1)}},} i G Y ( s ) = 1 10 ( 1 + s + ⋯ + s 9 ) = s 10 − 1 10 ( s − 1 ) . {\displaystyle G_{Y}(s)={\frac {1}{10}}{\big (}1+s+\cdots +s^{9}{\big )}={\frac {s^{10}-1}{10(s-1)}}.} Per la independència dels dos daus, G X + Y ( s ) = G X ( s ) G Y ( s ) = s 100 − 1 100 ( s − 1 ) . {\displaystyle G_{X+Y}(s)=G_{X}(s)G_{Y}(s)={\frac {s^{100}-1}{100(s-1)}}.} D'on resulta que X + Y ∼ U ( { 0 , 1 , , … , 99 } ) {\displaystyle X+Y\sim {\mathcal {U}}(\{0,1,,\dots ,99\})} .
La família de distribucions uniformes en un conjunt d'enters consecutius (amb un o ambdós límits desconeguts) té un estadístic suficient de dimensió finita, concretament, el triple del màxim de la mostra, el mínim de la mostra i la mida de la mostra. Però no és una família exponencial de distribucions, perquè el suport varia amb els paràmetres. Per a les famílies el suport de les quals no depèn dels paràmetres, el teorema de Pitman–Koopman–Darmois estableix que només les famílies exponencials tenen un estadístic suficient amb dimensió afitada quan augmenta la mida de la mostra. La distribució uniforme és, per tant, un exemple senzill que mostra la necessitat de les hipòtesis d'aquest teorema.
Aquesta secció es basa en.[9][10] Tenim una població numerada de l'1 al N {\displaystyle N} : per exemple, els taxis d'una ciutat que tenen un número de registre o uns objectes produïts per una fàbrica que tenen un número de sèrie. El número N {\displaystyle N} és desconegut i volem estimar-lo a partir de l'observació del número de registre de k {\displaystyle k} elements; específicament tenim k {\displaystyle k} observacions X 1 , … , X k {\displaystyle X_{1},\dots ,X_{k}} ; donat el context (vegeu més endavant el problema dels tancs alemanys) suposarem que fem el mostreig sense reposició: prenem un element amb distribució uniforme sobre { 1 , … , N } {\displaystyle \{1,\dots ,N\}} , anotem el número i el deixem fora, i llavors prenem un altre element, amb distribució uniforme entre els que queden, anotem el número i també el deixem fora, i així successivament. Cal tenir present que les variables aleatòries X 1 , … , X k {\displaystyle X_{1},\dots ,X_{k}} no són independents. Aquest problema es coneix com el problema dels tancs alemanys, o com el del número de taxis [11] (no confondre amb el número del taxi de Ramanujan) o Anàlisi de números seriats.
Intuïtivament, un estimador de N {\displaystyle N} és el número M {\displaystyle M} més gran que ha sortit: M = max { X 1 , … , X k } . {\displaystyle M={\text{max}}\{X_{1},\dots ,X_{k}\}.} De fet, M {\displaystyle M} és l'estimador del màxim de versemblança. Però és clar que aquest número sub-estima N {\displaystyle N} ; en altres paraules, M {\displaystyle M} té biaix. Per corregir el biaix, calculem la seva esperança: E [ M ] = k + 1 N + 1 N , {\displaystyle E[M]={\frac {k+1}{N+1}}\,N,} que és menor que N {\displaystyle N} ja que ( k + 1 ) / ( N + 1 ) < 1 {\displaystyle (k+1)/(N+1)<1} quan k < N {\displaystyle k<N} . Però l'estimador N ^ = k + 1 k M − 1 {\displaystyle {\widehat {N}}={\frac {k+1}{k}}M-1} és un estimador sense biaix de N {\displaystyle N} . A més, és un estadístic suficient i pel Teorema de Raó-Blackwell [12] N ^ {\displaystyle {\widehat {N}}} és l'estimador sense biaix de mínima variància. La variància de N ^ {\displaystyle {\widehat {N}}} és 1 k ( N − k ) ( N + 1 ) ( k + 2 ) ≈ N 2 k 2 per una mida mostral k ≪ N . {\displaystyle {\frac {1}{k}}\,{\frac {(N-k)(N+1)}{(k+2)}}\approx {\frac {N^{2}}{k^{2}}}{\text{per una mida mostral}}\ k\ll N.} Vegeu.[13][14][15][16]
Durant la Segona guerra mundial, el aliats volien estimar el número de tancs que fabricaven els alemanys.[17] Segons les estimacions dels serveis d'intel·ligència, els alemanys estaven produint entorn de 1.400 tancs per mes entre juny de 1940 i setembre de 1942, però els serveis d'estadística, a partir dels números de sèrie dels tancs alemanys capturats (tant aquells que encara estiguessin en estat de ser utilitzats com aquells parcialment destruïts) i aplicant fórmules similars a les anteriors, van estimar que la producció era 256 tancs al mes. Després de la guerra, les xifres de producció oficials, obtingudes de documents confiscats en el Ministeri de la guerra alemany, van mostrar que el nombre real era de 255.[18] Vegeu el video.[19]
Les dades concretes per a determinats mesos són :[17][20]
ContramesuresPer a confondre l'anàlisi dels números de sèrie, es poden excloure els números de sèrie o reduir la informació auxiliar utilitzable. Alternativament, es poden utilitzar números de sèrie que resisteixin una criptoanàlisi, triant, per exemple, números aleatòriament sense reemplaçament d'una llista que sigui molt major que el nombre d'objectes produïts; o produint números aleatoris i comprovant-los amb la llista de números ja assignats, però és probable que es produeixin empats tret que el nombre de dígits possibles sigui més del doble del nombre de dígits en el nombre d'objectes produïts (on el número de sèrie pot estar en qualsevol base); vegeu problema de l'aniversari. Per a això, es pot utilitzar un generador de números pseudoaleatoris criptogràficament segur. Tots aquests mètodes requereixen una taula de cerca (o trencar el xifrat) per a passar del número de sèrie a l'ordre de producció, la qual cosa complica l'ús dels números de sèrie: per exemple, no es pot recuperar un rang de números de sèrie, sinó que cal buscar cadascun per separat o generar una llista.
Alternativament, es poden encriptar els números de sèrie seqüencials mitjançant un xifrat per substitució simple, que permet una fàcil descodificació, però que també és fàcilment deduïble mitjançant anàlisi de freqüències: encara quan es comenci des d'un punt arbitrari, el text sense format té un patró (és a dir, els números es troben en seqüència). Hi ha un exemple d'això en la novel·la de Ken Follett Code to Zero, on l'encriptat dels números de sèrie del coet Jupiter-C són obtinguts com:
La paraula clau aquí és Huntsville (on s'ometen les lletres repetides) el que proveeix una clau de deu lletres.[21] Per tant, el coet número 13 era "HN", i el número del coet 24 era "UT".