GNU General Public License v3.0 licensed. Source available on github.com/zifeo/EPFL.
Fall 2015: Modèles Stochastiques
[TOC]
- résultat d'expérience :
$\zeta_i$ - événement :
$A={\zeta_1,\zeta_2,\ldots}$ - certain :
$\Omega ={\zeta_1,\ldots,\zeta_i}$ - impossible :
$\emptyset$
- certain :
-
probabilité de l'événement
$A$ :$P(A)$ $P(A)\ge 0$ $P(\Omega)=1$ $A_i\cap A_j=\emptyset\Rightarrow P(\cup_{i=1}^\infty A_i)=\sum_{i=0}^\infty P(A_i)$ -
$P(\bar A)=1-P(A)$ où$\bar A = \Omega\setminus A$ $P(A)\le 1$ $P(\emptyset)=0$ $P(A\cup B)=P(A)+P(B)-P(A\cap B)$ $A\subseteq B\Rightarrow P(A)\le P(B)$
-
probabilité conditionnelle :
$P(A|B)=\frac{P(A\cap B)}{P(B)}$ si$P(B)\not=0$ autrement$P(A|B)=0$ -
théorême des probabilités totales :
$P(B)=\sumzi P(B|A_i)P(A_i)$ pour$A_i\cap A_j=\emptyset$ et$A_1\cup\cdots\cup A_n=\Omega$ -
règles de Bayes :
$P(A_i|B)=\frac{P(B|A_i)P(A_i)}{\sumzj P(B|A_j)P(A_j)}$ pour$A_i\cap A_j=\emptyset$ et$A_1\cup\cdots\cup A_n=\Omega$ -
indépendance :
$P(A\cap B)=P(A)P(B)$ (pour plus de$2$ événements, l'indépendance doit être mutuelle) -
variable aléatoire : assigne à chaque résultat d'expérience
$\zeta$ un réel$X(\zeta)$ -
$A ={\zeta|X(\zeta)\le x}$ est un événement ${\zeta|X(\zeta)=\pm\infty}\Rightarrow P(X=\pm\infty)=0$
-
-
fonction de répartition :
$F_X(x)=P(X\le x)$ $0\le F_X(x)\le 1$ -
$\lim_{x\to -\infty}F_X(x)=0$ et$\lim_{x\to\infty} F_X(x)=1$ $a<b\Rightarrow F_X(a)\le F_X(b)$ $P(a<X\le b)=F_X(b)-F_X(a)$ - continue à droite
- support :
$S_X={X(\zeta)|\zeta\in\Omega}$ (si discret, peut être discontinue à gauche, si continu$P(X=x)=0$ )
-
densité de probabilité continue :
$f_X(x)=\frac{\d F_X(x)}{\dx}$ $f_X(x)\ge 0$ $\infint f_X(x)\dx=1$ $P(X\le a)=F_X(a)=\int_{-\infty}^a f_X(x)\dx$ $P(a<X\le b)=F_X(b)-F_X(a)=\int_a^b f_X(x)\dx$
-
densité de probabilité discrète :
$f_X(x)=\sum_ip_i\delta(x-x_i)$ $p_i\ge 0$ $\sum_i p_i=1$ $P(X\le a)=F_X(a)=\sum_{x_i \le a}p_i$ $P(X=x_i)=F_X(x_i)-F_X(x_i^-)=p_i$
-
fonction d'une variable aléatoire :
$Y=g(X)$ continue-
$m$ racines telles que$y=g(x_i)$ $f_Y(y)=\sum_i\frac{f_X(x_i)}{|g'(x_i)|}$
-
-
espérance :
$E[g(X)]=\infint g(x)f_X(x)\dx=\sum_i g(x)p_i$ uniquement si elle converge absolument- moment d'ordre
$n$ :$E[X^n]=\infint x^nf_X(n)\dx$ - moyenne :
$\mu_x=E[X]$ moment d'ordre$1$ - variance :
$\sigma^2=VAR[X]=E[(X-\mu_X)^2]=E[X^2]-\mu_X^2$ moment centré d'ordre$2$ - écart-type :
$\sigma$
- écart-type :
- moment d'ordre
-
fonction caractéristique :
$\Phi_X(\omega)=E[e^{j\omega X}]=\int_{-\infty}^\infty e^{j\omega x}f_X(x)\dx$ (transformée de Fourier)- maximale en
$\omega = 0$ - transformée inverse :
$f_X(x)=\frac{1}{2\pi}\infint e^{-j\omega x}\Phi_X(\omega)\d\omega$ $E[X^k]=\frac{1}{j^k}\frac{\d^k\Phi_X(\omega)}{\d\omega^k}\big |_{\omega=0}$
- maximale en
-
fonction généractice de moment :
$\hat\Phi_X(s)=E[e^{sX}]=\infint e^{sx}f_X(x)\dx$ (transformée de Laplace) -
fonction génératrice de cumulant :
$\Psi_X(\omega)=\ln\Phi_X(\omega)$ -
fonction génératrice de probabilité :
$G_X(z)=E[z^X]=\sumzk z^k P(X=k)=\sumzk z^k p_k$ (transformée en z)- transformée inverse :
$p_k=P(X=k)=\frac{1}{k!}\frac{\d^k G_X(z)}{\d z^k}\big |_{z=0}$ $G_X(1)=\sumzk p_k=1$ $E[X(X-1)\cdots(X-k+1)]=\frac{\d^k G_X(z)}{\d z^k}\big |_{z=1}$
- transformée inverse :
-
inégalité de Markov :
$P(X\ge a)\le E[X]/a$ -
inégalité de Tchébytcheff :
$P(|X-\mu_X|\ge b)\le \sigma_X^2/b^2$
-
fonction de répartition jointe :
$F_{XY}(x,y)=P(X\le x, Y\le y)$ - fonction de répartition marginale :
$F_X(x)=P(X\le x)=\lim_{y\to\infty}F_{XY}(x,y)$ et$F_Y(y)=P(Y\le y)=\lim_{x\to\infty}F_{XY}(x,y)$ $0\le F_{XY}(x,y)\le 1$ -
$\lim_{x\to -\infty}F_{XY}(x,y)=\lim_{y\to -\infty}F_{XY}(x,y)=0$ et$\lim_{x\to\infty,y\to\infty}F_{XY}(x,y)=1$
- fonction de répartition marginale :
-
densité de probabilité jointe continue :
$f_{XY}(x,y)=\frac{\partial^2F_{XY}(x,y)}{\partial x\partial y}$ - densité de probabilité marginale continue :
$f_X(x)=\frac{\d F_X(x)}{\dx}=\infint f_{XY}(x,\zeta)\d\zeta$ et$f_Y(y)=\frac{\d F_Y(y)}{\dy}=\infint f_{XY}(\zeta,y)\d\zeta$ $\infint\infint f_{XY}(x,y)\dx\d y=1$ $P(X\le a, Y\le b)=F_{XY}(x,y)=\int_{-\infty}^a\int_{-\infty}^b f_{XY}(x,y)\dx\dy$ $P(a_1<X\le a2, b_1< Y\le b_2)=F_{XY}(a_2,b_2)-F_{XY}(a_1,b_2)-F_{XY}(a_2,b_1)+F_{XY}(a_1,b_1)$
- densité de probabilité marginale continue :
-
densité de probabilité jointe discrète :
$f_{XY}(x,y)=\sum_{i,j}p_{ij}\delta(x-x_i)\delta(y-y_i)$ - densité de probabilité marginale discète :
$f_X(x)=\sum_{i,j}p_{ij}\delta(x-x_i)$ et$f_Y(y)=\sum_{i,j}p_{ij}\delta(y-y_i)$
- densité de probabilité marginale discète :
-
independance :
$F_{XY}(x,y)=F_X(x)F_Y(y)$ d'où$f_{XY}(x,y)=f_X(x)f_Y(y)$ $X\indep Y\Rightarrow Z=g(X)\indep W=h(Y)$
-
fonctions de variables aléatoires :
$Z=g_1(X,Y)$ et$W=g_2(X,Y)$ -
$m$ racines telles que$z=g_1(x_i, y_i)$ et$w=g_2(x_1,y_1)$ - jacobien : $J(x,y)=\det\begin{bmatrix}\partial g_1(x,y)/\partial x & \partial g_2(x,y)/\partial x\\ \partial g_1(x,y)/\partial y & \partial g_2(x,y)/\partial y \end{bmatrix}$
$f_{ZW}(z,w)=\sum_i\frac{f_{XY}(x_i,y_i)}{|J(x_i,y_i|}$ - transformation linéaire :
$z=Ax+b$ alors$f_Z(z)=\frac{f_X(A^{-1}(z-b)}{|\det(A)|}$ - addition :
$Z=X+Y$ alors$f_Z=f_X*f_Y$ (produit de convolution)
-
-
espérance :
$E[g(X,Y)]=\infint\infint g(x,y)f_{XY}(x,y)\dx\dy=\sum_{i,j}g(x_i,y_j)p_{ij}$ - linéaire
$X\indep Y\Rightarrow E[XY]=E[X]E[Y]$ - moment joints :
$E[X^nY^m]$ - orthogonales :
$E[XY]=0$ - covariance :
$COV[X,Y]=E[(X-\mu_X)(Y-\mu_Y)]=E[XY]-\mu_X\mu_Y$ - décorrelées :
$COV[X,Y]=0$ (automatique si indépendant) $COV[X,X]=\sigma^2$ $|COV[X,Y]|\le\sigma_X\sigma_Y$ - coefficient de corrélation :
$\rho=\frac{COV[X,Y]}{\sigma_X\sigma_Y}$ avec$-1\le\rho\le 1$
- décorrelées :
-
fonction caractéristique jointe :
$\Phi_{XY}(\omega_1,\omega_2)=E[e^{j(\omega_1X+\omega_2Y)}]=\infint\infint e^{j(\omega_1 x+\omega_2 y)}f_{XY}(x,y)\dx\dy$ (transformée de Fourier)- transformée inverse :
$f_{XY}=\frac{1}{4\pi^2}\infint\infint e^{-j(\omega_1x+\omega_2y)}\Phi_{XY}(\omega_1,\omega_2)\d\omega_1\d\omega_2$ - fonction caractéristique marginales :
$\Phi_X(\omega)=\Phi_XY(\omega,0)$ et$\Phi_Y(\omega)=\Phi_{XY}(0,\omega)$ - moments joints :
$E[X^mY^n]=\frac{1}{j^{m+n}}\frac{\partial^{m+n}\Phi_{XY}(\omega_1,\omega_2)}{\partial\omega_1^m\partial\omega_2^n}\big |_{(\omega_1,\omega_2)=(0,0)}$ $X\indep Y\Rightarrow \Phi_{XY}(\omega_1,\omega_2)=\Phi_X(\omega_1)\Phi_Y(\omega_2)$ - addition :
$Z=X+Y$ alors$\Phi_Z(\omega)=\Phi_X(\omega)\Phi_Y(\omega)$
- transformée inverse :
-
fonction génératrice de moment :
$\hat\Phi_{XY}(s_1,s_2)=E[e^{s_1X+s_2Y}]=\infint\infint e^{s_1X+s_2Y}f_XY(x,y)\dx\dy$ -
fonction de répartition conditionnelle continue :
$F_{X|Y}(x|y)=\lim_{\Delta y\to 0}P(X\le x|y\le Y<y+\Delta y)=\frac{\int_{-\infty}^x f_{XY}(\zeta,y)\d\zeta}{f_Y(y)}$ -
densité de probabilité conditionnelle continue :
$f_{X|Y}(x|y_i)=\frac{f_{XY}(x,y_i)}{f_Y(y_i)}$ -
fonction de répartition conditionnelle discrète :
$F_{X|Y}(x|y_i)=P(X\le x|Y=y_i)=\frac{P(X\le x, Y=y_i)}{P(Y=y_i)}$ si$P(Y=y_i)\not= 0$ autrement$0$ -
densité de probabilité conditionnelle discrète :
$f_{X|Y}(x|y_i)=\frac{\d F_{X|Y}(x|y_i)}{\dx}$ -
espérance conditionnelle :
$E[X|y]=\infint x f_{X|Y}(x,y)\dx=\sum_i x_iP(X=x_i|Y=y_i)$ $E[E[X|Y]]=E[X]$
-
variables aléatoires complexes :
$Z=X+jY$ - variance : $\sigma_Z^2=E[|Z-\mu_Z|^2]=E[(Z^-\mu_Z^)(Z-\mu_Z)]=\sigma_X^2+\sigma_Y^2$
- covariance :
$COV[Z,W]=COV^*[Z,W]$
-
convergence presque sûre :
$P({\zeta|\lim_{n\to\infty} X_n(\zeta)=X(\zeta)})=P(X_n\to X)=1$ lorsque$n\to\infty$ (implication forte) -
converge en distribution :
$\lim_{n\to\infty}F_n(x)=F(x)$ (implication faible) -
théorème central limite : une suite
${X_n}$ indépendantes et identiquement distribuées de moyenne$\mu$ et variance$\sigma^2$ alors$Z_n=\sum_{i=1}^n\frac{X_i-\mu}{\sqrt{n}\sigma}\to Z\sim N(0,1)$ lorsque$n\to\infty$ -
converge en probabilité :
$\lim_{n\to\infty}P(|X-X_n|>\epsilon)=0;\forall\epsilon > 0$ (implication moyenne) -
loi faible des grands nombres :
$\bar X_n=\frac{1}{n}\sum_{i=1}^n X_i$ alors$\lim_{n\to\infty} P(|\bar X_n-\mu| > \epsilon)=0;\forall\epsilon >0$ -
convergence en moyenne quadratique :
$\lim_{n\to\infty}E[(X_n-X)^2]=0$ (implication forte, abbréviation limit in meansquare$l.i.m.;X_n=X$ )
- processus stochastique :
$X(t,\zeta)$ - processus echantillonné :
$X_1=X(t_1,\zeta),\ldots,X_n=X(t_n,\zeta)$ -
fonction de répartition :
$F_\XS(\xs;\ts)=P(X(t_1)\le x_1;\cdots;X(t_n)\le x_n)$ -
densité de probabilité du $n$ième ordre :
$f_\XS(\xs;\ts)=\frac{\partial^n F_\XS(\xs;\ts)}{\partial x_1\cdots\partial x_n}$ -
moyenne (moment d'ordre 1) :
$\mu_X(t)=E[X(t)]=\infint x f_{X(t)}(x;t)\dx$ -
fonction d'auto-corrélation (moment d'ordre 2) :
$R_X(t_1,t_2)=E[X(t_1)X(t_2)]=\infint\infint x_1x_2 f_{X(t_1)X(t_2)}(x_1,x_2;t_1,t_2)\dx_1\dx_2$ - puissance moyenne :
$R_X(t,t)=E[X^2(t)]$
- puissance moyenne :
-
fonction d'auto-covariance :
$C_X(t_1,t_2)=E[(X(t_1)-\mu_X(t_1))(X(t_2)-\mu_X(t))]=R_X(t_1,t_2)-\mu_X(t_1)\mu_X(t_2)$ - variance :
$C_X(t,t)=VAR[X(t)]$
- variance :
-
coefficient d'autocorrélation :
$\rho_X(t_1,t_2)=\frac{C_X(t_1,t_2)}{\sqrt{C_X(t_1,t_1)C_X(t_2,t_2)}}$ - cross-corrélation:
$R_{XY}(t_1,t_2)=E[X(t_1)Y(t_2)]=\infint\infint x_1y_2 f_{X(t_1)Y(t_2)}(x_1,y_2;t_1,t_2)\dx_1\dy_2$ - orthogonaux :
$R_{XY}(t_1,t_2)=0;\forall t_1,t_2$
- orthogonaux :
- cross-covariance :
$C_{XY}(t_1,t_2)=E[(X(t_1)-\mu_X(t_1))(Y(t_2)-\mu_Y(t))]=R_{XY}(t_1,t_2)-\mu_X(t_1)\mu_Y(t_2)$ - non corrélés :
$C_{XY}(t_1,t_2)=0;\forall t_1,t_2$
- non corrélés :
- théorème de Fubini : pour échanger sommes et intégrations, elles doivent être (absolument) intégrable, impose souvent une moyenne null et donc un centrage de la variable
-
stationnarité au sens strict (SSS) : montrer
$\Phi_{X(t_1)\cdots X(t_n)}(\omega_1,\ldots,\omega_n)=\Phi_{X(t_1+c)\cdots X(t_n+c)}(\omega_1,\ldots,\omega_n)$ (avec décalage dans changement de variable, via fonction caractéristique)- propriétés statisques sont indépendantes de l'origine des temps
- peut être vérifié par les fonctions caractéristiques
- fonction de répartition :
$F_{X(t)}(x,t)=F_{X(t)}(x)$ - implique WSS
-
stationnarité au sens large (WSS)
- second moment peut dépendre de la différence entre deux instants
- fonction d'auto-corrélation :
$R_X(t_1,t_2)=R_X(t_1-t_2)$ -
$R_X(\tau)=R_X(-\tau)$ si réel $|R_X(\tau)|\le R_X(0)=E[X^2(t)]$
-
-
stationnarité cyclique de période
$T$ :$X(t-D)$ est WSS avec$D$ indépendant et uniforme entre$0$ et$T$ - stationnairité conjointe : WSS pour deux processus
- fonction d'auto-corrélation :
$R_{XY}(t_1,t_2)=R_{XY}(t_1-t_2)$ -
$R_{XY}(\tau)=R_{XY}(-\tau)$ si réel $|R_{XY}(\tau)|\le \sqrt{R_X(0)R_Y(0)}$ $|R_{XY}(\tau)|\le (R_X(0)+R_Y(0))/2$
-
- fonction d'auto-corrélation :
-
ergodisme par rapport à sa moyenne
$\iff \lim_{T\to\infty}\frac{1}{T}\int_0^TC_X(\tau)(1-\frac{\tau}{T}),d\tau=0$ - moyenne d'ensemble :
$\mu_X$ - moyenne temporelle :
$<X(t)>_T=\frac{1}{T}\int^T_0 X(t)\dt$ - condition suffisante :
$\lim_{\tau\to\infty}C_X(\tau)=0$
- moyenne d'ensemble :
- ergodisme par rapport à sa variance
$E[<X^2(t)>_T-\mu_X^2]\to\sigma^2$ $VAR[<X^2(t)>_T-\mu_X^2]\to0$
- ergodisme par rapport à sa fonction d'auto-corrélation
$<X(t+\tau)X(t)>_T=\frac{1}{T}\int_0^T X(t+\tau)X(t)\dt$ $E[<X(t+\tau)X(t)>_T]\to R_X(\tau)$ $VAR[<X(t+\tau)X(t)>_T]\to0$
- ergodisme par rapport à sa fonction de répartition : moyennes temporelles convergent en moyenne quadratique vers les fonctions de répartition
-
densité spectrale de puissance :
$S_X(f)=\infint R_X(\tau)e^{-j2\pi f\tau}\dta$ (transformée de Fourier)- bien défini si fini (pas le cas des processus à dépendances à long terme)
- préférence pour processus centré
- si moyenne non nul :
$S_X(f)=\infint C_X(\tau)e^{-j2\pi f\tau}\dta+\mu_X^2\delta(f)$ - transformée inverse (Wiener-Kintchine) :
$R_X(\tau)=\infint S_X(f)e^{j2\pi f\tau},df$ - puissance moyenne :
$E[X^2(t)]=R_X(0)=\infint S_X(f),df$ - comme
$R_X(\tau)$ pair, tranformée réel et pair $S_X(f)\ge 0$ -
$h(f)=S_X(f)/R_X(0)$ est une densité de probabilité
- densité spectrale mutuelle de puissance :
$S_{XY}(f)=\infint R_{XY}(\tau)e^{-j2\pi f\tau}\dta$ (en général complexe) -
système linéaire et invariant dans le temps (LTI) :
$y(t)=H(x(t))$ - transmittance :
$H(f)=\infint h(t)e^{-j2\pi ft}\dt$ - moyenne
$E[Y(t)]=H(0)\mu_X$ -
$S_Y(f)=H(f)H^*(f)S_X(f)=|H(f)|^2S_X(f)$ pour$X$ WSS $S_{YX}(f)=H(f)S_X(f)$ $S_{XY}(f)=H^*(f)S_X(f)$
- transmittance :
-
differenciation :
$Y(t)=\frac{dX}{\dt}(t)$ - WSS non requis
$E[Y(t)]=\frac{\d}{\dt}E[X(t)]$ -
$R_Y(\tau)=E[Y(t_1)Y(t_2)]=-\frac{d^2}{\partial t_1\partial t_2}E[X(t_1)X(t_2)]$ car$H(f)=2\pi j f$
- processus complexe
$R_{XY}(t_1,t_2)=E[X(t_1)Y^*(t_2)]$ - $C_{XY}(t_1,t_2)=E[(X(t_1)-\mu_X(t_1))(Y^(t_2)-\mu_Y^(t_2))]=R_{XY}(t_1,t_2)-\mu_X(t_1)\mu_Y^*(t_2)$
- si moyenne constante $R_X(\tau)=R_X(t,t-\tau)=R_{X^}(t-\tau,t)=R_{X^}(-\tau)$
- matrice de corrélation : $\Phi_X=\begin{bmatrix}R_X(n_1,n_1) & \cdots & R_X(n_1,n_m)\\ \vdots & \ddots & \vdots \\ R_X(n_m,n_1) & \cdots & R_X(n_m,n_m)\end{bmatrix}$
- matrice de covoriance : $\Gamma_X=\begin{bmatrix}C_X(n_1,n_1) & \cdots & C_X(n_1,n_m)\\ \vdots & \ddots & \vdots \\ C_X(n_m,n_1) & \cdots & C_X(n_m,n_m)\end{bmatrix}$
-
ergodisme par rapport à sa moyenne
$\iff \lim_{m\to\infty}\frac{1}{2m+1}\sum_{k=-2m}^{2m}C_X(k)(1-\frac{|k|}{2m+1})=0$ - moyenne temporelle : $<X(t)>m=\frac{1}{2m+1}\sum{n=-m}^mX(n)$
- condition suffisante :
$\lim_{k\to\infty}C_X(k)=0$
- ergodisme par rapport à sa fonction d'auto-corrélation : $<X(n)X(n-k)>m=\frac{1}{2m+1}\int{n=-m}^m X(n)X(n-k)$
-
densité spectrale de puissance :
$S_X(f)=\infsum R_X(k)e^{-j2\pi f k}$ - périodique de période
$1$ - transformée inverse :
$R_X(k)=\int_{-1/2}^{1/2} S_X(f)e^{j2\pi fk}\d f$ - puissance moyenne :
$E[X^2(t)]=R_X(0)=\int_{-1/2}^{1/2} S_X(f)\d f$ - transformée en z :
$\hat{S}_X(z)=\infsum R_X(k)z^{-k}$ avec$S_X(f)=\hat S_X(e^{j2\pi f})$
- périodique de période
-
densité spectrale mutuelle de puissance :
$S_{XY}(f)=\infsum R_{XY}(k)e^{-j2\pi fk}$ -
système linéaire et invariant dans le temps en z
-
$\hat S_Y(z)=\hat H(z)\hat H(1/z)\hat S_X(z)$ où$\hat H(z)=\infsum h(k)z^{-k}$
-
-
processus de comptage :
$N(t)$ représente nombre d'événements arrivant dans intervalle de temps$[0,t]$ - temps continu et valeurs entières non négative
-
$N(0)=0$ (arbitraire) -
$t_1<t_2$ entraine$N(t_1)\le N(t_2)$ - nombre d'événements dans
$]t_1,t_2]$ :$N(t_2)-N(t_1)$ $N(t)=\max{n\in\N_0:S(n)\le t}$
-
séquence des temps d'arrivée :
$S(n)$ représente le temps où arrive le $n$ième élément$S(n)=\sum_{m=0}^{n-1}T(m)$ $S(n)=\inf{t\in\R^+:N(t)=n}$ -
$f_{S(n)}(s;n)=\frac{\lambda(\lambda s)^{n-1}}{(n-1)!}e^{-\lambda s}$ (Erlang)
-
séquence des temps entre arrivées :
$T(n)$ réprésente l'intervalle de temps séparant l'arrivé du $n$ième élément et du $n+1$ième$T(n)=S(n+1)-S(n)$ -
$f_{T(n)}(t;n)=\lambda e^{-\lambda t}$ (exponentiel)
-
processus de poisson d'intensité
$\lambda$ : processus de comptage satisfaisant- accroissements indépendants :
$P({N(t+T)-N(t)=n_0}\cap{N(t)=n_1})=P(N(t+T)-N(t)=n_0)P(N(t)=n_1)$ - accroissements stationnaires (homogène dans le temps) :
$P(N(t+T)-N(t)=n_0)=P(N(T)=n_0)$ - probabilité d'avoir plus d'un événement est négligeable dans un petit interval de temps
$P(N(\Delta t)=0)=1-\lambda\Delta t + o(\Delta t)$ $P(N(\Delta t)=1)=\lambda\Delta t + o(\Delta t)$ $P(N(\Delta t)\ge 2)=o(\Delta t)$
- peut être résumé à accroissement indépendants et nombre d'événements dans une intervalle de longueur
$T$ suit une loi de poisson :$P(N(t+T)-N(t)=n)=\frac{(\lambda T)^n}{n!}e^{-\lambda T}$ - équation de Kolmogorov :
$\frac{\d p_0}{\dt}(t)=-\lambda p_0(t)$ et$\frac{\d p_n}{\dt}(t)=-\lambda p_n(t)+\lambda p_{n-1}(t)$ (résoluble par fonction génératrice ou récurrence) - propriétés
- fonction génératice :
$G_N(z;t)=e^{\lambda t(z-1)}$ - moyenne :
$\mu_N(t)=\lambda t$ - variance :
$\sigma_N^2(t)=\lambda t$ - auto-corrélation :
$R_N(t_1,t_2)=\lambda^2t_1t_2+\lambda\min(t_1,t_2)$ - superposition de
$M$ processus est un processus de taux$\lambda=\sum_{i=1}^M\lambda_i$ - décomposition en
$M$ processus indépendant respecte la composition avec$p_i\lambda$ où$\sum p_i = 1$
- fonction génératice :
- accroissements indépendants :
-
bruit impulsif de poisson :
$X_h(t)=\infsum h(t-S(k))$ et$h$ absolument intégrable-
$h$ deterministe $\mu_{X_h}=\lambda H(0)=\lambda\infint h(s),ds$ $\sigma_{X_h}^2=\lambda\infint h^2(s),ds$
-
-
bruit impulsif de poisson composé :
$\hat{X}_h(t)=\infsum A_kh(t-S(k))$ où$A_k$ iid et$h$ absolument intégrable (théorème de Campbell)$\mu_{\hat{X}_h}=\lambda\mu_AH(0)=\lambda\mu_A\infint h(s),ds$ $\sigma_{\hat{X}_h}^2=\lambda(\mu_A^2+\sigma_A^2)\infint h^2(s),ds$
- markovien : évolution future ne dépend que de sa valeur actuelle et non des valeurs passées (l'histoire du processus est entièrement résumée dans sa valeur actuelle)
-
processus markovien d'ordre
$1$ pour$t_1<\cdots<t_{k+1}$ - espace d'état discret :
$P(X(t_{k+1})=x_{k+1}|X(t_k)=x_k,\ldots,X(t_1)=x_1)=P(X(t_{k+1})=x_{k+1}|X(t_k)=x_k)$ - espace d'état continu :
$P(x_{k+1}<X(t_{k+1})<x_{k+1}+\Delta x_{k+1}|X(t_k)=x_k,\ldots,X(t_1)=x_1)=P(x_{k+1}<X(t_{k+1})<x_{k+1}+\Delta x_{k+1}|X(t_k)=x_k)$
- espace d'état discret :
-
probabilité d'état :
$\pi_i(n)=P(X(n)=i)$ avec$\sum \pi_i(n)=1$ -
probabilité de transition de l'état
$i\in S$ à$j\in S$ :$p_{ij}(n)=P(X(n+1)=j|X(n)=i)$ avec$\sum p_{ij}(n)=1$ -
matrice de transition : $P\begin{bmatrix}p_{00} & \cdots & p_{0i}\\ \vdots & \ddots & \vdots \\ p_{i0} & \cdots & p_{ii}\end{bmatrix}$ (stochastique, somme par ligne =
$1$ ) -
probabilité d'état après
$n$ étapes :$\pi_j(n)=\sum_{i\in S}p_{ij}\pi_i(n-1)$ $\pi(n)=\pi(0)P^n$ $\pi(n)=[\pi_0(n);\pi_1(n);\cdots]$
-
probabilité de transition à
$m$ étapes :$p_{ij}^{(m)}=P(X(n+m)=j|X(n)=i)=\sum_{k\in S}p_{kj}p_{ik}^{(m-1)}$ $p_{ii}^{(0)}=1$ $P^{(m)}=P^m$
-
chaine de Markov homogène stationaire au sens strict : sii distribution invariante
$\pi=\pi P$ (au moins une existe si chaine finie) -
classification
- état accéssible :
$p_{ij}^{(m)}>0$ - communication entre deux états : si accessible l'un à l'autre
$i \leftrightarrow j$ (réflexive, symétrique et transistive) - classe d'équivalence : ensemble d'états communiquant entre eux
- chaine irréductible : comporte 1 seule classe
- état absorbant : impossible de le quitter
$p_{ii}=1$ , forme une classe à lui tout seul - classe d'états absobante : impossible de la quitter
- état périodique : visitable uniquement à des multiples de
$d$ ainsi$p_{ii}^{(n)}=0$ pour chaque$n$ non multiple de$d$ (même période pour la classe) - état apériodique : si
$d=1$ - chaine apériodique : irréductible dont tous les états sont apériodiques
- état accéssible :
-
récurrence
- temps de premier passage par l'état
$i$ :$T_i=\inf{n\in\N_0:X(n)=i}$ (si vide$T_i=\infty$ ) - probabilité de retour :
$f_i=P(X(n)=i\text{ pour un certain }n\in\N_0 | X(0)=i)=P(T_i<\infty | X(0)=i)$ - état récurrent :
$f_i=1$ ou$\sum_{n=0}^\infty p_{ii}^{(n)} = \infty$ (même période pour la classe)- réccurent positif si fini
$E[T_i|X(0)=i]=\sum_{m\in\N}m P(T_i=m|X(0)=i)$ - réccurent nul si infini
- réccurent positif si fini
- état transitoire :
$f_i<1$ ou$\sum_{n=0}^\infty p_{ii}^{(n)} < \infty$ (même période pour la classe)
- temps de premier passage par l'état
-
espace d'état fini
- classe d'états réccurente postivie sii absorbante
- classe d'états transistoire sii non absorbante
- il existe au moins une classe d'états absobante
- si irréductible alors récurrente positive
- aucun état n'est récurrent nul
- ergodisme (en distrubition et en moyenne) : si irréductible, apériodique, états récurrents positifs
-
distribution stationnaire (si ergodique) : $\pi_j^*=\sum_{i\in S}\pi_i^p_{ij}$ et $\sum_{i\in S}\pi_i^=1$
- distribution satifait : $\pi^=\pi^ P$
- solution unique lorsque
$n\to\infty$ on a$\pi(n)\to\pi^*$ - stationnaire au sens strict :
$\pi(0)=\pi^*$ - s'il existe une solution : $\pi_i^>0$, chaine récurrente positvie, $\pi^$ unique
- si périodique :
$\lim_{n\to\infty}\frac{1}{n}\sum_{m=0}^{n-1}\pi_i(m)=\pi_i^*$ - temps moyen de retour à l'état
$i$ :$E[T_i|X(0)=i]=\frac{1}{\pi_i^*}$ -
$\sum_{i\in A}\sum_{j\not\in A}\pi_i^*p_{ij}=\sum_{i\in A}\sum_{j\not\in A}\pi_j^*p_{ji}$ où$A\subset S$ sous-ensemble des états
-
atteinte
- temps d'atteinte :
$H_A=\inf{n\in\N:X(n)\in A}$ où$A\subset S$ (si vide$T_i=\infty$ , différent de$T_i$ car valeur nulle possible) - probabilité d'atteinte :
$h_{iA}=P(H_A<\infty | X(0)=i)=P(X(n)\in A\text{ pour un certain }n\in\N | X(0)=i)$ -
$h_A=[h_{iA},i\in S]$ est la solution minimale non négative de$h_{iA}=\sum_{j\in S}p_{ij} h_{jA}$ si$i\not\in A$ autrement$1$ - solution unique si chaine finie
- temps moyens d'atteinte :
$\mu_{iA}^H=E[H_A|X(0)=i]=1+\sum_{j\not\in A}p_{ij}\mu_{jA}^H$ si$i\not\in A$ autrement$1$
- temps d'atteinte :
- chaines reversibles : si $\hat{p}{ij}=p{ij}$ et ergodique avec $\pi_i^\hat{p}_{ij}=\pi_j^\pi_{ji}$ (équation de balance, permet de trouver la distribution stationnaire plus facilement)
-
ergodisme et temps passé : pour toute fonction
$f:S\mapsto\mathbb R$ bornée$P\left (\frac{1}{m}\sum_{n=0}^{m-1} f(X(n))\to\sum_{i\in S}\pi_i^*f(i)\text{ pour }m\to\infty\right )=1$ - proportion de temps passé dans chaque état avant un certain temps
$m$ tend$\pi_i^*$ sur le long terme - pour
$f(x)=x$ , on a $\frac{1}{m}\sum_{n=0}^{m-1}f(X(n))=< X(n)>m$ et $\sum{i\in S}\pi_i^*f(i)=\mu_X$ - ergodisme plus fort qu'en moyenne quadratique
- proportion de temps passé dans chaque état avant un certain temps
-
non-ergodisme et temps passé : pour toute fonction
$f:S\mapsto\mathbb R$ bornée et chaine irréductible$P\left (\frac{1}{m}\sum_{n=0}^{m-1} f(X(n))\to\frac{1}{E[T_i|X(0)=i]}\text{ pour }m\to\infty\right )=1$ -
chaine cachée :
$\lambda = (P, B, \pi(0))$ - hidden : impossible de retrouver dans l'état initial en se basant sur les observations
- matrice de transition double stochastique
- deux paramètres
- nombre d'état
$N$ que peut prendre$X(n)$ - nombre
$M$ que peut prendre l'observation$O(n)$
- nombre d'état
- trois ensemble de probabilité
- distribution
$P={p_{ij}}$ des probabilités$p_{ij}=P(X(n+1)=j|X(n)=i)$ de transition entre les états$i$ et$j$ - distribution
$B={b_i(v_k)}$ des probabilités$b_i(v_k)=P(O(n)=v_k|X(n)=i)$ des observations dans l'état$i$ - distribution
$\pi(0)={\pi_i(0)}$ des probabilités d'état initiales$\pi_i(0)=P(X(0)=i)$
- distribution
-
processus markovien pour
$t_0<\cdots<t_n\in\R^+$ et suite d'états$i_0,\ldots,i_n\in S$ :$P(X(t_n)=i_n|X(t_{n-1})=i_{n-1},\ldots,X(t_0)=i_0)=P(X(t_n)=i_n|X(t_{n-1})=i_{n-1})$ -
processus homogène :
$P(X(t+s)=j|X(s)=i)=p_{ij}(t)=P(X(t)=j|X(0)=i)$ -
séquence des temps de transition :
$S(n)$ temps où se produit la $n$ième transition d'un état à un autre$S(n)=\text{inf}{t > S(n-1): X(t)\not = X(S(n-1))}$ $S(n)=\sum_{m=0}^{n-1} T(m)=T(0)+\cdots+T(n-1)$
-
séquence des temps de séjour (holding time) :
$T(n)$ intervalle de temps pendant lequel le processus reste dans un même état avec$T_i(n)=T(n)$ si$X(S(n-1))=i$ où$i\in S$ $T(n)=S(n+1)-S(n)$ -
$f_{T(n)}(t;n)=\lambda e^{-\lambda t}$ (exponentiel) - taux moyen de transition :
$\nu_i=\frac{1}{E[T_i(n)]}$ ($\nu_i >0$ evite états absorbants) - variables aléatoires indépendantes mais pas forcément identiquement distribuées car la moyenne dépend de l'état considéré, processus de poisson partage les mêmes moyennes partout)
-
chaine régulière :
$\sum_{m=0}^\infty T(m)=\lim_{n\to\infty} S(n)=\infty$ -
chaine induite :
$\hat X(n)=X(S(n))$ discret où$\hat q_{ii}=0$ et$\sum_{j\in S}\hat q_{ij}=1$ -
équations de Kolmogorov :
$\frac{\d\pi_i}{\dt}(t)=\sum_{k\in S}\pi_k(t)q_{ki}$ $p_{ij}(t_1+t_2)=\sum_{k\in S}p_{ik}(t_1)p_{kj}(t_2)$ $\pi_i(t+s)=\sum_{k\in S}\pi_k(t)p_{ki}(s)$ -
$q_{ij}=\nu_i \hat q_{ij}$ si$i\not = j$ autrement$q_{ii}=-\nu_i$ - générateur infinitésimal : matrice
$Q$ - équations prédictives :
$\frac{\d p_{ij}}{\dt}(t)=\sum_{k\in S}p_{ik}(t)q_{kj}$ avec$p(0)=1$ - équations retrospectives :
$\frac{\d p_{ij}}{\dt}(t)=\sum_{k\in S}q_{ik}p_{kj}(t)$ avec$p(0)=1$
- classification : même que sa chaine induite
-
périodicité : si
$p_{ij}(t)>0$ pour un certain$t > 0$ alors$p_{ij}(t)>0$ pour tous et ainsi pas de périodicité - récurrence : même que sa chaine induite
- ergodisme (en distrubition et en moyenne) : si irréductible, homogène, états récurrents positifs
-
distribution stationnaire (si homongène et ergodique) : $\sum_{i\in S}\pi_i^q_{ij}=0$ et $\sum_{i\in S}\pi_i^=1$
- distribution satifait :
$\pi^*Q=0$ - solution unique lorsque
$n\to\infty$ on a$\pi(t)\to\pi^*$ - stationnaire au sens strict :
$\pi(0)=\pi^*$ (pas toujours valable si l'espace d'état est infini) - proportion hors de l'état :
$\pi_i^*\nu_i$ - proportion jusqu'à l'état :
$\sum_{j\not =i}\pi_j^*q_{ji}$
- distribution satifait :
-
chaines reversibles : si la chaine induite $\hat{\tilde p}{ij}=\hat p{ij}$ et ergodique on a $\hat\pi_i^\hat q_{ij}=\hat\pi_j^\hat\pi_{ji}$ et
$\pi_i^*q_{ij}=\pi_j^*q_{ji}$ (équation de balance, permet de trouver la distribution stationnaire plus facilement) -
ergodisme et temps passé : pour toute fonction
$f:S\mapsto\mathbb R$ bornée$P\left (\frac{1}{T}\int_0^T f(X(t))\dt\to\sum_{i\in S}\pi_i^*f(i)\text{ pour }T\to\infty\right )=1$ - proportion de temps passé dans chaque état avant un certain temps
$T$ tend$\pi_i^*$ sur le long terme - pour
$f(x)=x$ , on a $\frac{1}{T}\int_0^Tf(X(t))\dt=< X(t)>T$ et $\sum{i\in S}\pi_i^*f(i)=\mu_X$ - ergodisme plus fort qu'en moyenne quadratique
- proportion de temps passé dans chaque état avant un certain temps
-
file d'attente : modélise des clients,
$n$ servers et$1$ tampon caractérisé par$A/B/s/K/C/DS$ -
$A$ : distribution des temps entre les arrivées des clients -
$B$ : distribution des durées de service -
$s$ : nombre de serveur -
$K$ : capacité de la file (en service et en attente de service, par défaut$\infty$ ) -
$C$ : population des clients (par défaut$\infty$ ) -
$DS$ : disciple de service (par défaut, FIFO)
-
-
distributions des temps entre arrivées et durées de service
-
$M$ : loi exponentielle -
$E_k$ : loi d'Erlang-k -
$D$ : constante deterministe -
$G$ ou$GI$ : loi générale ($I$ si i.i.d.)
-
-
grandeurs utilisées
-
$T$ : temps entre deux arrivées consécutives de clients -
$1/\lambda=E[T]$ : temps moyen entre deux arrivées consécutives avec$\lambda$ taux d'arrivée moyen -
$S(n)$ : temps de service du $n$ième client -
$1/\mu=E[S]$ : durée moyenne de service par client avec$\mu$ (en messages/sec) taux de service moyen par serveur (et$s\mu$ est le taux de service moyen pour$s$ serveurs) -
$1/\mu'$ : longueur moyenne des messages (en bits/message, si la capcité est en bits/sec) avec$\mu=\mu'C$ et$1\mu'C$ temps moyen de transmission (réseau de communication) -
$N(t)$ : nombre de clients dans la file d'attente et ceux en train d'être servi au temps$t$ -
$Q$ : nombre de clients dans le tampon -
$W$ : temps d'attente avant service -
$R=W+S$ : temps de réponse du système
-
-
ergodisme : nombre client devient infini, instable, si
$\lambda/s\mu$ pas respecté (si queue finie, système toujours stable) -
loi de Little : nombre moyen de clients dans le système = taux d'arrivée x temps de réponse moyen (système sans perte)
$E[N]=\lambda E[R]$ $E[Q]=\lambda E[W]$
-
théorème de Burke :
$M/M/1$ stationnaire avec paramètre$\lambda$ , alors le processus de départ a le même paramètre et le nombre de client dans le système est indépendant de la séquence des temps de départ
$x^3+y^3=(x+y)(x^2-xy+y^2)$ $\sqrt{b}-\sqrt{a}=\frac{b-a}{\sqrt{b}+\sqrt{a}}$ $\frac{1}{2}+\frac{1}{2^2}+\frac{1}{2^3}+\cdots+\frac{1}{2^n}=1-\frac{1}{2^n}$ -
$\sqrt{1+x}=1+\frac{x}{2}$ when$x << 1$ $e^x=\lim_{n\to\infty}(1+\frac{x}{n})^n$ - geometric series : converge to
$\sum_{n=1}^\infty ar^{n-1}=\frac{a}{1-r}$ if$|r|<1$ - Riemann series :
$\sum_{n=1}^\infty \frac{1}{p^\alpha}$ converges if$\alpha >1$ $(x+y)^n=\sum_{k=0}^n {n \choose k} x^{n-k}y^k$ $erf(x)=\frac{2}{\sqrt{\pi}}\int_0^xe^{-t^2}\dt$ $n!\approx n^ne^{-n}\sqrt{2\pi n}$
$2\sin^2 t = 1-\cos 2t$ $2\cos^2 x = 1+\cos 2x$ $\sin 2x = 2\sin x \cos x$ $\sin(a+b)=\sin a\cos b+\cos a\sin b$ $\cos(a+b)=\cos a\cos b-\sin a\sin b$ $\tan^2 x +1=\frac{1}{\cos^2 x}$ $\cot^2 x +1=\frac{1}{\sin^2 x}$ $\sin 0 = \frac{1}{2}\sqrt{0} = \cos \pi/2 = 0$ -
$\sin \pi/6 = \frac{1}{2}\sqrt{1} = \cos \pi/3 = \frac{1}{2}$ $\sin \pi/4 =\frac{1}{2}\sqrt{2} = \cos \pi/4 =\frac{\sqrt{2}}{2}$
$\sin \pi/3 = \frac{1}{2}\sqrt{3} = \cos \pi/6=\frac{\sqrt{3}}{2}$ $\sin \pi/2 = \frac{1}{2}\sqrt{4} = \cos 0 = 1$ $\cosh z =\frac{e^z+e^{-z}}{2}$ $\sinh z =\frac{e^z-e^{-z}}{2}$ $\cos z =\frac{e^{iz}+e^{-iz}}{2}=\cosh iz$ $\sin z =\frac{e^{iz}-e^{-iz}}{2i}=\frac{\sinh iz}{i}$ $e^z=\cosh z +\sinh z=\cos z+i\sin z$ $e^{-z}=\cosh z -\sinh z$ $\cosh^2 z -\sinh^2 z = 1$ $\sin mx\cos nx=\frac{1}{2}[\sin (m+n)x + \sin (m-n)x]$ $\cos mx\cos nx=\frac{1}{2}[\cos (m+n)x + \cos (m-n)x]$ $\sin mx\sin nx=\frac{1}{2}[-\cos (m+n)x + \cos (m-n)x]$
$\tan'x=\sec^2x$ $\csc'x = -\csc x\cot x$ $\sec'x = \sec x\tan x$ $\cot'x = -\csc^2x$ $\sin'^{-1}x = \frac{1}{\sqrt{1-x^2}}$ $\cos'^{-1}x = -\frac{1}{\sqrt{1-x^2}}$ $\tan'^{-1}x = \frac{1}{1+x^2}$ $\csc'^{-1}x = -\frac{1}{x\sqrt{x^2-1}}$ $\sec'^{-1}x = \frac{1}{x\sqrt{x^2-1}}$ $\cot'^{-1}x = -\frac{1}{1+x^2}$ - inverse function :
$(f^{-1})'(a)=\frac{1}{f'(f^{-1}(a))}$ or$(f^{-1})'(f(a))=\frac{1}{f'(a)}$ $\div\grad f=\Delta f$ $\rot\grad f=\vec 0$ $\div\rot F=0$ $\div(f\grad g)=f\Delta g +\grad f\cdot\grad g$ $\grad(fg)=f\grad g+g\grad f$ $\div(fF)=f\div F+F\cdot\grad f$ $\rot\rot F=-\Delta F +\grad\div F$ $\rot(fF)=\grad f\wedge F+f\rot F$
$\int \ln x dx = x \ln x - x$ $\int x \ln xdx= \frac{1}{4}x^2(2\ln x -1)$ $\int \frac{1}{x\log x}dx=\log (\log x)$ $\int \frac{1}{x\log^2 x}dx=-\frac{1}{\log x}$ $\int \frac{1}{x}dx = \ln |x|$ $\int a^x dx = \frac{1}{\ln a} a^x$ $\int \tan x dx = \ln |\sec x| $ $\int \frac{a}{a^2+x^2}dx = \tan^{-1}\frac{x}{a}$ $\int \frac{a}{a^2-x^2}dx = \frac{1}{2}\ln\left|\frac{x+a}{x-a}\right|$ $\int \frac{1}{\sqrt{a^2-x^2}} dx = \sin^{-1} \frac{x}{a}$ $\int \frac{1}{\sqrt{x^2-a^2}} dx = \cosh^{-1} \frac{x}{a}$ $\int \frac{1}{\sqrt{x^2+a^2}} dx = \sinh^{-1} \frac{x}{a}$ $\int \sin^{-1} x dx=\sqrt{1-x^2}+x\sin^{-1} x$ $\int \cos^{-1} x dx=-\sqrt{1-x^2}+x\cos^{-1} x$ $\int \tan^{-1} x dx=-\frac{1}{2}\ln(x^2+1)+x\tan^{-1} x$ $\int \sin x \cos xdx = -\frac{1}{2}\cos^2 x$ $\displaystyle\int^\pi_{-\pi} 1\cdot \cos (nx),dx=\left.\frac{1}{n}\sin (nx)\right|^{\pi}_{-\pi}=0.$ $\quad\displaystyle\int^\pi_{-\pi} 1\cdot \sin (nx),dx=\left.-\frac{1}{n}\cos (nx)\right|^{\pi}_{-\pi}=0.$ $\displaystyle\int^\pi_{-\pi} \sin (nx)\cos (nx),dx=\left.\frac{\sin^2 (nx)}{2n}\right|^{\pi}_{-\pi}=0.$ $\displaystyle\int^\pi_{-\pi} \sin (mx)\sin(nx),dx=0$ $\displaystyle\int^\pi_{-\pi} \cos (mx)\cos(nx),dx=0$ $\displaystyle\int^\pi_{-\pi} \sin (mx)\cos(nx),dx=0$ $\int_{{-c}}^{{c}}\sin {x};\mathrm{d}x = 0 !$ $\int_{{-c}}^{{c}}\cos {x};\mathrm{d}x = 2\int_{{0}}^{{c}}\cos {x};\mathrm{d}x = 2\int_{{-c}}^{{0}}\cos {x};\mathrm{d}x = 2\sin {c} !$ $\int_{{-c}}^{{c}}\tan {x};\mathrm{d}x = 0 !$ $\int_{-\frac{a}{2}}^{\frac{a}{2}} x^2\cos^2 {\frac{n\pi x}{a}};\mathrm{d}x = \frac{a^3(n^2\pi^2-6)}{24n^2\pi^2} \qquad\mbox{(for }n=1,3,5...\mbox{)},!$ $\int_{\frac{-a}{2}}^{\frac{a}{2}} x^2\sin^2 {\frac{n\pi x}{a}};\mathrm{d}x = \frac{a^3(n^2\pi^2-6(-1)^n)}{24n^2\pi^2} = \frac{a^3}{24} (1-6\frac{(-1)^n}{n^2\pi^2}) \qquad\mbox{(for }n=1,2,3,...\mbox{)},!$ $\int_{{0}}^{{2 \pi}}\sin^{2m+1}{x}\cos^{2n+1}{x};\mathrm{d}x = 0 ! \qquad {n,m} \in \mathbb{Z}$ $\int_0^{2\pi} \sin x \cos^2 x \d x=0$ $\int_0^{2\pi} \sin^2 x \cos x \d x=0$ $\int_0^{2\pi} \sin^2 x \d x=\pi$ $\int_0^{2\pi} \cos^2 x \d x=\pi$ $\int_0^{2\pi} \sin^4 x \d x=\frac{3\pi}{4}$ $\int_0^{2\pi} \cos^4 x \d x=\frac{3\pi}{4}$ $\int_0^{2\pi} \sin^2 x \cos^2 x \d x=\frac{\pi}{4}$ $\int x\sin x\d x=\frac{\sin(n x)-n x \cos(n x)}{n^2}$ $\int x\cos x\d x=\frac{nx\sin(n x)+ \cos(n x)}{n^2}$ $\frac{2}{T}\int_0^T\co\cos(\frac{2\pi m}{T}x)\d x=\frac{2}{T}\int_0^T\si\sin(\frac{2\pi m}{T}x)\d x\cases{0 &\t{si }n\not=m\\ 1 &\t{si }n=m}$ $\int_0^T\si\cos(\frac{2\pi m}{T}x)\d x=0$
$\frac{1}{1-ax}=\sum_{n=0}^\infty (ax)^n=1+ax+ax^2+ax^3+\cdots$ $\frac{1}{1+x}=\sum_{n=0}^\infty (-x)^n=1-x+x^2-x^3+\cdots$ $\frac{1}{(1-x)^2}=\sum_{n=0}^\infty (n+1)x^n=1+2x+3x^2+4x^3+\cdots$ $\sin x=\sum_{n=0}^\infty (-1)^n \frac{x^{2n+1}}{(2n+1)!}=x-\frac{x^3}{3!}+\frac{x^5}{5!}-\cdots$ $\cos x=\sum_{n=0}^\infty (-1)^n \frac{x^{2n}}{(2n)!}=1-\frac{x^2}{2!}+\frac{x^4}{4!}-\cdots$ $\tan^{-1} x=\sum_{n=0}^\infty (-1)^n \frac{x^{2n+1}}{2n+1}=x-\frac{x^3}{3}+\frac{x^5}{5}-\cdots$ $ln(1+x)=\sum_{n=1}^\infty (-1)^n \frac{x^n}{n}=x-\frac{x^2}{2}+\frac{x^3}{3}-\cdots$
- Jacobian : $J=|\frac{\partial(x,y)}{\partial(u,v)}|=\begin{vmatrix} \frac{dx}{du}&\frac{dx}{dv} \\ \frac{dy}{du}&\frac{dy}{dv}\end{vmatrix}$
-
substitution :
$\int_{\mathbb D}f(\vec x) d\vec x = \int_S f(T(\vec u)) J d\vec u$ - polar coordinates :
$x = r \cos \theta\quad y = r\sin\theta\quad J=r$ and$\int_{\mathbb D}f(\vec x)d\vec x = \int_a^b \int_{g(\theta)}^{f(\theta)} f(r,\theta)r dr d\theta$ - cylindrial coordinates :
$x = r \cos \theta\quad y = r\sin\theta\quad z=z \quad J=r$ - spherical coordinates :
$x = \rho \sin \phi \cos \theta\quad y = \rho \sin\phi\sin\theta\quad z=\rho\cos\phi \quad J=\rho^2\sin \phi$ where$0 \le \theta \le 2\pi$ and$0\le \phi\le\pi$ (starting on the positive y-axis side) - affine transformations : (exemple : barycentric coordinates)
$\vec x = \vec v_1 \beta_1 + \vec v_2 \beta_2 \quad 0 \le \beta_i \le 1 \quad \beta_1+\beta_2=1$ - rotation matrix : $A=\begin{pmatrix} \cos \theta & -\sin \theta \\ \sin \theta & \cos \theta \end{pmatrix}$
-
gaussienne multivariée :
$f_X(x)=\frac{1}{\sqrt{(2\pi)^n\det\Sigma}}e^{-\frac{1}{2}(x-\mu)^T\Sigma^{-1}(x-\mu)}$ - matrice de covariance :
$\Sigma$ symmetrique et semi-définie postivie - entièrement caractérisisé par les moments d'ordre 1 et 2
- changement de variables linéaire :
$Y=AX+b$ alors$S=A\Sigma A^T$ et$m=A\mu+b$ remplacent$A$ et$\mu$ - décorrelation possible par diagonalisation
- matrice de covariance :
-
sinusoide à phase aléatoire :
$X(t,\Phi(\zeta))=a\sin(2\pi f_0t+\Phi(\zeta))$ -
$\Phi$ either$0$ or$\pi$ (equal chances)$\mu_X(t)=0$ $R_X(t_1,t_2)=\frac{a^2}{2}[\cos(2\pi f_0(t_1-t_2))-\cos(2\pi f_0(t_1+t_2))]$ - pas WSS
-
$\Phi\sim U(0,2\pi)$ $\mu_X(t)=0$ $R_X(t_1,t_2)=\frac{a^2}{2}\cos(2\pi f_0(t_1-t_2))$ - SSS
- ergodique à sa moyenne et à sa variance si
$f_0\not=0$ $S_X(f)=\frac{a^2}{4}(\delta(f-f_0)+\delta(f+f_0))$
-
-
sinusoide à phase et amplitute aléatoire :
$X(t)=A\sin(2\pi f_0t+\Phi)$ avec$\Phi\sim U(0,2\pi)$ et$A=Bernouilli(p)$ - ergodique à sa moyenne, pas à sa variance (certaines réalisations auront différentes amplitudes)
-
sinusoide en quadrature à amplitudes aléatoires :
$X(t)=A\cos(2\pi f_0t)+B\sin(2\pi f_0 t)$ avec$A,B$ de moyenne nulle et même variance$\sigma^2$ $\mu_X(t)=0$ $R_X(t_1,t_2)=\sigma^2\cos(2\pi f_0(t_1-t_2))$ - WSS et même SSS si
$A,B$ normal
-
bruit blanc : modèle idéalisé
- gaussien : si la distribution de
$N(t)$ suit une loi gaussienne -
$\mu_N(t)=0$ par défaut -
$R_N(\tau)=\frac{N_0}{2}\delta(\tau)$ (infini à$0$ et donc irréalisable) $S_N(f)=\frac{N_0}{2}$ - à bande étroite : largeur de bande
$2B$ centrée autour de la fréquence$f_0$ -
$S_N(f)=\frac{N_0}{2}$ si$f_0-B<|f|<f_0+B$ autrement$0$ $R_N(\tau)=2N_0B\cos(2\pi f_0 \tau)\sinc(2B\tau)$
-
- gaussien : si la distribution de
-
processus gaussien :
$f_X(t;\ts)=\frac{1}{\sqrt{(2\pi)^n|det\Gamma_X|}}e^{-\frac{1}{2}(x-\mu_x)^T\Gamma_X^{-1}(x-\mu_X)}$ $X=[X(t_1)\ldots X(t_n)]^T$ $x=[x_1\ldots x_n]^T$ $\mu_X=[E[X(t_1)]\ldots E[X(t_n)]]^T$ - $\Gamma_X=\begin{bmatrix}C_X(t_1,t_1)=\sigma^2 & \cdots & C_X(t_1,t_n)\\ \vdots & \ddots & \vdots \\ C_X(t_n,t_1) & \cdots & C_X(t_n,t_n)=\sigma^2\end{bmatrix}$
- entièrement caractérisé par moments d'ordre 1 et 2
-
$Y(t)=\int X(t)\dt$ avec$X,Y$ gaussien - WSS
$\equiv$ SSS
-
pulse amplitude modulation (PAM) :
$X(t)=\infsum A_k g(t-kT-D)$ avec$D\sim U(0,T)$ et variables aléatoires$A_k$ $\mu_X(t)=\frac{\mu_A}{T}\infint g(s')\d s'$ $R_X(t_1,t_2)=\frac{1}{T}\sumin R_A(n)\infint g(s')g((t_2-t_1)+nT+s')\d s'$ - cyclo-stationnaire
-
$S_X(f)=\frac{1}{T}G(f)G(-f)\hat S_A(e^{-2\pi j f T})=\frac{1}{T}|G(f)|^2\hat S_A(e^{-2\pi j f T})$ avec$G(f)=\infint g(t)e^{-2\pi j ft}\dt$
-
processus de poisson
- pas WSS mais accroissements stationnaires
-
bruit blanc : bien défini à l'origine, suite de variables aléatoires centrées non corrélées
- moyenne nulle
-
$R_N(n_1,n_2)=\sigma_N^2$ si$n_1=n_2$ autrement$0$
-
processus d'innovation :
$U(n)$ est un bruit blanc de variance$\sigma_U^2$ -
moyenne mobile (MA) :
$X(n)=\sum_{k=0}^mb_kU(n-k)$ -
$\hat H_{MA}(z)=\hat H_{ARMA}(z)$ avec$\hat A(z)=1$ (que des zéros)
-
-
processus auto-régressif (AR) :
$X(n)=-\sum_{k=1}^pa_kX(n-k)+U(n)$ (coefficient choisi pour stabilité)-
$\hat H_{AR}(z)=\hat H_{ARMA}(z)$ avec$\hat B(z)=1$ (que des poles)
-
-
processus ARMA :
$X(n)=-\sum_{k=1}^pa_kX(n-k)+\sum_{k=0}^mb_kU(n-k)$ $\hat H_{ARMA}(z)=\frac{\hat B(z)}{\hat A(z)}=\frac{\sum_{k=0}^m b_kz^{-k}}{1+\sum_{k=1}^p a_k z^{-k}}$
-
processus ARIMA (intregrated) :
$Y(n)=Y(n-1)+X(n)$ -
filtre optimal de Wiener : prédiction (délais) ou filtrage (ajout de bruit)
- équations normales (Wiener-Hopf) :
$\sum_{l=-\infty}^\infty h(k)R_X(k-l)=R_{DX}(k)$ start at$l=0$ if causalilty needed - transmittance du filtre de Wiener
$H(f)=\frac{S_{DX}(f)}{S_X(f)}$ où$DX$ est le signal désiré
- équations normales (Wiener-Hopf) :
-
chaine de Markov à deux états
- matrice de transition : $P=\begin{bmatrix}1-p & p \\ q & 1-q \end{bmatrix}$ et $P^n=\frac{1}{p+q}\begin{bmatrix}q & p \\ q & p\end{bmatrix}+\frac{(1-p-q)^n}{p+q}\begin{bmatrix}p & -p \\ -q & q\end{bmatrix}$
- irréductible
- états récurrents positifs
- aprériodique : si
$p+q<2$ - distribution stationnaire : $\pi^*=\begin{bmatrix}\frac{q}{p+q} & \frac{p}{p+q}\end{bmatrix}$
-
marche aléatoire uni-dimensionnelle sur
$\mathbb Z$ :$X(n+1)=X(n)+U(n)$ avec$U\sim Bernouilli(p)$ de valeur$-1$ ou$1$ - cas
$p=1/2$ : marche symmetrique- états récurrents nuls :
$p_{00}^{(2n)}\approx\frac{1}{\sqrt(\pi n)}$ et$p_{00}^{(2n+1)}=0$ - similaire au cas équiprobable sur
$\mathbb Z^2$ mais plus vrai dès que$\mathbb Z^k$ et$k\ge 3$
- états récurrents nuls :
- cas
$p<1/2$ - états transistoires
- cas
-
marche aléatoire uni-dimensionnelle sur
$\mathbb N$ - barrière
$0$ et$N$ :$p_{NN}=p=1-p_{00}$ - toute chaine avec des barrières et les transitions limités à ses deux voisins immédiats est reversible
- ergodique
- distribution stationnaire :
$\pi_i^*=\frac{1-\rho}{1-\rho^{N+1}}\rho^i$ avec$\rho=\frac{p}{1-p}$
- barrière
-
marche aléatoire sur un cercle :
$N+1$ états$p_{N0}=p=1-p_{0N}$ - reversible si
$p=1/2$ autrement non car$p_{ij}=p_{ji}$ selon les équations de balances - nombre d'état impaire
- ergodique
- distribution stationnaire :
$\pi_i^*=\frac{1}{N+1}$
- nombre d'état paire
- périodique de période
$2$ - distribution stationnaire :
$\pi_i^*=\frac{1}{N+1}$
- périodique de période
-
ruine du joueur sur
$0,\ldots,N$ - chaine absorbante
- gagnant :
$h_{iN}=qh_{i-1,N}+ph_{i+1,N}$ avec$h_{0N}=0$ et$h_{NN}=1$ -
$h_{iN}=\frac{(q/p)^i-1}{(q/p)^N-1}$ si$p\not=q$ -
$h_{iN}=i/N$ si$p=q$
-
- temps de jeu
-
$\mu_{i,{0,N}}^H=\frac{1}{p-q}(N\frac{(q/p)^i-1}{(q/p)^N-1}-i)$ si$p\not=q$ -
$\mu_{i,{0,N}}^H=i(N-i)$ si$p=q$
-
-
ruine du joueur sur
$\mathbb N$ - chaine absorbante
- gagnant :
$h_{i0}=qh_{i-1,0}+ph_{i+1,0}$ avec$h_{00}=1$ -
$h_{i0}=(q/p)^i$ si$p>1/2$ -
$h_{i0}=1$ si$p\le 1/2$
-
-
processus de naissance et de mort
- chaine de Markov à deux états :
- générateur infinitésimal : $Q=\begin{bmatrix}-\lambda & \lambda \\ \mu & -\mu\end{bmatrix}$
- chaine induite : $\hat Q=\begin{bmatrix}0 & 1 \\ 1 & 0 \end{bmatrix}$
- distribution stationnaire : $\pi^*=\begin{bmatrix}\frac{\mu}{\lambda +\mu} & \frac{\lambda}{\lambda + \mu}\end{bmatrix}$
- distribution :
$\pi_0(t)=\frac{\mu}{\lambda+\mu}+(\pi_0(0)-\frac{\mu}{\lambda + \mu})e^{-(\lambda +\mu)t}$ et$\pi_1(t)=\frac{\lambda}{\lambda+\mu}+(\pi_1(0)-\frac{\lambda}{\lambda + \mu})e^{-(\lambda +\mu)t}$
- naissance pure : transisition possible uniquement de
$i$ à$i+1$ - générateur infinitésimal :
$q_{ij}=\lambda_i$ si$j=i+1$ autrement$0$ ou$q_{ii}=-\lambda_i$ - chaine induite :
$\hat q_{ij}=1$ si$j=i+1$ autrement$0$ - distribution stationnaire : c'est le processus de poisson
$\pi_i(t)=\frac{(\lambda t)^i}{i!}e^{-\lambda t}$ - processus de Yule : compte le nombre d'individu d'une population avec
$\lambda_i=i\lambda$ et$\pi_i(t)=e^{-\lambda t}(1-e^{-\lambda t})^{i-1}$
- générateur infinitésimal :
- naissance et mort :
- générateur infinitésimal : $q_{ij}=\begin{cases}\mu_i & j=i-1\\ -(\lambda_i+\mu_i) & j=i \\ \lambda_i & j=i+1 \\ 0 & \text{sinon}\end{cases}$ avec si
$i\ge 1$ $q_{ij}=\begin{cases}-\lambda_0 & j=0\\ \lambda_0 & j=1 \\ 0 & j\ge 2\end{cases}$ - reversible car marche aléatoire
- chaine induite
$\hat q_{0,1}=1$ $\hat q_{i,i+1}=\frac{\lambda_i}{\lambda_i+\mu_i}$ $\hat q_{i,i-1}=\frac{\lambda_i}{\lambda_i+\mu_i}$
- équation de balances
- $\lambda_0\pi_0^=\mu_1\pi_1^$
- $(\lambda_i+\mu_i)\pi_i^=\lambda_{i-1}\pi_{i-1}^+\mu_{i+1}\pi_{i+1}^*$
- distribution stationnaire :
$\pi_0^*=\frac{1}{1+\sum_{i=0}^\infty \frac{\lambda_{i-1}\cdots\lambda_0}{\mu_i\cdots\mu_1}}$
- générateur infinitésimal : $q_{ij}=\begin{cases}\mu_i & j=i-1\\ -(\lambda_i+\mu_i) & j=i \\ \lambda_i & j=i+1 \\ 0 & \text{sinon}\end{cases}$ avec si
- chaine de Markov à deux états :
-
file
$M/M/1$ - stabilité :
$\lambda<\mu$ - distribution stationnaire :
$\pi_n^*=(1-\rho)\rho^n$ avec$\rho=\lambda/\mu$ - fonction génératrice :
$G_N(z)=\sum_{n=0}^\infty\pi_n^*z^n=\frac{1-\rho}{1-\rho z}$ - nombre moyen de clients dans la file d'attente :
$E[N]=\frac{\rho}{1-\rho}$ - temps de réponse :
$f_R(r )=(\mu-\lambda)e^{-(\mu-\lambda)r}$ - tiré de
$f_{R|N=n}(r|N=n)=\frac{\mu(\mu r)^ne^{-\mu r}}{n!}$ qui est une variable aléatoire d'Erlang (somme d'exponentielle) - tiré du temps de séjour quand un client arrive dans la file avec
$n$ clients :$R=S(1)+\cdots+S(n)+S(n+1)$ - vérifie
$E[R]=1/(\mu-\lambda)$ via la loi de little
- tiré de
- stabilité :
-
file
$M/M/s/K$ - centraux téléphoniques sans attente
$M/M/s/s$ - appels poissonniens : taux
$\lambda$ - durées moyenne des appels :
$\frac{1}{\mu}$ - distribution stationnaire : $\pi_n^=\frac{(\lambda/\mu)^n}{n!}\pi_0^$ avec
$\pi_0^*=\frac{1}{\sum_{n=0}^s(\lambda/\mu)^n/n!}$ - formule d'Erlang-B :
$P(rejet)=\pi_s^*=B(s,\lambda/\mu)$
- appels poissonniens : taux
- centraux téléphoniques avec attente
$M/M/s$ - formule d'Erlang-C :
$P(attente)=P(X\ge s)=\frac{\rho^s/s!}{(1-\rho/s)\sum_{n=0}^{s-1}\rho^n/n!+\rho^s/s!}C(s,\rho=\lambda/\mu)$
- formule d'Erlang-C :
- centraux téléphoniques sans attente
- file
$M/GI/1$ - plus compliqué car non markovien : construction de
$\hat N(k)=N(S_d(k))$ - nombre de clients arrivant dans la file pendant que $k$ième client est servi :
$P(A(k)=n)=\int_0^\infty e^{-\lambda s}\frac{(\lambda s)^n}{n!}f_S(s)\d s$ - générateur infinitésimal :
$\hat q_{mn}=P(\hat N(k+1)=n|\hat N(k)=m)=P(A(k+1)=n-m+1)$ si$m\ge 1$ autrement$P(A(k+1)=n)$ - distribution stationnaire : $\hat\pi_n^=a_n\hat\pi_0^+\sum_{m=0}^\infty a_{n-m+1}\hat\pi_m^-a_{n+1}\hat\pi_0^$ avec
$\hat\pi_0^*=1-\rho$ - à l'équilibre les probabilités de
$N(t)$ coincindent avec$\hat N(t)$ (fonction génératice) :$G_{\hat N}(z)=\frac{(1-p)(z-1)G_A(z)}{z-G_A(z)}$ - nombre moyen de client dans la file :
$E[N]=\frac{\rho}{1-\rho}(1-\frac{\rho(1-\mu^2\sigma_S^2)}{2})$
- plus compliqué car non markovien : construction de
- file
$M/GI/\infty$ - densité de probabilité jointe des temps d'arrivée
$S(1)<\cdots < S(n)$ :$f_{S(1)\ldots S(n)|N(t)=n}(s_1,\ldots,s_n|N(t)=n)=\frac{n!}{t^n}$ sachant que le temps auqel l'une de ces$n$ arrivées a eu lieu est distribué uniformément dans$[0,t]$ - probabilité qu'un des
$m$ clients pris au hasard n'ait pas terminé son service au temps$t$ :$p(t)\frac{1}{t}\int_0^t(1-F_S(s))\d s$ - nombre de client qui n'ont pas encore terminé leur service au temps
$t$ :$P(N(t)=n|A(t)=m)=C_m^np^n(1-p)^{m-n}$ (Binomial) - distribution stationnaire :
$\pi_n(t)=\frac{(\lambda t p(t))^n}{n!}e^{-\lambda t p(t)}$ - nombre moyenne de client dans le système :
$E[N]=\rho$ - pour le processus de départ : indépendant (étend le théorème de Burke), suit un loi de poisson avec paramètre
$\lambda t$
- densité de probabilité jointe des temps d'arrivée
- file
$M/G/s/s$ : plus compliqué mais formule d'Erlang-B reste valable