Stat 110 Strategic Practice 4, Fall 2011

1. Distributions and Expected Values for Discrete Random Variables

Problem 1
Find an example of two discrete random variables $X$ and $Y$ (on the same sample space) such that $X$ and $Y$ have the same distribution (i.e., same PMF and same CDF), but the event $X = Y$ never occurs.

Sol
$X \sim \text{Bernoulli}(1/2)$라 하고 $Y = 1-X$라고 하자. 그러면 $Y$ 또한 $\text{Bernoulli}(1/2)$를 따르지만, $Y = 1-X$이므로 $X=Y$는 불가능하다.

이를 일반화한 예로 $X \sim \text{Binomial}(n,1/2)$라 하고 $Y=n-X$라고 하자. 여기서 $X$는 $n$번의 동전 던지기에서 성공한 횟수이고, $Y$는 실패한 횟수이다.

$X$가 $k$번 성공할 확률은 $P(X=k)=\binom{n}{k}(1/2)^n$이고, $Y=n-X$이므로 $Y$가 $k$가 될 확률은 $P(Y=k)=P(X=n-k)=\binom{n}{n-k}(1/2)^n$이다.

그런데 $\binom{n}{n-k}=\binom{n}{k}$이므로 $P(Y=k)=P(X=k)$가 성립한다. 따라서 $X$와 $Y$는 동일한 $\text{Binomial}(n,1/2)$ 분포를 따른다.

하지만 $Y=n-X$이므로 $X=Y$가 되려면 $X=n/2$여야 한다. 따라서 $n$을 홀수로 가정하면 $n/2$가 정수가 아니므로 $X=Y$는 불가능하다.

즉, $X$와 $Y$는 동일한 분포를 가지지만 서로 같은 확률변수는 아니다.

Problem 2
Let $X$ be a random day of the week, coded so that Monday is $1$, Tuesday is $2$, etc. (so $X$ takes values $1, 2, ..., 7$, with equal probabilities).

Let $Y$ be the next day after $X$ (again represented as an integer between $1$ and $7$). Do $X$ and $Y$ have the same distribution? What is $P(X < Y)$?

Sol
X는 1~7까지 가능하다. 따라서 1~7까지 각각 $\frac17$확률을 가지게 된다. $Y = (X \pmod 7) + 1$이므로 X와 분포가 같다.

$Y$가 $X$보다 작은 경우는 $Y = 1, X = 7$인 경우 밖에 없다. 따라서 $P(X<Y) = \frac67$이다.

Problem 3
A coin is tossed repeatedly until it lands Heads for the first time. Let $X$ be the number of tosses that are required (including the toss that landed Heads), and let $p$ be the probability of Heads. Find the CDF of $X$, and for $p = 1/2$ sketch its graph.

Sol
앞면이 나올 확률이 $p$이고, $X$를 앞면이 처음 나온 순간까지의 필요한 동전 던지기 횟수라면 다음과 같다.

따라서 $X$의 CDF는 다음과 같다

그래프는 discrete random varialbe이므로 step function이다.

Problem 4
Are there discrete random variables $X$ and $Y$ such that $E(X) > 100E(Y)$ but $Y$ is greater than $X$ with probability at least $0.99?

Sol
$X$는 1%로 $10^6$이고, 99%로 0이라고 하자. $Y$는 항상 1이라고 가정하자.

따라서 기댓값은 $X$가 더 크지만, $P(Y>X) = 0.99$이다.

Problem 5
Let $X$ be a discrete r.v. with possible values $1,2,3,\ldots$. Let $F(x)=P(X\le x)$ be the CDF of $X$. Show that $E(X)=\sum_{n=0}^{\infty}(1-F(n))$.

Hint: organize the order of summation carefully, using the fact that, for example, $P(X>3)=P(X=4)+P(X=5)+\cdots$.

Sol
$1-F(n)$은 $P(X>n)$과 같다. 따라서 $1-F(0) = P(X = 1) + P(X = 2) + \cdots$, $1-F(1) = P(X = 2) + P(X = 3) + \cdots$, $\cdots$이다.

따라서 각 $k$에 대하여 $P(X = k)$은 정확히 $k$번 나타난다.

따라서 $\sum_{n=0}^{\infty} (1 - F(n)) = \sum_{k=1}^{\infty} k P(X = k) = E[X]$이다.

