0
$\begingroup$

A group of three friends has n books they would all like to read. Each friend (independently of the other two) picks a random permutation of the books and reads them in that order, one book per week (for $n$ consecutive weeks). Let $X$ be the number of weeks in which all three friends are reading the same book. Compute $Var(X)$.

So, I first approached the problem by defining the indicator random variable $X_i$.

$X = X_1+X_2+...X_n$

where $X_i = 1$ if all $3$ friends are reading the same book, and $X_i=0$ otherwise.

$E[X_i] = 1\times Pr[X_i=1]$

$Pr[X_i=1] =$ the probability that all three friends are reading the same book

I thought that since there are $n!$ permutations of the book, $Pr[X_i=1]=\frac{1}{(n!)^3}$ but I was wrong. This is what the book says:

$E[X_i] = Pr[X_i=1] = (\frac{1}{n})^2$

I'm trying to understand where this quantity came from. I know that I can rewrite it as $\frac{1}{n} \times \frac{1}{n}$ but why are there only two? What happened to the notion of permutations?

There's another part of this question, I'm confused about which I will try to figure out on my own after this is answered, but I might update this post with a followup.

EDIT: The book goes on to say the following

$Pr[X_i=X_j=1] = Pr[X_i = 1 \cap X_j = 1] = \frac{1}{(n(n-1))^2}$

I know that this is the probability of all three friends reading the same book on two different weeks. Assuming they don't repeat books, I get where the $n$ and $n-1$ are coming from, but I'm having trouble breaking down the given expression.

$\endgroup$
1
  • $\begingroup$ On week $i$, the first friend is reading some book. The second person has $1/n$ chance of reading the same book, and the third person has $1/n$ chance of reading the same book. $\endgroup$
    – angryavian
    May 29, 2017 at 4:47

1 Answer 1

Reset to default
1
$\begingroup$

If it is not immediately intuitive to you, then using the tedious approach:

Let $A_{(i,k)},B_{(i,k)},C_{(i,k)}$ (with $1\leq k\leq n$ and $1\leq i\leq n$) each represent the events that person $A$, person $B$ and person $C$ respectively are reading book $k$ on day $i$.

Then note that $Pr(X_i=1)=Pr(\bigcup\limits_{k=1}^n\left[A_{(i,k)}\cap B_{(i,k)}\cap C_{(i,k)}\right]) = \sum\limits_{k=1}^nPr(A_{(i,k)}\cap B_{(i,k)}\cap C_{(i,k)})$

$=n\cdot Pr(A_{(1,1)}\cap B_{(1,1)}\cap C_{(1,1)}) = n\cdot Pr(A_{(1,1)})\cdot Pr(B_{(1,1)})\cdot Pr(B_{(1,1)})$

$=n\cdot \frac{1}{n}\cdot \frac{1}{n}\cdot \frac{1}{n}=\frac{1}{n^2}$

For more detail as to why $Pr(A_{(1,1)})=\frac{1}{n}$, note that there are $(n-1)!$ arrangements where the first day the person is reading the first book out of the $n!$ total arrangements, giving $Pr(A_{(1,1)})=\frac{(n-1)!}{n!}=\frac{1}{n}$

The shorter explanation is via conditional probability: given whatever $A$'s choice of book is for day $i$, $B$'s choice on that day is equally likely to be any of the available books and so his chance of matching $A$'s choice is $\frac{1}{n}$. Similarly for $C$, giving the probability $Pr(X_i=1)=Pr(B~\text{matches}~ A)\times Pr(C~\text{matches}~A)=\frac{1}{n^2}$

$\endgroup$
3
  • $\begingroup$ Thank you that is very clear. I edited my original post with a followup given my new understanding $\endgroup$
    – Carpetfizz
    May 29, 2017 at 5:01
  • $\begingroup$ @Carpetfizz the explanation will be nearly identical, if perhaps a bit tedious to write out completely using the rigorous argument. The conditional probability argument is that person $B$ must first match $A$ for week $i$, and given that that happened further match $A$ for week $j$ and similarly for $C$, and then note that given that $B$ already matches $A$ in week $i$ the probability that $B$ matches $A$ in week $j$ will be $\frac{1}{n-1}$. $\endgroup$
    – JMoravitz
    May 29, 2017 at 5:04
  • $\begingroup$ We get then $Pr(X_i=X_j=1)=Pr($B matches A first and second time and C matches A first and second time$)=Pr($B matches A first time$)\cdot Pr($B matches A second time$\mid$ B matches A first time$)\times\dots = \frac{1}{n}\times\frac{1}{n-1}\times\frac{1}{n}\times\frac{1}{n-1}$ $\endgroup$
    – JMoravitz
    May 29, 2017 at 5:07

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .