ÐÁÍÅÐÉÓÔÇÌÉÏ ÊÑÇÔÇÒ - ÔÌÇÌÁ ÌÁÈÇÌÁÔÉÊÙÍ

Ðñüïäïò ãéá ôï ìÜèçìá È. ÐéèáíïôÞôùí

ÄéäÜóêùí: Ìé÷Üëçò ÊïëïõíôæÜêçò

Ïé áðáíôÞóåéò óáò ðñÝðåé íá åßíáé ðëÞñùò áéôéïëïãçìÝíåò êáé èá äïèåß éäéáßôåñï âÜñïò óôï ðþò åêöñÜæåóôå. Äåí åðéôñÝðåôáé íá Ý÷åôå ìáæß óáò âéâëßá Þ Üëëåò óçìåéþóåéò. ÅðéôñÝðåôáé ç ÷ñÞóç õðïëïãéóôÞ.

1. (á) Áí $n$ ðåñéôôüò áðïäåßîôå ìå óõíäõáóôéêü åðé÷åßñçìá üôé

$$\sum_{\mbox{$k$ Üñôéïò}} {n \choose k} = \sum_{\mbox{$k$ ðåñéôôüò}} {n \choose k}.$$

(â) Äåßîôå ôï ßäéï ãéá ãåíéêü $n$ ìå ïðïéïíäÞðïôå ôñüðï.

Ëýóç: (á) Ôï áñéóôåñü ìÝëïò åßíáé ôï ðëÞèïò üëùí ôùí õðïóõíüëùí ôïõ ${\left\{{1,\ldots,n}\right\}}$ ìå Üñôéï ìÝãåèïò, åíþ ôï äåîß ìÝëïò åßíáé ôï ðëÞèïò áõôþí ìå ðåñéôôü ìÝãåèïò. Áí üìùò ôï $n$ åßíáé ðåñéôôü ôüôå áõôÝò ïé äýï êáôçãïñßåò õðïóõíüëùí ìðïñïýí íá ôåèïýí óå 1-1 áíôéóôïé÷ßá

$$A \to A^c$$

áíôéóôïé÷ßæïíôáò êÜèå óýíïëï ìå ðåñéôôü ìÝãåèïò óôï óõìðëÞñùìÜ ôïõ ðïõ Ý÷åé Üñôéï ìÝãåèïò. ¶ñá ïé äýï êáôçãïñßåò óõíüëùí åßíáé éóïðëçèéêÝò êáé áõôü áêñéâþò ëÝåé ç éóüôçôá.

(â) ×ñçóéìïðïéïýìå áðëÜ ôï äéùíõìéêü èåþñçìá

$$(1+x)^n = \sum_{k=0}^n {n \choose k} x^k$$

ìå $x = -1$.

2. (á) ÄéáëÝãïõìå 6 ÷áñôéÜ áðü ìéá óõíçèéóìÝíç ôñÜðïõëá (13 íïýìåñá åðß 4 ó÷Ýäéá). Ðïéá ç ðéèáíüôçôá Ýíá áðü áõôÜ ôá ÷áñôéÜ íá åßíáé ôï 4 óðáèß êáé ç åîÜäá íá Ý÷åé 6 äéáäï÷éêÜ íïýìåñá;
(â) Ñß÷íïõìå Ýíá óõììåôñéêü íüìéóìá 100 öïñÝò. Ðáßñíïõìå Ýôóé ìéá áêïëïõèßá ìÞêïõò 100 ðïõ óå êÜèå èÝóç Ý÷åé Ê Þ Ã. Äåßîôå üôé ç ðéèáíüôçôá íá ìçí õðÜñ÷ïõí 5 äéáäï÷éêÝò èÝóåéò óôéò ïðïßåò íá åìöáíßæåôáé ç ìïñöÞ ÊÃÃÊÊ åßíáé ôï ðïëý

$$\left(31 \over 32\right)^{20}.$$

Ëýóç: (á) ÕðÜñ÷ïõí áêñéâþò 4 åîÜäåò áðü äéáäï÷éêÜ íïýìåñá ðïõ ðåñéÝ÷ïõí ôï 4, ïé 1-6, 2-7, 3-8, 4-9. Ãéá êÜèå ìéá áðü áõôÝò ôï ó÷Ýäéï ôùí 5 öýëëùí åêôüò ôïõ 4 åßíáé åëýèåñï Üñá ãéá êÜèå ìéá áðü ôéò 4 åîÜäåò õðÜñ÷ïõí $4^5$ åðéëïãÝò ó÷åäßùí ãéá áõôÜ ôá íïýìåñá. ¶ñá ç æçôïýìåíç ðéèáíüôçôá åßíáé