Problem 6
Job candidates $C_1,C_2,\ldots$ are interviewed one by one, and the interviewer compares them and keeps an updated list of rankings (if $n$ candidates have been interviewed so far, this is a list of the $n$ candidates, from best to worst). Assume that there is no limit on the number of candidates available, that for any $n$ the candidates $C_1,C_2,\ldots,C_n$ are equally likely to arrive in any order, and that there are no ties in the rankings given by the interview.

Let $X$ be the index of the first candidate to come along who ranks as better than the very first candidate $C\_1$ (so $C\_X$ is better than $C\_1$, but the candidates after 1 but prior to $X$ (if any) are worse than $C\_1$. For example, if $C\_2$ and $C\_3$ are worse than $C\_1$ but $C\_4$ is better than $C\_1$, then $X = 4$. All $4!$ orderings of the first 4 candidates are equally likely, so it could have happened that the first candidate was the best out of the first 4 candidates, in which case $X \> 4$.

What is $E(X)$ (which is a measure of how long, on average, the interviewer needs to wait to find someone better than the very first candidate)? Hint: find $P(X \> n)$ by interpreting what $X \> n$ says about how $C\_1$ compares with other candidates, and then apply the result of the previous problem.

Sol
$X$를 첫 번째 후보자 $C_1$보다 더 좋은 후보자가 처음으로 등장하는 후보자의 번호라고 하자.

$X>n$이라는 것은 $C_2,\ldots,C_n$ 중에서 $C_1$보다 좋은 후보자가 없다는 뜻이다. 따라서 $X>n$이라는 사건은 $C_1$이 처음 $n$명의 후보자 중에서 가장 높은 순위를 갖는 사건과 같다.

처음 $n$명의 후보자 중에서 가장 높은 순위를 갖는 후보자는 $C_1,\ldots,C_n$ 중 누구든 될 수 있고, 모든 후보자가 가장 높은 순위를 가질 확률은 동일하다. 따라서 $n\ge2$일 때 $P(X>n)=\frac{1}{n}$이다.

한편 $X$는 첫 번째 후보자보다 더 좋은 후보자가 처음 등장하는 번호이므로 항상 $X\ge2$이다. 따라서 $P(X>0)=P(X>1)=1$이다.

이제 지시 확률변수를 이용하여 $X$를 나타내면 $X=I(X>0)+I(X>1)+I(X>2)+\cdots$이다. 실제로 $X=4$라면 $I(X>0),I(X>1),I(X>2),I(X>3)$은 모두 1이고, 그 이후의 지시 확률변수는 모두 0이므로 그 합은 4가 된다.

따라서 양변의 기댓값을 취하면 $E(X)=\sum_{n=0}^{\infty}E[I(X>n)]$이다. 지시 확률변수의 성질에 의해 $E[I(X>n)]=P(X>n)$이므로 $E(X)=\sum_{n=0}^{\infty}P(X>n)$을 얻는다.

앞에서 구한 $P(X>n)$을 대입하면 $E(X)=1+\sum_{n=1}^{\infty}\frac{1}{n}$이다.

그런데 $\sum_{n=1}^{\infty}\frac{1}{n}=1+\frac12+\frac13+\frac14+\cdots$는 조화급수이고 발산한다. 따라서 $E(X)=\infty$이다.

즉, $X$는 각각의 경우에는 항상 유한한 값을 가지지만, 후보자의 수에 제한이 없는 이론적인 상황에서는 $X$의 기댓값이 무한대가 된다.

핵심은 $P(X=n)$을 직접 구하지 않고 $X>n$을 해석하는 것이다. $X>n$이면 $C_1$이 처음 $n$명 중 가장 좋은 후보자이므로 $P(X>n)=\frac1n$을 쉽게 구할 수 있다. 그다음 지시 확률변수를 이용하면 이 꼬리확률들을 모두 더해서 $E(X)$를 구할 수 있다.

---

2. Indicator Random Variables and Linearity of Expectation

Problem 1
A group of 50 people are comparing their birthdays (as usual, assume their birthdays are independent, are not February 29, etc.). Find the expected number of pairs of people with the same birthday, and the expected number of days in the year on which at least two of these people were born.

Sol
50명의 사람들이 있다고 하자. 먼저 각 사람의 쌍에 대해 지시확률변수를 하나씩 만들자. 즉, 사람 $i$와 사람 $j$의 생일이 같으면 지시확률변수 $I_{ij}$가 1의 값을 갖고, 생일이 다르면 0의 값을 갖도록 한다. 그러면 같은 생일을 가진 사람의 쌍의 총 개수는 이러한 지시확률변수들의 합으로 표현할 수 있다. 두 사람의 생일이 같을 확률은 $\frac{1}{365}$이므로 각 지시확률변수의 기댓값은 $\frac{1}{365}$이다. 가능한 사람의 쌍은 $\binom{50}{2}$개이므로 기댓값의 선형성에 의해 같은 생일을 가진 사람의 쌍의 기대 개수는 $\binom{50}{2}\frac{1}{365}$가 된다.

이번에는 사람의 쌍이 아니라 1년의 각 날짜에 대해 지시확률변수를 하나씩 만들자. 특정 날짜에 대해 그 날짜에 태어난 사람이 적어도 2명이면 지시확률변수가 1의 값을 갖고, 그렇지 않으면 0의 값을 갖도록 한다. 그러면 적어도 2명의 사람이 태어난 날짜의 총 개수는 365개의 지시확률변수의 합으로 표현할 수 있다.

특정 날짜에 적어도 2명이 태어날 확률을 직접 계산하는 대신, 그 반대인 0명 또는 1명이 태어날 확률을 계산하자. 50명 모두가 특정 날짜가 아닌 다른 날짜에 태어날 확률은 $\left(\frac{364}{365}\right)^{50}$이다. 또한 정확히 1명만 그 날짜에 태어날 확률은 50명 중 누가 그 날짜에 태어날지를 고르는 방법이 50가지이고, 그 한 명이 해당 날짜에 태어날 확률이 $\frac{1}{365}$이며, 나머지 49명이 다른 날짜에 태어날 확률이 $\left(\frac{364}{365}\right)^{49}$이므로 $50\cdot\frac{1}{365}\left(\frac{364}{365}\right)^{49}$이다.

따라서 특정 날짜에 적어도 2명이 태어날 확률은 $1-\left(\frac{364}{365}\right)^{50}-50\cdot\frac{1}{365}\left(\frac{364}{365}\right)^{49}$이다. 365개의 날짜 각각에 대해 동일한 방식으로 지시확률변수를 정의했으므로, 기댓값의 선형성에 의해 적어도 2명의 사람이 태어난 날짜의 기대 개수는 $365\left(1-\left(\frac{364}{365}\right)^{50}-50\cdot\frac{1}{365}\left(\frac{364}{365}\right)^{49}\right)$가 된다.

Problem 2
A total of 20 bags of Haribo gummi bears are randomly distributed to the 20 students in a certain Stat 110 section. Each bag is obtained by a random student, and the outcomes of who gets which bag are independent. Find the average number of bags of gummi bears that the first three students get in total, and find the average number of students who get at least one bag.

Sol
각 학생이 받는 젤리 봉지의 개수를 먼저 생각해보자. $X_j$를 $j$번째 학생이 받는 젤리 봉지의 개수라고 하자. 20개의 봉지가 각각 독립적으로 20명의 학생 중 한 명에게 무작위로 주어지므로, 특정 봉지가 $j$번째 학생에게 갈 확률은 $\frac{1}{20}$이다. 따라서 $X_j$는 20번의 독립적인 시행에서 성공 확률이 $\frac{1}{20}$인 성공 횟수이므로 $X_j\sim\operatorname{Bin}(20,\frac{1}{20})$이다. 따라서 $E[X_j]=20\cdot\frac{1}{20}=1$이다.

우리가 알고 싶은 것은 첫 번째 세 학생이 받는 봉지의 총 개수이므로 $X_1+X_2+X_3$의 기댓값을 구하면 된다. 기댓값의 선형성에 의해 $E[X_1+X_2+X_3]=E[X_1]+E[X_2]+E[X_3]=1+1+1=3$이다. 여기서 $X_1,X_2,X_3$가 서로 독립인지 여부는 중요하지 않다. 기댓값의 선형성은 독립성을 필요로 하지 않기 때문이다.

이번에는 적어도 하나의 봉지를 받은 학생의 평균적인 수를 구해보자. 각 학생 $j$에 대해 $I_j$를 정의하여, $j$번째 학생이 적어도 하나의 봉지를 받으면 $I_j=1$, 그렇지 않으면 $I_j=0$이 되도록 하자. 그러면 적어도 하나의 봉지를 받은 학생의 총 개수는 $I_1+\cdots+I_{20}$으로 표현할 수 있다.

따라서 기댓값의 선형성에 의해 평균적인 학생의 수는 $E[I_1+\cdots+I_{20}]=20E[I_1]$이다. 지시확률변수이므로 $E[I_1]=P(I_1=1)$이고, $I_1=1$이라는 것은 첫 번째 학생이 적어도 하나의 봉지를 받았다는 뜻이다.

첫 번째 학생이 적어도 하나의 봉지를 받는 사건을 직접 계산하는 대신, 그 반대인 첫 번째 학생이 봉지를 하나도 받지 못하는 경우를 생각하자. 각각의 봉지가 첫 번째 학생에게 가지 않을 확률은 $\frac{19}{20}$이고, 20개의 봉지가 독립적으로 배정되므로 20개의 봉지가 모두 첫 번째 학생에게 가지 않을 확률은 $\left(\frac{19}{20}\right)^{20}$이다. 따라서 첫 번째 학생이 적어도 하나의 봉지를 받을 확률은 $1-\left(\frac{19}{20}\right)^{20}$이다.

결국 적어도 하나의 봉지를 받은 학생의 평균적인 수는 $20E[I_1]=20P(I_1=1)=20\left(1-\left(\frac{19}{20}\right)^{20}\right)$이 된다.

Problem 3
There are 100 shoelaces in a box. At each stage, you pick two random ends and tie them together. Either this results in a longer shoelace (if the two ends came from different pieces), or it results in a loop (if the two ends came from the same piece). What are the expected number of steps until everything is in loops, and the expected number of loops after everything is in loops? (This is a famous interview problem; leave the latter answer as a sum.)

Hint: for each step, create an indicator r.v. for whether a loop was created then, and note that the number of free ends goes down by 2 after each step.

Sol
처음에는 신발끈이 100개이고 각각 양 끝을 가지므로 자유로운 끝은 총 $200$개이다. 매 단계마다 자유로운 끝 2개를 골라 서로 묶기 때문에, 두 개의 서로 다른 조각이 연결되거나 같은 조각의 두 끝이 연결되어 새로운 loop가 만들어진다. 따라서 어느 경우든 자유로운 끝의 개수는 2개씩 감소한다. $k$번의 단계를 거친 후 자유로운 끝의 개수는 $200-2k$개이므로, 모든 것이 loop가 되려면 $200-2k=0$이어야 한다. 따라서 $k=100$이고, 항상 정확히 100번의 단계가 필요하다.

이제 최종적으로 만들어지는 loop의 개수를 생각하자. $I_j$를 $j$번째 단계에서 새로운 loop가 만들어졌는지를 나타내는 지시변수라고 하자. 즉, $I_j=1$이면 $j$번째 단계에서 loop가 만들어지고, $I_j=0$이면 그렇지 않다. 최종 loop의 개수를 $L$이라고 하면 각 단계에서 loop가 만들어졌는지를 모두 더하면 되므로 $L=I_1+I_2+\cdots+I_{100}$이다.

이제 $n$개의 조각이 아직 loop가 되지 않은 상태라고 하자. 각 조각에는 자유로운 끝이 2개씩 있으므로 자유로운 끝은 총 $2n$개이다. 이때 자유로운 끝 2개를 무작위로 선택하므로 가능한 선택의 수는 $\binom{2n}{2}$이다. 새로운 loop가 만들어지려면 같은 조각에 속한 두 끝을 선택해야 한다. $n$개의 조각 각각에 대해 자신의 두 끝을 선택하는 경우가 하나씩 있으므로 loop가 만들어지는 경우의 수는 $n$이다. 따라서 새로운 loop가 만들어질 확률은 $P(\text{loop})=\frac{n}{\binom{2n}{2}}=\frac{n}{n(2n-1)}=\frac{1}{2n-1}$이다.

기대값의 선형성에 의해 $E[L]=E[I_1]+\cdots+E[I_{100}]$이고, 지시변수의 기대값은 $E[I_j]=P(I_j=1)$이므로 각 단계에서 loop가 만들어질 확률을 모두 더하면 최종 loop의 기대 개수를 구할 수 있다. $n$은 처음의 100에서 마지막의 1까지 감소하므로 $E[L]=\sum_{n=1}^{100}\frac{1}{2n-1}$이다. 따라서 필요한 단계의 수는 $\boxed{100}$이고, 모든 것이 loop가 된 후의 loop의 기대 개수는 $\boxed{\displaystyle\sum_{n=1}^{100}\frac{1}{2n-1}}$이다.

Problem 4
A hash table is a commonly used data structure in computer science, allowing for fast information retrieval. For example, suppose we want to store some people’s phone numbers. Assume that no two of the people have the same name. For each name $x$, a hash function $h$ is used, where $h(x)$ is the location to store $x$’s phone number. After such a table has been computed, to look up $x$’s phone number one just recomputes $h(x)$ and then looks up what is stored in that location.

The hash function $h$ is deterministic, since we don’t want to get different results every time we compute $h(x)$. But $h$ is often chosen to be pseudorandom. For this problem, assume that true randomness is used. So let there be $k$ people, with each person’s phone number stored in a random location (independently), represented by an integer between $1$ and $n$. It then might happen that one location has more than one phone number stored there, if two different people $x$ and $y$ end up with the same random location for their information to be stored.

Find the expected number of locations with no phone numbers stored, the expected number with exactly one phone number, and the expected number with more than one phone number (should these quantities add up to $n$?).

Sol
$j$번째 위치가 비어 있는지를 나타내는 지시변수 $I_j$를 정의하자. 즉, $I_j=1$이면 $j$번째 위치가 비어 있고, $I_j=0$이면 그렇지 않다고 하자. 여기서 $1\le j\le n$이다. 특정 위치 $j$가 비어 있으려면 $k$명의 사람이 모두 그 위치를 선택하지 않아야 한다. 한 사람이 $j$번째 위치를 선택하지 않을 확률은 $1-\frac1n$이고, 각 사람의 위치 선택은 서로 독립이므로 $P(I_j=1)=\left(1-\frac1n\right)^k$이다.

한편 $I_1+\cdots+I_n$은 비어 있는 위치의 총 개수를 나타낸다. 따라서 기대값의 선형성에 의해 $E\left[\sum_{j=1}^n I_j\right]=\sum_{j=1}^nE[I_j]$이고, $E[I_j]=P(I_j=1)$이므로 $E\left[\sum_{j=1}^n I_j\right]=n\left(1-\frac1n\right)^k$이다. 따라서 기대되는 빈 위치의 개수는 $n\left(1-\frac1n\right)^k$이다.

이제 특정 위치에 정확히 하나의 전화번호가 저장될 확률을 생각하자. 정확히 한 명의 사람이 그 위치를 선택해야 하므로, $k$명 중 그 위치를 선택할 사람을 고르는 방법은 $\binom{k}{1}=k$가지이다. 선택된 한 사람이 그 위치를 선택할 확률은 $\frac1n$이고, 나머지 $k-1$명이 그 위치를 선택하지 않을 확률은 $\left(1-\frac1n\right)^{k-1}$이다. 따라서 특정 위치에 정확히 하나의 전화번호가 저장될 확률은 $\frac{k}{n}\left(1-\frac1n\right)^{k-1}$이다. 위치가 총 $n$개이므로 기대되는 위치의 개수는 $n\cdot\frac{k}{n}\left(1-\frac1n\right)^{k-1}=k\left(1-\frac1n\right)^{k-1}$이다.

마지막으로 각 위치는 비어 있거나, 정확히 하나의 전화번호가 있거나, 두 개 이상의 전화번호가 있는 경우 중 정확히 하나에 해당한다. 따라서 세 종류의 위치의 개수를 더하면 항상 $n$이고, 기대값의 선형성에 의해 세 기대값을 더해도 $n$이 된다. 따라서 두 개 이상의 전화번호가 저장된 위치의 기대 개수는 $n-n\left(1-\frac1n\right)^k-k\left(1-\frac1n\right)^{k-1}$이다.

따라서 각각의 기대값은 $n\left(1-\frac1n\right)^k$, $k\left(1-\frac1n\right)^{k-1}$, $n-n\left(1-\frac1n\right)^k-k\left(1-\frac1n\right)^{k-1}$이고, 이 세 값을 더하면 정확히 $n$이 된다.