The paradox of i.i.d. data (at least for me) As far as my aggregate (and scarce) knowledge on statistics permits, I understood that if $X_1, X_2,..., X_n$ are i.i.d. random variables, then as the term implies they are independent and identically distributed. 
My concern here is the former property of i.i.d. samples, which reads:
$$p(X_{n}|X_{i_1},X_{i_2},...,X_{i_k}) = p(X_{n}),$$
for any collection of distinct $i_j$'s s.t. $1 \leq i_j < n$. 
However one knows that the aggregate of independent samples of identical distributions provide information about the distribution structure, and as a result about $X_n$ in the above case, so indeed it should not be the case that:
$$p(X_{n}|X_{i_1},X_{i_2},...,X_{i_k}) = p(X_{n}).$$
I know that I am victim of fallacy but I don't know why. Please help me out on this one. 
 A: I think you are confusing an estimated model of a distribution with a random variable. Let's rewrite the independence assumption as follows:
$$
P(X_n | \theta, X_{i_1}, X_{i_2}, \dots, X_{i_k}) = P(X_n | \theta) \tag{1}
$$
which says that if you know the underlying distribution of $X_n$ (and, for example, can identify it by a set of parameters $\theta$) then the distribution does not change given that you have observed a few samples from it. 
For example, think of $X_n$ as the random variable representing the outcome of the $n$-th toss of a coin. Knowing the probability of head and tail for the coin (which, btw, assume is encoded in $\theta$) is enough to know the distribution of $X_n$. In particular, the outcome of the previous tosses does not change the probability of head or tail for the $n$-th toss, and $(1)$ holds.
Note, however, that $P(\theta | X_n) \neq P(\theta | X_{i_1}, X_{i_2}, \dots, X_{i_k})$.
A: If you take a Bayesian approach and treat parameters describing the distribution of $X$ as a random variable/vector, then the observations indeed are not independent, but they would be conditionally independent given knowledge of $\theta$ hence $P(X_n \mid X_{n-1}, \ldots X_1, \theta) = P(X_n \mid \theta)$ would hold.
In a classical statistical approach, $\theta$ is not a random variable. Calculations are done as if we know what $\theta$ is. In some sense, you're always conditioning on $\theta$ (even if you don't know the value). 
When you wrote, "... provide information about the distribution structure, and as a result about $X_n$" you implicitly were adopting a Bayesian approach but not doing it precisely. You're writing a property of IID samples that a frequentist would write, but the corresponding statement in a Bayesian setup would involve conditioning on $\theta$.
Bayesian vs. Classical statisticians
Let $x_i$ be the result of flipping a lopsided, unfair coin. We don't know the probability the coin lands heads.


*

*To the classical statistician, the frequentist, $P(x_i = H)$ is some parameter, let's call it $\theta$. Observe that $\theta$ here is a scalar, like the number 1/3. We may not know what the number is, but it's some number! It is not random!

*To the Bayesian statistician, $\theta$ itself is a random variable! This is extremely different!


The key idea here is that the Bayesian statistician extends the tools of probability to situations where the classical statistician doesn't. To the frequentist, $\theta$ isn't a random variable because it only has one possible value! Multiple outcomes are not possible! In the Bayesian's imagination though, multiple values of $\theta$ are possible, and the Bayesian is willing to model that uncertainty (in his own mind) using the tools of probability.
Where is this going?
Let's say we flip the coin $n$ times. One flip does not affect the outcome of the other. The classical statistician would call these independent flips (and indeed they are). We'll have:
$$P(x_n=H \mid x_{n-1}, x_{n-2}, \ldots,x_{1}) = P(x_n=H) = \theta $$
Where $\theta$ is some unknown parameter. (Remember, we don't know what it is, but it's not a random variable! It's some number.)
A Bayesian deep into subjective probability would say that what matters is the probability from her perspective!. If she sees 10 heads in a row, an 11th head is more likely because 10 heads in a row leads one to believe the coin is lopsided in favor of heads. 
$$P(x_{11} = H \mid x_{10}=H, x_{9}=H, \ldots,x_{1}=H) > P(x_1 = H)$$
What has happened here? What is different?! Updating beliefs about a latent random variable $\theta$! If $\theta$ is treated as a random variable, the flips aren't independent anymore. But, the flips are conditionally independent given the value of $\theta$.
$$P(x_{11} = H \mid x_{10}=H, x_{9}=H, \ldots,x_{1}=H, \theta) = P(x_1 = H \mid \theta) = \theta $$
Conditioning on $\theta$ in a sense connects how the Bayesian and the classical statistician models the problem. Or to put it another way, the frequentist and the Bayesian statistician will agree if the Bayesian conditions on $\theta$.
Further notes
I've tried my best to give a short intro here, but what I've done is at best quite superficial and the concepts are in some sense quite deep. If you want to take a dive into the philosophy of probability, Savage's 1954 book, Foundation of Statistics is a classic. Google for bayesian vs. frequentist and a ton of stuff will come up.
Another way to think about IID draws is de Finetti's theorem and the notion of exchangeability. In a Bayesian framework, exchangeability is equivalent to independence conditional on some latent random variable (in this case, the lopsidedness of the coin).