$${4\cdot 4^5 \over {52 \choose 6}} = {4^6 \over {52 \choose 6}}.$$

(â) ¸óôù $A$ ôï åíäå÷üìåíï íá ìçí åìöáíßæåôáé ðïõèåíÜ ç ìïñöÞ ÊÃÃÊÊ êáé $B$ ôï åíäå÷üìåíï ç ìïñöÞ áõôÞ íá ìçí åìöáíßæåôáé ïýôå ðåíôÜäá 1-5, ïýôå óôçí 6-10, ïýôå óôçí 11-15, ïýôå, êëð, ïýôå óôçí 96-100. Ðñïöáíþò ôï $A$ óõíåðÜãåôáé ôï $B$, Üñá ${{\bf {Pr}}\left[{A}\right]} \le {{\bf {Pr}}\left[{B}\right]}$. Ãéá êÜèå ìéá áðü ôéò 20 ðåíôÜäåò ðïõ áíáöÝñïíôáé óôï $B$ ïíïìÜæïõìå $B_i$ ôï åíäå÷üìåíï íá ìçí åìöáíßæåôáé ç ìïñöÞ ÊÃÃÊÊ óôçí ðåíôÜäá áõôÞ ($i=1,\ldots,20$). Ôüôå ôá $B_i$ åßíáé áíåîÜñôçôá áöïý ôï êáèÝíá åîáñôÜôáé áðü äéáöïñåôéêÝò ñßøåéò ôïõ íïìßóìáôïò êáé åðßóçò ${{\bf {Pr}}\left[{B_i}\right]} = 1-2^{-5} = 31/32$ ìéá êáé ç ðéèáíüôçôá íá Ý÷ù ôç ìïñöÞ áõôÞ åßíáé $2^{-5}$. ¶ñá

$$\begin{eqnarray*} {{\bf {Pr}}\left[{A}\right]} & \le & {{\bf {Pr}}\left[{B}\righ... ...}}\left[{B_{20}}\right]}\\ &=& \left({31\over 32}\right)^{20}. \end{eqnarray*}$$

3. ¸íáò Üíèñùðïò îåêéíÜ áðü ôï $0$ ôçò ðñáãìáôéêÞò åõèåßáò êáé ìåôÜ áðü êÜèå äåõôåñüëåðôï ðçäÜåé êáôÜ Ýíá ìÝôñï äåîéÜ Þ áñéóôåñÜ ìå ôçí ßäéá ðéèáíüôçôá $1/2$. ¸óôù $S_n$ ç èÝóç ðïõ âñßóêåôáé ìåôÜ áðü $n$ äåõôåñüëåðôá. Âñåßôå ôç ìÝóç ôéìÞ ôïõ $S_n^4$.

Ëýóç: ÃñÜöïõìå $X_i = +1$ áí ôï $i$-ïóôü ðÞäçìá åßíáé ðñïò ôá äåîéÜ êáé $-1$ áí åßíáé ðñïò ôá áñéóôåñÜ. ¸ôóé $S_n = X_1+\cdots+X_n$ êáé

$$S_n^4 = (X_1+\cdots+X_n)^4 = \sum_{i,j,k,l=1}^n X_i X_j X_k X_l.$$

Ðáßñíïíôáò ìÝóç ôéìÞ Ý÷ïõìå

$${\bf E}\left[S_n^4\right] = \sum_{i,j,k,l=1}^n {\bf E}\left[X_i X_j X_k X_l\right].$$

ÄåîéÜ Ý÷ïõìå üëá ôá äõíáôÜ ãéíüìåíá ðïõ ìðïñïýí íá öôéá÷ôïýí áðü 4 áðü ôá $X_1,\ldots,X_n$ (åðáíáëÞøåéò åðéôñÝðïíôáé).

