# How do you show a sequence of random variable are not independent or identically distributed?

Consider the i.i.d (independent identically distributed) sequence $X_1,X_2,X_3,..$ of random variables such that $X_i \in {1,2,3,...}$ and for all $i$ $P(X_n=i) = p_i > 0$

Let $Y_n = 1$ with probability 1. For $n >= 2$ let $Y_n = 1$ if the value of $X_n$ has not been observed previously; and $Y_n=0$ otherwise.

Are variables $Y_1, Y_2, Y_3,..$ independent? Are they identically distributed ?

The answer to both of these questions is apparently no (not independent nor identically distributed), and I'm wondering why. This can be shown via a counter-example (all you need is one), but I'm still unclear about this.

I would appreciate if somebody from the community could clearly explain why the Ys are not independent nor identically distributed.

• If I understand the setup, for $n \gt 1$ we have $Y_n=1$ if and only if $X_n$ is distinct from all previous $X_1,\ldots,X_{n-1}$. Clearly $Y_2$ is not identically distributed with $Y_1$ for discretely distributed $X_i$ since $Y_1$ is $1$ with probability $1$. Have you tried a simple binomial distribution for the $X_i$'s? – hardmath Oct 8 '14 at 15:05

Intuitively the chance of result $X_n$ differing from all previous $X_i$'s must decline as $n$ increases. The first $X_1$ is of a certainty distinct, but the chance that the second $X_2$ will differ from $X_1$ is strictly less than $1$:

$$\text{Pr}(X_2 \neq X_1) = 1 - \text{Pr}(X_2 = X_1)= 1 - \sum_{i=1}^\infty p_i^2$$

In terms of the $Y_n$'s this means the chance that $Y_2 = 1$ is less than the chance that $Y_0=1$:

$$\text{Pr}(Y_2=1) = \text{Pr}(X_2 \neq X_1) \lt 1 = \text{Pr}(Y_1=1)$$

Clearly the $Y_n$'s are not identically distributed, and a similar calculation shows $\text{Pr}(Y_n = 1)$ is strictly decreasing as $n \to \infty$.

Consider now the independence of $Y_n$'s. If $Y_2$ and $Y_3$ were independently distributed, then $\text{Pr}(Y_3=1)$ would equal $\text{Pr}(Y_3=1| Y_2=0)$. But if $Y_2=0$, it means $X_2=X_1$. Therefore:

$$\text{Pr}(Y_3=1|Y_2=0) = \text{Pr}(Y_2=1) \gt \text{Pr}(Y_3=1)$$

since when $X_2=X_1$, $X_3$ has only to differ from that single value to make $Y_3=1$.