---
title: "東京大学大学院　情報理工入試過去問（数学）解答・２０１７年　第三問"
tags: u-tokyo, exam
---

# 東京大学大学院　情報理工入試過去問（数学）<br><span style="float: right;">―解答・２０１７年　第三問</span>

<style>
.markdown-body h1 > span:last-child{
font-size: 18pt;
float: right;
width: 100%;
text-align: right;
border-bottom: 1pt #EEE solid;
padding-bottom: 5pt;
margin-bottom: 5pt
}

.markdown-body h1{
border: none;
}

.markdown-body h2{
padding-top: 8px;
padding-left: 5px;
color: black;
background-color: #F2D7D9;
z-index: 1;
}

.markdown-body h3{
padding: 5px 0 5px 5px;
background-color: #D3CEDF
}

.markdown-body h4{
position: relative;
line-height: 28pt;
padding-left: 5px;
color: #FFFFFF;
font-size: 13pt;
background-color: #9CB4CC;
}

.markdown-body strong{
color: #555555;
letter-spacing: 0.5px;
text-transform: uppercase;
position: relative;
z-index: 0;
}

.markdown-body strong:after{
content: "";
position: absolute;
left: 10%;
bottom: 0;
height: 45%;
width: 90%;
background-color: #F2D7D9;
z-index: -1;
}

.markdown-body .alert-info{
background-color: #748DA6;
border: none;
box-shadow: 4px 4px 3px #9CB4CC;
color: #FFFFFF;
}

.markdown-body .mjx-sub{
font-size: 65% !important;
}

/* Pallete #F2D7D9 #D3CEDF #9CB4CC #748DA6 */
</style>