Áò åðéêåíôñùèïýìå óôçí ðïóüôçôá ${\bf E}\left[X_i X_j X_k X_l\right]$. Ðáñáôçñïýìå êáôáñ÷Þí üôé ${\bf E}\left[X_r\right] = 0$ ãéá êÜèå $r$. Áí ôþñá êÜðïéïò áðü ôïõò äåßêôåò $i, j, k, l$ åìöáíßæåôáé ìüíï ìéá öïñÜ óôçí ôåôñÜäá ôüôå ç Üíù ìÝóç ôéìÞ âãáßíåé 0. Ãéá ðáñÜäåéãìá

$${\bf E}\left[X_1 X_1 X_2 X_5\right] = {\bf E}\left[X_1^2\rig... ...}\left[X_2\right] {\bf E}\left[X_5\right] = 1\cdot0\cdot0 = 0.$$

Ôï óõìðÝñáóìá åßíáé üôé ïé ìüíïé üñïé ðïõ ìÝíïõí óôï $\sum_{i,j,k,l=1}^n {\bf E}\left[X_i X_j X_k X_l\right]$ åßíáé áõôïß ðïõ Ý÷ïõí ôÝóóåñåéò ßäéïõò äåßêôåò êáé áõôïß ðïõ Ý÷ïõí äýï äéáöïñåôéêïýò äåßêôåò áðü äõü öïñÝò ôïí êáèÝíá. Êáé óôéò äýï ðåñéðôþóåéò ôï ${\bf E}\left[X_i X_j X_k X_l\right]$ åßíáé ßóï ìå 1.

Ðüóïé åßíáé áõôïß ïé åðéæþíôåò üñïé; ÕðÜñ÷ïõí áêñéâþò $n$ üñïé ðïõ Ý÷ïõí üëïõò ôïõò äåßêôåò ßäéïõò êáé ${n \choose 2}{4 \choose 2} = 3n(n-1)$ üñïé üðïõ åìöáíßæïíôáé äýï ìüíï äéáöïñåôéêïß äåßêôåò áðü äõü öïñÝò ï êáèÝíáò. Áõôü ôï ôåëåõôáßï ôï âëÝðïõìå ùò åîÞò: åðéëÝãïõìå ðñþôá ôï ðïéïé èá åßíáé áõôïß ïé äýï äéáöïñåôéêïß äåßêôåò êáé ìåôÜ äéáëÝãïõìå óå ðïéåò äýï áðü ôéò 4 èÝóåéò ôçò ôåôñÜäáò èá ìðåß ï ìåãáëýôåñïò áðü ôïõò äýï äåßêôåò.

¶ñá

$${\bf E}\left[S_n^4\right] = \sum_{i,j,k,l=1}^n {\bf E}\left[X_i X_j X_k X_l\right] = n + 3n(n-1) = 3n^2 -2n.$$

4. Ñß÷íïõìå ðïëëÝò öïñÝò Ýíá íüìéóìá ðïõ öÝñíåé êïñþíá ìå ðéèáíüôçôá $p$. Ðüóåò öïñÝò ðñÝðåé íá ôï ñßîïõìå þóôå ìå ðéèáíüôçôá ôïõëÜ÷éóôïí 95% ç ðáñáôçñïýìåíç óõ÷íüôçôá åìöÜíéóçò êïñþíáò íá äéáöÝñåé áðü ôï $p$ êáôÜ ôï ðïëý ${1\over 10}p$; (×ñçóéìïðïéåßóôå ôçí áíéóüôçôá ôïõ Chebyshev.)

Ëýóç: ÃñÜöïõìå $X_i = 1$ áí ç $i$-ïóôÞ ñßøç öÝñåé êïñþíá (ðéèáíüôçôá $p$) êáé 0 áëëéþò. Ç ðáñáôçñïýìåíç óõ÷íüôçôá êïñþíáò óôéò $n$ ñßøåéò åßíáé ç ðïóüôçôá

$$F = {1\over n}(X_1+\cdots+X_n).$$

¸÷ïõìå ${\bf E}\left[F\right] = p$ êáé

$$\sigma^2 = {\bf Var}{F} = {1\over n^2} n {\bf Var}{X_1} = {1\over n} p(1-p).$$

Åöáñìüæïõìå ôçí áíéóüôçôá ôïõ Chebyshev óôçí $F$ êáé ðáßñíïõìå

