Usuari:Freutci/generatriu

En Teoria de la probabilitat i Estadística, la distribució uniforme discreta és una distribució de probabilitat sobre un conjunt finit que dóna 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 en el context de les variables aleatòries, és a dir, on el conjunt de referència és 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.

Definició

Es diu que una variable aleatòria $X$ té una distribució uniforme discreta o distribució rectangular discreta sobre el conjunt $\{x_{1},\dots ,x_{n}\}\subset \mathbb {R}$ si $$P(X=x_{1})=\cdots =P(X=x_{n})={\frac {1}{n}}.$$Escriurem $X\sim {\mathcal {U}}(\{x_{1},\dots ,x_{n}\}).$

L'esperança de $X$ és$$E(X)={\frac {1}{n}}\sum _{j=1}^{n}x_{j}.$$En general, el moment d'ordre $k$ és$$E(X^{k})={\frac {1}{n}}\sum _{j=1}^{n}x_{j}^{k}.$$La variància és$${\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)={\frac {1}{n}}\sum _{j=1}^{n}e^{tx_{j}},\ t\in \mathbb {R} .$$La funció característica és$$\varphi _{X}(t)={\frac {1}{n}}\sum _{j=1}^{n}e^{itx_{j}},\ t\in \mathbb {R} .$$

Distribució uniforme sobre un conjunt de nombres enters consecutius

Distribució uniforme sobre el conjunt {1,2,...,n}

Començarem estudiant el cas $X\sim {\mathcal {U}}(\{1,\dots ,n\})$ i després veurem un cas més general. La funció de distribució és$$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)={\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 $\lfloor x\rfloor$ és la part entera de $x$.

Per la fórmula de la suma d'una progressió aritmètica, $$E(X)={\frac {n+1}{2}}.$$Anàlogament, per la fórmula de la suma dels quadrats dels primers nombres naturals, $$E(X^{2})={\frac {(n+1)(2n+1)}{6}}.$$Llavors, $${\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{\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{\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 $$\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.

Cas general

Considerem dos nombres enters $a,b\in \mathbb {Z}$, $a<b$ i sigui $Y\sim {\mathcal {U}}(\{a,a+1,\dots ,b\})$. Sigui $n=b-a+1$ el nombre d'elements del conjunt $\{a,a+1,\dots ,b\}$. Llavors,

$$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$ és $$E[Y]={\frac {a+b}{2}}.$$La variància és$${\text{Var}}(Y)={\frac {n^{2}-1}{12}}={\frac {(b-a)(b-a+2)}{12}}.$$La funció generatriu de probabilitats és $$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)={\frac {e^{ta}-e^{t(b+1)}}{n(1-e^{t})}},\ t\in \mathbb {R} .$$Aquestes propietats poden demostrar-se directament o bé utilitzant que si $X\sim {\mathcal {U}}(\{1,\dots ,n\})$ aleshores $$Y=X+a-1\sim {\mathcal {U}}(\{a,a+1,\dots ,b\}).$$Així, per exemple, la funció generatriu de probabilitats $G_{Y}$ es pot deduir $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)={\frac {s^{a}-s^{b+1}}{n(1-s)}},\ s\in (-1,1).$$Aquesta distribució també és una distribució simètrica.

Extensió: Distribució uniforme sobre un conjunt de punts equidistants

Johnson et al. consideren la següent situació: fixem dos números $r,s\in \mathbb {R}$ , $r<s$, i sigui $h=(s-r)/n$, i consideren la distribució uniforme sobre el conjunt $\{r,r+h,r+2h,\dots ,r+(n-1)h,s\}$; notem que aquest conjunt té $n+1$ punts.

Suma de variables uniformes discretes independents

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\sim {\mathcal {U}}(\{1,2,\dots ,6\})$ el resultat del primer dau i per $Y\sim {\mathcal {U}}(\{1,2,\dots ,6\})$ el resultat del segon dau, que òbviament són independents, i designem per $S=X+Y$ la seva suma, veiem que $$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)={\frac {2}{36}}.$$Anàlogament, es completa la taula

$j$	2	3	4	5	6	7	8	9	10	11	12
$P(S=j)$	${\frac {1}{36}}$	${\frac {1}{18}}$	${\frac {1}{12}}$	${\frac {1}{9}}$	${\frac {5}{36}}$	${\frac {1}{6}}$	${\frac {5}{36}}$	${\frac {1}{9}}$	${\frac {1}{12}}$	${\frac {1}{18}}$	${\frac {1}{36}}$

