I am trying to understand how the Mutual Information behaves when I have a sequence of iid samples $X^n$, where each $X$ takes values in an alphabet $\mathcal{X}$ and I have an algorithm $\mathcal{A}:\mathcal{X}^n\to \mathcal{Y}$. I am not posing any constraint on $\mathcal{A}$, but I prefer to think about it as a randomized function.
More precisely I am trying to lower bound $I(X^n;Y)$ where $Y=\mathcal{A}(X^n)$.
I know that: $$I(X^n;Y)\geq n(I(X;Y)) $$ and that $0\leq I(X;Y) \leq \log(|\mathcal{X}|)$.
Since $X$ and $Y$ are far from independent I would argue that $I(X;Y)>0$. Do you think that it is possible that $I(X^n;Y)$ is not polynomial in $n$? Could it be that $I(X;Y)\approx(1/n)$? Is there something trivial that I am not considering?
Thanks for any tip!