$$\begin{eqnarray*} {{\bf {Pr}}\left[{{\left\vert{F-p}\right\vert} > {p\over 10}}\... ... &\le& {100 \sigma^2 \over p^2}\\ &=& {100 (1-p) \over p n}. \end{eqnarray*}$$

ÁõôÞ ç ôåëåõôáßá ðïóüôçôá èÝëïõìå íá åßíáé $\le 5/100$ êáé ëýíïíôáò ôçí áíéóüôçôá ðáßñíïõìå $n > 2000{1-p \over p}$.

Äéåõêñßíéóç-Äéüñèùóç: ÊáôÜ ôç äéÜñêåéá ôçò åîÝôáóçò óáò åß÷á ðåé íá âñåßôå êÜôù öñÜãìá ãéá ôï $n$ ðïõ íá åßíáé áíåîÜñôçôï ôïõ $p$. ¼ðùò öáßíåôáé êé áðü ôï áðïôÝêëåóìá ðïõ âãÜëáìå ôÝôïéï öñÜãìá äåí õðÜñ÷åé ìéá êáé ãéá $p\to 0$ ôï êÜôù öñÜãìá ðïõ âãÜëáìå ðÜåé óôï $\infty$.

5. Óå Ýíá êïõôß âñßóêïíôáé 100 Üóðñåò, 50 ìáýñåò êáé 50 êüêêéíåò ìðÜëëåò. ÅðéëÝãïõìå ÷ùñßò åðáíÜèåóç 50 áðü áõôÝò êáé ïíïìÜæïõìå $X$ êáé $Y$ ôïí áñéèìü ôùí Üóðñùí êáé ôùí ìáýñùí ìðáëëþí óôï äåßãìá. Íá âñåèåß ç ìÝóç ôéìÞ ôçò ìåôáâëçôÞò $(X-Y)^2$.

Ëýóç: ÃñÜöïõìå $X=X_1+\cdots+X_{50}$ êáé $Y=Y_1+\cdots+Y_{50}$, üðïõ $X_i = 1$ áí ôñáâÞîïõìå Üóðñç óôçí $i$-ïóôÞ ëÞøç êáé 0 áëëéþò êáé $Y_i = 1$ áí ôñáâÞîïõìå ìáýñç êáé 0 áëëéþò.

¸÷ïõìå ${\bf E}\left[(X-Y)^2\right] = {\bf E}\left[X^2\right] + {\bf E}\left[Y^2\right] - 2{\bf E}\left[XY\right]$. Õðïëïãßæïõìå ðñþôá ôï ${\bf E}\left[X^2\right]$:

$$\begin{eqnarray*} {\bf E}\left[X^2\right] &=& {\bf E}\left[(X_1+\cdots X_{50})^2... ... {1\over 2} + 2 {50 \choose 2}{1\over 2}{99/199}\\ &=& 634.42. \end{eqnarray*}$$

Ïìïßùò ãéá ôï ${\bf E}\left[Y^2\right]$:

$$\begin{eqnarray*} {\bf E}\left[Y^2\right] &=& {\bf E}\left[(Y_1+\cdots Y_{50})^2... ...er 4} + 2 {50 \choose 2}{1\over 4}{49 \over 199}\\ &=& 163.31. \end{eqnarray*}$$

ÔÝëïò õðïëïãßæïõìå ôï ${\bf E}\left[XY\right]$:

$$\begin{eqnarray*} {\bf E}\left[XY\right] &=& {\bf E}\left[(X_1+\cdots+X_{50}) (Y... ...left[X_iY_i\right] + \sum_{i\neq j} {\bf E}\left[X_i Y_j\right]. \end{eqnarray*}$$

Åßíáé öáíåñü üôé ${\bf E}\left[X_iY_i\right] = {{\bf {Pr}}\left[{X_iY_i=1}\right]} = {{\bf {Pr}}\left[{X_i = Y_i = 1}\right]} = 0$. ÌÝíåé ëïéðüí ï õðïëïãéóìüò ôïõ ${\bf E}\left[X_i Y_j\right]$ ãéá $i \neq j$.

$${\bf E}\left[X_iY_j\right] = {{\bf {Pr}}\left[{X_iY_j=1}\rig... ...}\left[{X_i=1}\right]} = ={50 \over 199}{1 \over 2} = 0.1256.$$

ÓõëëÝãïíôáò ôïõò õðïëïãéóìïýò ìáò ðáßñíïõìå

$${\bf E}\left[(X-Y)^2\right] = 634.42 + 163.31 - 50\cdot49\cdot0.1256 = 490.01.$$

ÇñÜêëåéï, 6 Íïåìâñßïõ 2001