El problema de De Moivre. Siguin $X_{1},\dots ,X_{m}$ variables aleatòries independents, totes amb distribució uniforme discreta en el conjunt $\{1,2,\dots ,k\}$ . Volem estudiar la distribució de la suma $$S_{m}=X_{1}+\cdots +X_{m}.$$Aquest problema va ser resolt amb tota generalitat per De Moivre (Feller ) mitjançant funcions generatrius de probabilitat: per a $\ell =m,\,m+1,\dots ,km,$$$P\{S_{m}=\ell \}={\frac {1}{k^{m}}}\sum _{i=0}^{\ell ^{*}}(-1)^{i}{\binom {m}{i}}{\binom {\ell -ki-1}{m-1}},$$ on $$\ell ^{*}={\Big \lfloor }{\frac {\ell -m}{k}}{\Big \rfloor }.$$ També es demostra que per a $\ell =m,m+1,\dots ,km$,$$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$. Llavors, la probabilitat d'obtenir una suma de 15 punts és$$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\sim {\mathcal {U}}(\{0,10,20,\dots ,90\})$ és el resultat del dau en desenes i $Y\sim {\mathcal {U}}(\{0,1,\dots ,9\})$ el resultat del dau en unitats, les funcions generatrius de probabilitat són $$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)={\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)={\frac {s^{100}-1}{100(s-1)}}.$$D'on resulta que $X+Y\sim {\mathcal {U}}(\{0,1,,\dots ,99\})$.

Estimació dels paràmetres

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.

Estimació de la mida d'una població seriada

Aquesta secció es basa en . Tenim una població numerada de l'1 al $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$ és desconegut i volem estimar-lo a partir de l'observació del número de registre de $k$ elements; específicament tenim $k$ observacions $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,\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},\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 (no confondre amb el número del taxi de Ramanujan) o Anàlisi de números seriats.

L'estimador de $N$ que primer ve al cap és prendre el número $M$ més gran que ha sortit:$$M={\text{max}}\{X_{1},\dots ,X_{k}\}.$$De fet, $M$ és l'estimador del màxim de versemblança. Però és clar que aquest número sub-estima $N$; en altres paraules, $M$ té biaix. Per corregir el biaix, calculem la seva esperança: $$E[M]={\frac {k+1}{N+1}}\,N,$$que és clar que és menor que $N$ ja que $(k+1)/(N+1)<1$ quan $k<N$. Però l'estimador $${\widehat {N}}={\frac {k+1}{k}}M-1$$és un estimador sense biaix de $N$. A més, és un estadístic suficient i pel Teorema de Raó-Blackwell ${\widehat {N}}$és l'estimador sense biaix de mínima variància. La variància és $M$

$${\frac {1}{k}}\,{\frac {(N-k)(N+1)}{(k+2)}}\approx {\frac {N^{2}}{k^{2}}}{\text{per una mida mostral}}\ k\ll N.$$

Problema dels tancs alemany

Durant la Segona guerra mundial, el aliats volien estimar el número de tancs que fabricaven els alemanys . Segons les estimacions dels serveis d'inteligència, els alemanys estaven produint entorn de 1.400 tancs per mes entre juny de 1940 i setembre de 1942, però els serveis d'Estadistica, aplicant fórmules similars a les anteriors, utilitzant els números de sèrie dels tancs alemanys capturats (tant aquells que encara estiguessin en estat de ser utilitzats com aquells parcialment destruïts), el número resultant es va calcular en 256 al mes. Després de la guerra, les xifres de producció oficials, obtingudes de documents confiscats en el Ministeri de la Guerra d'Albert Speer, van mostrar que el nombre real va ser de 255.

Vegeu el video

on m és el major número de sèrie observat (màxim de la mostra) i k és el nombre de tancs observat (grandària de la mostra).

Dades específiques

S'han citat les següents estimacions per a alguns mesos específics:

Mes	Estimació estadística	Estimació d'intel·ligència	Registre alemany
Juny de 1940	169	1000	122
Juny de 1941	244	1550	271
Agost de 1942	327	1550	342

Contramesures

Per 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 la criptoanàlisi, de forma més efectiva triant 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; és probable que es produeixin col·lisions 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:

H	O	N	T	S	V	I	L	E	X
1	2	3	4	5	6	7	8	9	0

La paraula clau aquí és Huntsville (on s'ometen les lletres repetides) el que proveeix una clau de deu lletres. Per tant el coet número  13 era "HN", i el número del coet  24 era "UT".