Difficulty in understanding "Find $E[N]$ , where $N=\min\{n>0: X_n=X_0\}$"

Question

It is Question 30 on page 168 in Ross's book (Introduction to Probability Models-11th edition)

Let $X_i, i\ge 0$ be independent and identically distributed random variables with probability mass function

$p(j)=P(X_i=j), j=1,\ldots,m, \sum_{j=1}^m P(j) = 1$

Find $E[N]$, where $N=\min\{n>0: X_n = X_0\}$

The same question was here, but I don't have enough credit to comment on. Find $E[N]$, where $N = \min\{n>0: X_n = X_0\}$

Here are my questions:

1. What is the sample space for it? Can anyone give me a simple example? or any references?

2. What does $X_n = X_0$ mean for 2 random variables with the same distribution?

3. Is it possible to resolve it with conditional probability?

4. Are there any applications of such a question? What is the point behind the question?

Any help would be greatly appreciated.

Update 1: The Solution says:

E[N] = $\sum_{j=1}^m$ E[N|Xo = j] * p(j) = $\sum_{j=1}^m (1/p(j)) * p(j) = m$

I am totally confused, so I want to confirm a few things.

1. $N=\min\{n>0: X_n = X_0\}$: Is this the least index of indices of Xi that are equal to X0 (having the same j with X0)?

Answer 1

Using nothing but definitions we get

\begin{align} \mathbb E(N) &=\sum_{n\geq 1}\,n\cdot\mathbb P(N=n)\\ &=\sum_{n\geq 1}\,n\cdot\mathbb P(\min\{k\in\mathbb N\,:\,X_k=X_0\}=n)\\ &=\mathbb P\left(X_1=X_0\right)+\sum_{n\geq 2}\,n\cdot \mathbb P\left(\Big(X_n=X_0\Big)\cap\left(\bigcap_{k=1}^{n-1}\Big(X_k\neq X_0\Big)\right)\right) \end{align}

Now, we may use the law of total probability to calculate each of the terms above. We'll have

\begin{align} \mathbb P\left(X_1=X_0\right) =&\sum_{j\geq1}\,\mathbb P\left(X_1=j\,|\,X_0=j\right)\cdot\mathbb P\left(X_0=j\right)\\ \stackrel{\text{indep.}}{=}&\sum_{j\geq1}\,\mathbb P\left(X_1=j\right)\cdot\mathbb P\left(X_0=j\right)\\ \stackrel{\text{iid}}{=}&\sum_{j\geq1}\,{\mathbb P\left(X_0=j\right)}^2 \tag{1} \end{align}

Similarly:

\begin{align} \mathbb P\left(\Big(X_n=X_0\Big)\cap\left(\bigcap_{k=1}^{n-1}\Big(X_k\neq X_0\Big)\right)\right)& \\ =\sum_{j\geq1}\,\mathbb P\left(\Big(X_n=j\Big)\cap\left(\bigcap_{k=1}^{n-1}\Big(X_k\neq j\Big)\right)\,\middle|\,X_0=j\right)\cdot\mathbb P\left(X_0=j\right)&\\ \stackrel{\text{indep. and iid}}{=}\,\sum_{j\geq1}\,{\mathbb P\left(X_0=j\right)}^2\cdot{\mathbb P\left(X_0\neq j\right)}^{n-1}&& \tag{2} \end{align}

So we can see that the formula in $(2)$ also applies to $(1)$, with $n=1$. Hence:

$$\mathbb E(N) =\sum_{n\geq 1}\,n\cdot \left(\sum_{j\geq1}\,{\mathbb P\left(X_0=j\right)}^2\cdot{\mathbb P\left(X_0\neq j\right)}^{n-1}\right) \tag{3}$$

For our particular case, $(3)$ reduces to

$$\mathbb E(N) =\sum_{n\geq1}\,n\cdot \left(\sum_{j=1}^m\,p(j)\,^2\cdot{\big(1-p(j)\big)}^{n-1}\right) $$

We can then change summation order to obtain

$$\mathbb E(N) =\sum_{j=1}^m\,p(j)\,^2\cdot \underbrace{\left(\sum_{n\geq1}\,n\cdot{\big(1-p(j)\big)}^{n-1}\right)}_{(*)} $$

To calculate $(*)$, consider the identitiy

$$\sum_{n\geq 0}x^n=\frac1{1-x},$$

which holds whenver $|x|<1$. Differentiate both sides to obtain

$$\sum_{n\geq 1}nx^{n-1}=\frac1{(1-x)^2}.$$

We can apply the identity above to $(*)$ with $x=1-p(j) \iff 1- x = p(j)$, yielding

$$\mathbb E(N) =\sum_{j=1}^m\,p(j)\,^2\cdot \frac{1}{p(j)\,^2} =\sum_{j=1}^m\,1=m $$

as the solution claims.

Answer 2

$N=min\{n>0 | X_n=X_0\}$ means that $N$ is a random variable whose value is the minimum of the set $\{n>0 | X_n=X_0\}$.

Imagine an experience where you first make a draw, say X_0, and then keep drawing $X_i$, one after another, until you get a draw similar to $X_0$ again and then you stop. The number of draws you made is equal to $N$ as defined earlier.

The sample space for it is $\Bbb N^*$ (even though it is impossible in terms of probabilities, you could keep drawing an infinite number of times without getting $X_0$)

What you're looking for is the expected number of draws you made until you got $X_0$ again (a draw identical to the first one).

It follows that $(N|X_0=x_o)$ follows has a Geometric distribution of parameter $p(x_0)$. The expectation for that is $E[N|X_0] = \frac1{p(x_0)}$. Now given (and that's the formula used in Ross's book) $E[N] = E[E[N|X_0]] = \sum_{x_0=1}^m p(x_0)*\frac1{p(x_0)} = m$ Intuitively it makes sense. Among m objects, you have to make m draws on average to get the one you were looking for.

Answer 3

First of all, notice $X_i, i > 0$, are uncountable.

then

$E[N]$ = $\sum_{i=0}^m E[N|X_0=i] * P(X_0 = i)$

for $E[N|X_0 = i]$

= $\sum_{n=0} P(N > n)$ # N is independent of $X_0$

= $\sum_{n=0} [ \prod_{k=1}^n P(X_k != X_0)] $ # here P(N > n) follows a geometric distribution.

= $1$ + $(1-pi)$ + $(1-pi)^2$ + ... +$(1-pi)^n$

= $1/p_i$

finally $E[N]$

= $\sum_{i=0}^m (1/p_i) * P(X_0 = i)$

= $\sum_{i=0}^m (1/p_i) * p_i $

= $m$

Answer 4

Thank you @Fimpellizieri for your answer. I was thinking to explain Solution in simple words.

Assume the 0th variable $X_0=j$, what means its probability is $p(j)$. Now the question is: at what $n$ is the next occurrence of $j$? If $X_n=j$ that means $X_1 \neq j, X_2 \neq j, ..., X_{n-1} \neq j$. What is clearly a Geometric distribution, so $P(X_n=j)=(1-p(j))^{n-1}p(j)$. In case of Geometric distribution, we know $E[N]=\frac{1}{p(j)}$. The value of a random variable $X_0$ depends on its probability $P\{X_0=j\}=p(j)$, that is why we condition on $X_0=j$: $$ E[N]=E\left[E[N|X_0=j]\right]=E\left[\frac{1}{p(j)}\right]=\sum^m_{j=1}\frac{1}{p(j)}p(j)=m$$