Probability and Mathematic Stastics Homework #1

Author： Bi_Gu
发布时间：September 14, 2022
1168 views
No comments
8940 words
Categories：概率论与数理统计

<button class="btn m-b-xs btn-light btn-roundedbtn-addon" onclick='window.open("https://cdn.dabigu.xyz/97096454_p0.jpg","_blank")'><i class="fa fa-camera"></i>$\quad$ **明日方舟 终末地 Endfield by RIVER** </button>

# SI140 Probability and Mathematic Statistics

## Homework 1

### Problem 1

(**Story Proof**) Define $\begin{Bmatrix}n\\k\end{Bmatrix}$ as the number of ways to partition $\{1,2,\cdots,n\}$ into $k$ non-empty subsets, or the number of ways to have $n$ students spilt up into $k$ groups such that each group has at least one student.

Prove the following identities:

**(a)**

$$
\begin{Bmatrix}n+1\\k\end{Bmatrix}=\begin{Bmatrix}n\\k-1\end{Bmatrix}+k\cdot\begin{Bmatrix}n\\k\end{Bmatrix}
$$

Suppose that there are $n+1$ people, and one of them is named *Alice*.  Now we want to divide them into $k$ groups.

One method is to do it directly, and we have $\begin{Bmatrix}n+1\\k\end{Bmatrix}$ possible ways to do so.

Or we can also focus on the opinion of *Alice* first. If she is afraid of social interaction and wants to be in a group by herself, then we only need to divide the rest $n$ people into $k-1$ groups, which has $\begin{Bmatrix}n\\k-1\end{Bmatrix}$ ways; Otherwise, the rest $n$ people are divided normally as $k$ groups, and *Alice* has $k$ ways to choose one of the groups to join. In total we have $\begin{Bmatrix}n\\k-1\end{Bmatrix}+k\cdot\begin{Bmatrix}n\\k\end{Bmatrix}$ ways.

The two methods achieve the same result, so the number of ways should be the same, which means that

$$
\begin{Bmatrix}n+1\\k\end{Bmatrix}=\begin{Bmatrix}n\\k-1\end{Bmatrix}+k\cdot\begin{Bmatrix}n\\k\end{Bmatrix}.
$$

**The proof is complete.**

**(b)**

$$
\sum_{j=k}^n\begin{pmatrix}n\\j\end{pmatrix}\cdot\begin{Bmatrix}j\\k\end{Bmatrix}=\begin{Bmatrix}n+1\\k+1\end{Bmatrix}
$$

Suppose that there are $n+1$ people, and one of them is named *Alice*; Now we want to divide them into $k+1$ groups.

One method is to do it directly, and we have $\begin{Bmatrix}n+1\\k+1\end{Bmatrix}$ possible ways to do so.

However, since *Alice* is the class monitor, actually she can choose her teammates, $\mathrm{i.e.}$ decide how many people are going to be in her group. Suppose the number of people **not** in *Alice's* group to be $j$. Since that there has to be at least one person in each group, we have $k\leq j\leq n$.

For each $j$, we pick out the $j$ people not in *Alice's* group first, at a count of $\begin{pmatrix}n\\j\end{pmatrix}$ ways;

Then divide them into $k$ groups (the rest have been picked by *Alice* thus in the ${(n+1)}^{\text{th}}$ group already). Thus in total we have $\sum_{j=k}^n\begin{pmatrix}n\\j\end{pmatrix}\cdot\begin{Bmatrix}j\\k\end{Bmatrix}$ ways;

The two methods achieve the same result, so the number of ways should be the same, which means that

$$
\sum_{j=k}^n\begin{pmatrix}n\\j\end{pmatrix}\cdot\begin{Bmatrix}j\\k\end{Bmatrix}=\begin{Bmatrix}n+1\\k+1\end{Bmatrix}
$$

**The proof is complete.**

### Problem 2

