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.

  • $\begingroup$ 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? $\endgroup$
    – hardmath
    Oct 8, 2014 at 15:05

1 Answer 1


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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.