<!-- Probability & Statistics Related -->
$$
\newcommand{\prob}[1]{\mathrm{P}(#1)}
\newcommand{\probsub}[2]{\mathrm{P}_{#1}(#2)}
\newcommand{\func}[2]{\mathrm{#1}(#2)}
\newcommand{\funcsub}[3]{\mathrm{#1}_{#2}(#3)}
\newcommand{\excp}[1]{\mathrm{E}(#1)}
\newcommand{\cdf}[1]{\mathrm{F}(#1)}
$$

<!-- Linear Algebra Related -->
$$
\require{boldsymbol}
\newcommand{\vec}[1]{\boldsymbol{#1}}
\newcommand{\bmat}[1]{\begin{bmatrix} #1 \end{bmatrix}}
\newcommand{\rank}[1]{\mathrm{rank}(#1)}
\newcommand{\norm}[1]{\| #1 \|}
\newcommand{\trps}[1]{#1^{\moveleft{1.5px}{\raise{2px}{\mathrm{T}}}}}
\newcommand{\inv}[1]{#1^{-1}}
$$

<!-- General Macros -->
$$
\newcommand{\intinf}{\displaystyle\int^{\infty}_{-\infty}}
\newcommand{\intlo}[1]{\displaystyle\int^{#1}_{-\infty}}
\newcommand{\inthi}[1]{\displaystyle\int^{\infty}_{#1}}
\newcommand{\nobj}[3]{#1_1{\;#3\;} #1_2{\;#3} \;\ldots\; {#3\;} #1_#2}
\newcommand{\nobjsfx}[4]{#1_1#3{\;#4\;} #1_2#3{\;#4} \;\ldots\; {#4\;} #1_#2#3}
$$

+ こちらの解答は非公式で個人記録用に作成されており、大学院側に認められたものではありません。正確性についての保証は致しかねます。
+ 問題本文は研究科のウェブサイトから見ることができます。
+ 満足出来た解答でしたらコメントしていただけると幸いです。

## ２０１７年　第三問
### (1) Find the mean and the CDF ($F(t)$) of the **Exponential Distribution:** $$f(t) = \begin{cases}\lambda e^{-\lambda t} &, t \geq 0\\0 &, t < 0\end{cases}$$
The mean of the probability distribution is:
$$
\mu = \intinf tf(t)dt = \int^{\infty}_{0} t\lambda e^{-\lambda t}dt = \left.\displaystyle\frac{-\lambda t - 1}{\lambda}e^{-\lambda t}\right\vert^{t = \infty}_{t = 0} = \frac{1}{\lambda}
$$

The CDF of the probabiilty distribution is:
$$
\cdf{t} = \intlo{t}f(t)dt = \int^{t}_{0} \lambda e^{-\lambda t}dt = \left. -e^{-\lambda t} \right\vert^{t = t}_{t = 0} = 1 - e^{-\lambda t}
$$

### (2) Prove that $f(t)$ has no memory, a.k.a., for arbritrary $s > 0, t > 0$, $$\prob{T > s + t \mid T > s} = \prob{T > t} $$

+ **LHS:** Since $\prob{A \mid B} = \displaystyle\frac{\prob{A \cap B}}{\prob{B}}$,
$$
\begin{align}
\prob{T > s + t \mid T > s} &= \frac{\prob{(T > s + t) \cap (T > s)}}{\prob{T > s}}
= \frac{\prob{T > s + t}}{\prob{T > s}}
= \frac{1 - \prob{T \leq s + t}}{1 - \prob{T \leq s}} \\[1ex]
&= \frac{1 - \displaystyle\int^{s + t}_{0} \lambda e^(-\lambda t) dt}{1 - \displaystyle\int^{s}_{0} \lambda e^(-\lambda t) dt}
= \frac{1 - \left. (-e^{-\lambda t}) \right\vert^{t = s+t}_{t = 0}}{1 - \left. (-e^{-\lambda t}) \right\vert^{t = s}_{t = 0}}\\[1ex]
&= \frac{e^{-\lambda(s + t)}}{e^{-\lambda s}}
= e^{-\lambda(s + t - s)} = e^{-\lambda t}
\end{align}
$$

+ **RHS:**
$$
\prob{T > t} = 1 - \prob{T \leq t} = 1 - \displaystyle\int^{t}_{0} \lambda e^{-\lambda t} dt = 1 - \left. (-e^{-\lambda t}) \right\vert^{t = t}_{t = 0} = e^{-\lambda t}
$$

Since the two side is same, we can conclude that the distribution has no memory.

### (3) Let there be $n$ student doing a test. Under the following conditions,<br> find the mean and the probability distribution of the minimum finish time.
:::info
+ All students' finish time is under exponential distribution with parameter $\lambda_0$
+ All $n$ students' finish time are independent
:::
Let $\nobj{X}{n}{,}$ be the random varibales of finish time for each student, and $Y$ be the random variable of the finish time for the fastest student, then:
$$
\begin{align}
\cdf{y} = \prob{Y \leq y} &= \prob{\min(\nobj{X}{n}{,}) \leq y} \\[1ex]
&= 1 - \prob{\nobjsfx{(X}{n}{ > y)}{\cap}}
\end{align}
$$

Since all $X_i$ are independent, it further becomes:
$$
\begin{align}
\cdf{y} &= 1 - \prob{X_1 > y} \cdot \prob{X_2 > y} \cdot \ldots \cdot \prob{X_n > y} \\[1ex]
&= 1 - \Big[ 1 - \prob{X \leq y} \Big]^n \\[1ex]
&= 1 - \Big[ 1 - \cdf{X} \Big]^n = 1 - \Big[ 1 - (1 - e^{-\lambda_0 t}) \Big]^n \\[1ex]
&= 1 - e^{-\lambda_0 nt}
\end{align}
$$

Since for some CDF $\cdf{a}$, the $f(a) = \frac{d\cdf{a}}{da}$, the distribution function $f(y) = \prob{Y = y}$ is:
$$
f(y) = \displaystyle\frac{d(1 - e^{-\lambda_0 ny})}{dy} = \lambda_0 ne^{-\lambda_{\scriptscriptstyle{0}} ny}
$$

And so the mean of $f(y)$ is:
$$
\mu = \inthi{0} \lambda_0nye^{-\lambda_0 ny} dy = \left. \left(\frac{-\lambda_0 ny - 1}{\lambda_0 n}e^{-\lambda_0 ny} \right) \right\vert^{y = \infty}_{y = 0} = 0 + \frac{1}{\lambda_0 n} = \frac{1}{\lambda_0 n}
$$

### (4) Let there be student $A$, $B$ doing a test. Under the following conditions, <br>find the probability that student $A$ finished the test first.
:::info
+ The finish time of student $A$ is under exponential distribution $f_A(t)$ with parameter $\lambda_a$
+ The finish time of student $B$ is under exponential distribution $f_B(t)$ with parameter $\lambda_b$
+ The finish time of student $A$ and $B$ are independent.
:::
Since $A$, $B$ are independent, the joint distribution function $f_{AB}(a, b) = f_A(a)f_B(b).$

To calculate $\prob{A < B}$, simply integrate the joint distribution function over the region $a < b$:
$$
\begin{align}
\displaystyle \int^{\infty}_{0} \int^{b}_{0} f_{AB}(a, b) dadb &= \int^{\infty}_{0} \int^{b}_{0} \lambda_ae^{-\lambda_a a}\lambda_be^{-\lambda_b b} dadb \\[1ex]
&= \int^{\infty}_0 \lambda_be^{-\lambda_bb}\left. (-e^{-\lambda_aa}) \right\vert^{a = b}_{a = 0} db \\[1ex]
&= \int^{\infty}_0 \lambda_be^{-\lambda_bb}\left( 1 - e^{-\lambda_ab} \right) db \\[1ex]
&= \int^{\infty}_0 \lambda_be^{-\lambda_bb} db - \int^{\infty}_0 \lambda_be^{-(\lambda_a + \lambda_b)b} db \\[1ex]
&= \left. -e^{-\lambda_bb} \right\vert^{b = \infty}_{b = 0} - \left. \displaystyle \frac{\lambda_b}{-(\lambda_a + \lambda_b)} e^{-(\lambda_a + \lambda_b)b} \right\vert^{b = \infty}_{b = 0} \\[1ex]
&= 1 - \left( \displaystyle\frac{\lambda_b}{\lambda_a + \lambda_b} \right) = \frac{\lambda_a}{\lambda_a + \lambda_b}
\end{align}
$$

### (5) Let there be a student $Y$, and other $10$ students $\nobj{X}{{10}}{, }$ doing a test, whose finish time all having exponential distribution. The mean finish time of $Y$ ($\mu_Y$) is $10$ times shorter than all other students.
#### Find the probability of student $Y$ finishing first.
We know that $10\mu_Y = \mu_{X_1} = \mu_{X_2} = \ldots = \mu_{X_{10}}$, so we can say:
$$
\mu_Y = c \\
\mu_{X_1} = \mu_{X_2} = \ldots = \mu_{X_{10}} = 10c
$$
For some positive $c$.

From (1), we know the mean of a distribution is $\frac{1}{\lambda}$, inducing the density function of $Y$, $X_i$ respectivly are:
$$
f_Y(y) = \begin{cases}
\displaystyle \frac{e^{-\frac{y}{10c}}}{10c} &, y \geq 0 \\
0 &, y < 0
\end{cases} \;\;\;\;\;\;\;\;\;\;
f_{X_i}(x_i) = \begin{cases}
\displaystyle \frac{e^{-\frac{x_i}{c}}}{c} &, x_i \geq 0 \\
0 &, x_i < 0
\end{cases}
$$

Where $x_i, y$ are the finish times.

Finishing as first means $\forall i \in [1 .. 10] : y < x_i$, and all $\prob{Y < X_i}$ are independent. Thus using (4), the probability of student $Y$ finishing first is:
$$
\begin{align}
\prob{\text{Student } Y \text{ is the first}} &= \prob{\min(Y, \nobj{X}{{10}}{, }) = y} \\[1ex]
&= \prob{Y < X_1} \cap \prob{Y < X_2} \cap \ldots \cap \prob{Y < X_{10}} \\[1ex]
&= \left( \displaystyle\frac{\frac{1}{c}}{\frac{1}{c} + \frac{1}{10c}} \right)^{10} = \left( \frac{10}{11} \right)^{10}
\end{align}
$$

#### Find the probability of student $Y$ fininshing fourth.
Student $Y$ finishing fourth, meaning student $Y$ beated $7$ out of $10$ ordinary students and failed to do so $3$ times — since each *competetions* are independent, this is the boission distribution $b(x; n, p)$ where
+ The number of success trails $x = 7$
+ The total number of trials $n = 10$
+ The success rate $p = \frac{10}{11}$.

Thus the probability of student $Y$ finished fourth is:
$$
b(x; n, p) = \binom{10}{7}\left( \frac{10}{11} \right)^7\left( \frac{1}{11} \right)^3 = \frac{10 \times 9 \times 8}{3 \times 2 \times 1} \cdot \frac{10^7}{11^7} \cdot \frac{1}{11^3} = \frac{12 \times 10^8}{11^{10}} \approx 0.04625
$$