A *norepeatword* is a sequence of at least one (and possibly all) of the usual 26 letters a, b, c, . . . , z, with repetitions not allowed. For example, “course” is a norepeatword, but “statistics” is not. Order matters, e.g., “course” is not the same as “source”. A norepeatword is chosen randomly, with all norepeatwords equally likely. Show that the probability that it uses all 26 letters is very close to 1/$e$.

The number of $k$-letter *norepeatword* is a $k$-permutation since order matters and there is no replacement. We have to choose $k$ letters out of 26 letters first, whose number of ways is $\begin{pmatrix}n\\k\end{pmatrix}$.

Let sample space $S$ denote all possible *norepeatword* and event $A$ be those with 26 letters. Thus

$$
\begin{aligned}
P(A)&=\frac{26!}{\sum_{i=1}^{26}\begin{pmatrix}26\\i\end{pmatrix}\cdot i!}=
\frac{26!}{\sum_{i=1}^{26}\displaystyle\frac{26!}{i!(26-i)!}\cdot i!}
\\&=\frac{26!}{\displaystyle\frac{26!}{0!}+\frac{26!}{1!}+\cdots+\frac{26!}{25!}}
\\&=\frac{1}{\displaystyle\frac{1}{0!}+\frac{1}{1!}+\cdots+\frac{1}{25!}}
\\&\approx\bigg(1+x+\frac{x^2}{2!}+\frac{x^3}{3!}+\cdots+\frac{x^{25}}{25!}+\cdots+o(x^n)\bigg|_{x=1}\bigg)^{-1}
\\&=\frac{1}{e^x}\bigg|_{x=1}
\\&=\frac{1}{e}
\end{aligned}
$$

**The proof is complete.**

### Problem 3

Given $n\geq 2$ numbers $a_1,a_2,\cdots,a_n$ with no repetitions, a bootstrap sample is a sequence $x_1,x_2,\cdots,x_n$ formed from the $a_j$'s by sampling with replacement with equal probabilities. Bootstrap samples arise in a widely used statistical method known as the bootstrap. For example, if $n=2$ and $(a_1,a_2)=(3,1)$, then the possible bootstrap samples are $(3,3),(3,1),(1,3)$ and $(1,1)$.

**(a)** How many possible bootstrap samples are there for $(a_1,a_2,\cdots,a_n)$?

For any $x_i$ with $i=1,2,\cdots,n$, it has $n$ possible choices, $\mathrm{i.e.}$ $a_1,a_2,\cdots,a_n$.

Therefore there are $n^n$ possible bootstrap samples.

**(b)** How many bootstrap samples are there for $(a_1,a_2,\cdots,a_n)$, if order does not matter (in the sense that it only matters how many times each $a_j$ was chosen, not the order in which they were chosen)?

Suppose that among $x_i$, $a_i$ is chosen $b_i$ times for $i=1,2,\cdots,n$. Since that the order does not matter, the number of such possible bootstrap samples is exactly the same as the number of **nonnegative** solutions to the equation

$$
b_1+b_2+\cdots+b_n=n
$$

From the **Theorem** for Bose-Einstein Counting we have that number to be $\begin{pmatrix}2n-1\\n-1\end{pmatrix}$.

**(c)** One random bootstrap sample is chosen (by sampling from $a_1,a_2,\cdots,a_n$ with replacement, as described above). Show that not all unordered bootstrap samples (in the sense of (b)) are equally likely. Find an unordered bootstrap sample $\textbf{b}_1$ that is as likely as possible, and an unordered bootstrap sample $\textbf{b}_2$ that is as unlikely as possible. Let $p_1$ be the probability of getting $\textbf{b}_1$ and $p_2$ be the probability of getting $\textbf{b}_2$ (so $p_i$ is the probability of getting the specific unordered bootstrap sample $\textbf{b}_i$). What is $p_1/p_2$? What is the ratio of the probability of getting an unordered bootstrap sample whose probability is $p_1$ to the probability of getting an unordered sample whose probability is $p_2$?

Not all unordered bootstrap samples are equally likely, as more **repeatition** of a certain $a_i$ lead to less probability;

The **most** likely sample $\textbf{b}_1=(a_1,a_2,a_3,\cdots,a_n)$ has the least repetition as every element is different, and the **least** likely sample $\textbf{b}_2=(a_1,a_1,a_1,\cdots,a_1)$ has the most repetition as every element is the same.

We have

$$
\begin{cases}
	p_1=\displaystyle\frac{n!}{n^n}\\p_2=\displaystyle\frac{1}{n^n}\end{cases}\Rightarrow\frac{p_1}{p_2}=n!
$$

For those samples whose probability is $p_1$, it is an $n$-permutation as every $a_i$ is chosen exactly once; And for those samples whose probability is $p_2$, there are $n$ choices
$(a_1,a_1,\cdots,a_1),(a_2,a_2,\cdots,a_2),\cdots,(a_n,a_n,\cdots,a_n).$ So that we have

$$
\frac{P(\text{getting an unordered bootstrap sample whose probability is }p_1)}{P(\text{getting an unordered bootstrap sample whose probability is }p_2)}
	=\frac{n!}{n}=(n-1)!\ .
$$

#### Problem 4

**(Geometric Probability)** You get a stick and break it randomly into three pieces. What is the probability that you can make a triangle using such three pieces?

Since that the length of the stick is trivial in such problem, assume the length to be 1; Thus assume the length of three pieces to be $x,y,1-x-y$. In order for them to form a triangle, none of their length should surpass $\displaystyle\frac{1}{2}$ otherwise it would be longer than the sum of the rest two; Therefore we have

$$
\text{Sample Space }S=\left\{\begin{array}{l}0\leq x,y\leq 1\\0\leq x+y\leq 1\end{array}\right.\quad
\text{Event(Triangle Exists) }A=\left\{\begin{array}{l}0\leq x,y\leq\displaystyle\frac{1}{2}\\\displaystyle\frac{1}{2}
\leq x+y\leq 1\end{array}\right.
$$

From the graph above we have

$$
P(A)=\frac{S_A}{S_S}=\frac{\displaystyle\frac{1}{2}\times\frac{1}{2}\times\frac{1}{2}}{\displaystyle 1\times1\times\frac{1}{2}}=\frac{1}{4}.
$$

### Problem 5

In the birthday problem, we assumed that all 365 days of the year are equally likely (and excluded February 29). In reality, some days are slightly more likely as birthdays than others. For example, scientists have long struggled to understand why more babies are born 9 months after a holiday. Let $\textbf{p}=(p_1,p_2,\cdots,p_365)$ be the vector of birthday probabilities, with $p_j$ the probability of being born on the $j$ th day of the year (February 29 is still excluded, with no offense intended to Leap Dayers). The $k$th elementary symmetric polynomial in the variables $x_1,\cdots,x_n$ is defined by

$$
e_k(x_1,\cdots,x_n)=\sum_{1\leq j_1< j_2<\cdots<j_k\leq n}x_{j_1}\cdots x_{j_k}.
$$

This just says to add up all of the $\begin{pmatrix}n\\k\end{pmatrix}$ terms we can get by choosing and multiplying $k$ of the variables. For example, $e_1(x_1,x_2,x_3)=x_1+x_2+x_3,e_2(x_1,x_2,x_3)=x_1x_2+x_1x_3+x_2x_3$,
and $e_3(x_1,x_2,x_3)=x_1x_2x_3$. Now let $k\geq2$ be the number of people.

**(a)** Find a simple expression for the probability that there is at least one birthday match, in terms of **p** and an elementary symmetric polynomial.

From the definition we know that $e_k(\textbf{p})$ is the number of ways of choosing $k$ different (birth)days out of 365 days. And there are $k!$ ways to assign those birthdays to $k$ people. Therefore, the probability that there is **no** birthday match is $k!\cdot e_k(\textbf{p})$;

So that the probability that there is at least one birthday match is

$$
1-k!\cdot e_k(\textbf{p}).
$$

**(b)** Explain intuitively why it makes sense that $P$(at least one birth match) is minimized when $p_j=\displaystyle \frac{1}{365}$ for all $j$, by considering simple and extreme cases.

In the simple case where $k=2$, we have

$$
\begin{aligned}
		P(\text{at least one birth match})&=1-2\cdot e_2(\textbf{p})=(p_1+p_2+\cdots+p_{365})^2-2\cdot e_2(\textbf{p})\\&=p_1^2+p_2^2+\cdots p_{365}^2\\&\geq 365
		\cdot\bigg(\frac{p_1+p_2+\cdots+p_{365}}{365}\bigg)^2=\frac{1}{365}
		\end{aligned}
$$

The minumum is taken $\mathrm{iff.}$ $p_1=p_2=\cdots=p_{365}$, $\mathrm{i.e.}$ $p_j=\displaystyle\frac{1}{365}$ for all $j$.

**The proof is complete.**

**(c)** The famous arithmetic mean-geometric mean inequality says that for $x,y\geq 0$

$$
\frac{x+y}{2}\geq\sqrt{xy}.
$$

This inequality follows from adding $4xy$ to both sides of $x^2-2xy+y^2=(x-y)^2\geq 0$. Define **r**=$(r_1,r_2,\cdots,r_{365})$ by $r_1=r_2=(p_1+p_2)/2,r_j=p_j$ for $3\leq j\leq 365$. Using the arithmetic mean-geometric mean bound and the fact, which you should verify, that

$$
e_k(x_1,\cdots,x_n)=x_1x_2e_{k-2}(x_3,\cdots,x_n)+(x_1+x_2)e_{k-1}(x_3,\cdots,x_n)+e_k(x_3,\cdots,x_n)
$$

show that

$$
P(\text{at least one birthday match}\mid\textbf{p})\geq P(\text{at least one birthday match}\mid\textbf{r})
$$

with strict inequality if $\textbf{p}\neq \textbf{r}$, where the given **r** notation means that the birthday probabilities are given by **r**. Using this, show that the value of **p** that minimizes the probability of at least one birthday match is given by $p_j=\displaystyle\frac{1}{365}$ for all $j$.

**Part A.** First we verify the fact that

$$
e_k(x_1,\cdots,x_n)=x_1x_2e_{k-2}(x_3,\cdots,x_n)+(x_1+x_2)e_{k-1}(x_3,\cdots,x_n)+e_k(x_3,\cdots,x_n)
$$

We can divide $e_k(x_1,\cdots,x_n)$ into four partitions: (1) Both $x_1,x_2$ attend the calculation; (2) Only $x_1$ attend the calculation; (3) Only $x_2$ attend the calculation; (4) Neither of them attend the calculation.

Thus we have

$$
\begin{aligned}
			\text{Total }&=\text{ Part (1) }+\text{ Part (2) }+\text{ Part (3) }+\text{ Part (4) }\\
			e_k(x_1,\cdots,x_n)&=x_1x_2e_{k-2}(x_3,\cdots,x_n)+x_1\cdot e_{k-1}(x_3,\cdots,x_n)\\&+x_2\cdot e_{k-1}(x_3,\cdots,x_n)+e_k(x_3,\cdots,x_n)
		\\&=x_1x_2e_{k-2}(x_3,\cdots,x_n)+(x_1+x_2)e_{k-1}(x_3,\cdots,x_n)+e_k(x_3,\cdots,x_n)
		\end{aligned}
$$

**Part B.** Next we show that

$$
P(\text{at least one birthday match}\mid\textbf{p})\geq P(\text{at least one birthday match}\mid\textbf{r})
$$

$$
\begin{aligned}
				&\quad P(\text{at least one birthday match}\mid\textbf{p})\\&=1-k!\cdot e_k(\textbf{p})
				\\&=1-k!\cdot\big(p_1p_2e_{k-2}(p_3,\cdots,p_n)+(p_1+p_2)e_{k-1}(p_3,\cdots,p_n)+e_k(p_3,\cdots,p_n)\big)
				\\&\geq 1-k!\cdot\bigg(\displaystyle\frac{(p_1+p_2)^2}{4}\cdot e_{k-2}(p_3,\cdots,p_n)\\&+(p_1+p_2)e_{k-1}(p_3,\cdots,p_n)+e_k(p_3,\cdots,p_n)\bigg)
				\\&=1-k!\cdot\big(r_1r_2e_{k-2}(r_3,\cdots,r_n)+(r_1+r_2)e_{k-1}(r_3,\cdots,r_n)+e_k(r_3,\cdots,r_n)\big)
				\\&=1-k!\cdot e_k(\textbf{r})
				\\&=P(\text{at least one birthday match}\mid\textbf{r})
			\end{aligned}
$$

**Part C.**

Finally we prove that the value of **p** that minimizes the probability of at least one birthday match is given by $p_j=\displaystyle\frac{1}{365}$ for all $j$.

Suppose that there exists some vector $\textbf{p}'$ that minimizes the probability of at least one birthday match other than **p**, where $\textbf{p}=(\displaystyle \frac{1}{365},\frac{1}{365},\cdots,\frac{1}{365})$ and $\exists i\neq j\in[1,365]~\mathrm{s.t.}~p_i\neq p_j\in\textbf{p}'$.

Then since that $p_i p_j>\displaystyle\frac{(p_i+p_j)^2}{4}$ for $p_i\neq p_j$,

define $\textbf{r}'$=$(r_1,r_2,\cdots,r_365)$ by $r_i=r_j=(p_i+p_j)/2,r_k=p_k$ for the rest of $k$ in $[1,365]$.

Then using the same method in **Part A** and **B**we have that

$$
P(\text{at least one birthday match}\mid\textbf{p}')\geq P(\text{at least one birthday match}\mid\textbf{r}')
$$

So that $\textbf{r}'$ should be the minimization vector instead of $\textbf{p}'$, which leads to the contradiction.

Thus the probability is minimized $\mathrm{iff.}$ $p_j=\displaystyle\frac{1}{365}$ for all $j$.

**The proof is complete.**

### Problem 6

(**Coupon Collection**) If each box of a brand of crispy instant noodle contains a coupon, and there are 108 different types of coupons. Given $n\geq 200$, what is the probability that buying $n$ boxes can collect all 108 types of coupons? You also need to plot a figure to show how such probability changes with the increasing value of $n$. When such probability is no less than 95\%, what is the minimum number of $n$?

Collecting all 108 types of coupons in $n$ boxes is equivalent to dividing $n$ coupons into 108 nonempty parts where the order of parts **does not matter**;

So that the probability of achieving this is

$$
P=\frac{\begin{Bmatrix}n\\108\end{Bmatrix}\cdot 108!}{108^n}=\sum_{i=0}^{108}(-1)^i\cdot\begin{pmatrix}108\\k\end{pmatrix}\cdot
	\bigg(\frac{108-i}{108}\bigg)^n
$$

where $n$ takes a minimum number of 823 when $P\geq 0.95$.

Last modification：February 18, 2023

Support if you like my work! qwq

版权声明：若文中无特殊说明，则本文为原创文章，版权归 Bi_Gu 所有。

本文链接：https://dabigu.xyz/index.php/archives/616/

所有原创文章采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可。
您可以自由的转载和修改，但请务必注明文章来源并且不可用于商业目的。

猜你想看 Probability and Mathematic Stastics Lecture #2 Conditional Probability Probability and Mathematic Stastics Lecture #1 Probability and Counting

随机文章 Signals and Systems Chapter 0 Discrete Mathematics Homework #9 LaTeX格式渲染问题

Probability and Mathematic Stastics Homework #1

Bi_Gu • 2022 年 09 月 14 日

# SI140 Probability and Mathematic Statistics

## Homework 1

### Problem 1

Prove the following identities:

**(a)**

$$
\begin{Bmatrix}n+1\\k\end{Bmatrix}=\begin{Bmatrix}n\\k-1\end{Bmatrix}+k\cdot\begin{Bmatrix}n\\k\end{Bmatrix}
$$

Suppose that there are $n+1$ people, and one of them is named *Alice*.  Now we want to divide them into $k$ groups.

One method is to do it directly, and we have $\begin{Bmatrix}n+1\\k\end{Bmatrix}$ possible ways to do so.

The two methods achieve the same result, so the number of ways should be the same, which means that

$$
\begin{Bmatrix}n+1\\k\end{Bmatrix}=\begin{Bmatrix}n\\k-1\end{Bmatrix}+k\cdot\begin{Bmatrix}n\\k\end{Bmatrix}.
$$

**The proof is complete.**

**(b)**

$$
\sum_{j=k}^n\begin{pmatrix}n\\j\end{pmatrix}\cdot\begin{Bmatrix}j\\k\end{Bmatrix}=\begin{Bmatrix}n+1\\k+1\end{Bmatrix}
$$

Suppose that there are $n+1$ people, and one of them is named *Alice*; Now we want to divide them into $k+1$ groups.

One method is to do it directly, and we have $\begin{Bmatrix}n+1\\k+1\end{Bmatrix}$ possible ways to do so.

For each $j$, we pick out the $j$ people not in *Alice's* group first, at a count of $\begin{pmatrix}n\\j\end{pmatrix}$ ways;

The two methods achieve the same result, so the number of ways should be the same, which means that

$$
\sum_{j=k}^n\begin{pmatrix}n\\j\end{pmatrix}\cdot\begin{Bmatrix}j\\k\end{Bmatrix}=\begin{Bmatrix}n+1\\k+1\end{Bmatrix}
$$

**The proof is complete.**

### Problem 2

Let sample space $S$ denote all possible *norepeatword* and event $A$ be those with 26 letters. Thus

**The proof is complete.**

### Problem 3

**(a)** How many possible bootstrap samples are there for $(a_1,a_2,\cdots,a_n)$?

For any $x_i$ with $i=1,2,\cdots,n$, it has $n$ possible choices, $\mathrm{i.e.}$ $a_1,a_2,\cdots,a_n$.

Therefore there are $n^n$ possible bootstrap samples.

$$
b_1+b_2+\cdots+b_n=n
$$

From the **Theorem** for Bose-Einstein Counting we have that number to be $\begin{pmatrix}2n-1\\n-1\end{pmatrix}$.

Not all unordered bootstrap samples are equally likely, as more **repeatition** of a certain $a_i$ lead to less probability;

We have

$$
\begin{cases}
	p_1=\displaystyle\frac{n!}{n^n}\\p_2=\displaystyle\frac{1}{n^n}\end{cases}\Rightarrow\frac{p_1}{p_2}=n!
$$

$$
\frac{P(\text{getting an unordered bootstrap sample whose probability is }p_1)}{P(\text{getting an unordered bootstrap sample whose probability is }p_2)}
	=\frac{n!}{n}=(n-1)!\ .
$$

#### Problem 4

**(Geometric Probability)** You get a stick and break it randomly into three pieces. What is the probability that you can make a triangle using such three pieces?

From the graph above we have

$$
P(A)=\frac{S_A}{S_S}=\frac{\displaystyle\frac{1}{2}\times\frac{1}{2}\times\frac{1}{2}}{\displaystyle 1\times1\times\frac{1}{2}}=\frac{1}{4}.
$$

### Problem 5

$$
e_k(x_1,\cdots,x_n)=\sum_{1\leq j_1< j_2<\cdots<j_k\leq n}x_{j_1}\cdots x_{j_k}.
$$

**(a)** Find a simple expression for the probability that there is at least one birthday match, in terms of **p** and an elementary symmetric polynomial.

So that the probability that there is at least one birthday match is

$$
1-k!\cdot e_k(\textbf{p}).
$$

**(b)** Explain intuitively why it makes sense that $P$(at least one birth match) is minimized when $p_j=\displaystyle \frac{1}{365}$ for all $j$, by considering simple and extreme cases.

In the simple case where $k=2$, we have

The minumum is taken $\mathrm{iff.}$ $p_1=p_2=\cdots=p_{365}$, $\mathrm{i.e.}$ $p_j=\displaystyle\frac{1}{365}$ for all $j$.

**The proof is complete.**

**(c)** The famous arithmetic mean-geometric mean inequality says that for $x,y\geq 0$

$$
\frac{x+y}{2}\geq\sqrt{xy}.
$$

$$
e_k(x_1,\cdots,x_n)=x_1x_2e_{k-2}(x_3,\cdots,x_n)+(x_1+x_2)e_{k-1}(x_3,\cdots,x_n)+e_k(x_3,\cdots,x_n)
$$

show that

$$
P(\text{at least one birthday match}\mid\textbf{p})\geq P(\text{at least one birthday match}\mid\textbf{r})
$$

**Part A.** First we verify the fact that

$$
e_k(x_1,\cdots,x_n)=x_1x_2e_{k-2}(x_3,\cdots,x_n)+(x_1+x_2)e_{k-1}(x_3,\cdots,x_n)+e_k(x_3,\cdots,x_n)
$$

Thus we have

**Part B.** Next we show that

$$
P(\text{at least one birthday match}\mid\textbf{p})\geq P(\text{at least one birthday match}\mid\textbf{r})
$$

**Part C.**

Finally we prove that the value of **p** that minimizes the probability of at least one birthday match is given by $p_j=\displaystyle\frac{1}{365}$ for all $j$.

Then since that $p_i p_j>\displaystyle\frac{(p_i+p_j)^2}{4}$ for $p_i\neq p_j$,

define $\textbf{r}'$=$(r_1,r_2,\cdots,r_365)$ by $r_i=r_j=(p_i+p_j)/2,r_k=p_k$ for the rest of $k$ in $[1,365]$.

Then using the same method in **Part A** and **B**we have that

$$
P(\text{at least one birthday match}\mid\textbf{p}')\geq P(\text{at least one birthday match}\mid\textbf{r}')
$$

So that $\textbf{r}'$ should be the minimization vector instead of $\textbf{p}'$, which leads to the contradiction.

Thus the probability is minimized $\mathrm{iff.}$ $p_j=\displaystyle\frac{1}{365}$ for all $j$.

**The proof is complete.**

### Problem 6

Collecting all 108 types of coupons in $n$ boxes is equivalent to dividing $n$ coupons into 108 nonempty parts where the order of parts **does not matter**;

So that the probability of achieving this is

$$
P=\frac{\begin{Bmatrix}n\\108\end{Bmatrix}\cdot 108!}{108^n}=\sum_{i=0}^{108}(-1)^i\cdot\begin{pmatrix}108\\k\end{pmatrix}\cdot
	\bigg(\frac{108-i}{108}\bigg)^n
$$

where $n$ takes a minimum number of 823 when $P\geq 0.95$.

Probability and Mathematic Stastics Homework #1

Leave a Comment Cancel reply

《Phigros》游戏记录

使用RD Client实现Windows远程桌面

基于opencv和pyautogui的腾讯会议自动入会

Probability and Mathematic Stastics Homework #1

Introduction to Machine Learning Homework #2

Maths Analysis II - Section 8.4

Maths Analysis II - Homework #20 20220510

CS101 Lecture#1 Introduction

Maths Analysis II - Homework #19 20220505

Maths Analysis II - Homework #14 20220407

Probability and Mathematic Stastics Homework #1