Skip to main content
MathOverflow

Return to Question

replaced http://mathoverflow.net/ with https://mathoverflow.net/
Source Link
Community Bot
Community Bot
  • 1
  • 2
  • 3

Let $X_n$ be a random variable distributed on $A_n:=\{1, \ldots, n\}$ and $g_n\colon A_n \to A_n$ such that $\Pr\big(X_n \neq g_n(X_n)\big) \to 0$. Putting $Y_n=g_n(X_n)$, then by Fano's inequality $$\frac{H(X_n\mid Y_n)}{\log n} \to 0,$$ which can be written $$\frac{H(X_n\mid Y_n)}{H(X_n)} \to 0 \qquad (\ast)$$ in the particular case when $X_n$ is uniformly distributed on $A_n$.

As shown by @AnthonyQuas hereshown by @AnthonyQuas here, $(\ast)$ fails in general. Now I'd like to know whether $$\limsup \frac{H(X_n\mid Y_n)}{H(X_n)} <1 \qquad (\ast\ast)$$ holds true in general, in the case when $H(X_n)\to \infty$.

Let $X_n$ be a random variable distributed on $A_n:=\{1, \ldots, n\}$ and $g_n\colon A_n \to A_n$ such that $\Pr\big(X_n \neq g_n(X_n)\big) \to 0$. Putting $Y_n=g_n(X_n)$, then by Fano's inequality $$\frac{H(X_n\mid Y_n)}{\log n} \to 0,$$ which can be written $$\frac{H(X_n\mid Y_n)}{H(X_n)} \to 0 \qquad (\ast)$$ in the particular case when $X_n$ is uniformly distributed on $A_n$.

As shown by @AnthonyQuas here, $(\ast)$ fails in general. Now I'd like to know whether $$\limsup \frac{H(X_n\mid Y_n)}{H(X_n)} <1 \qquad (\ast\ast)$$ holds true in general, in the case when $H(X_n)\to \infty$.

Let $X_n$ be a random variable distributed on $A_n:=\{1, \ldots, n\}$ and $g_n\colon A_n \to A_n$ such that $\Pr\big(X_n \neq g_n(X_n)\big) \to 0$. Putting $Y_n=g_n(X_n)$, then by Fano's inequality $$\frac{H(X_n\mid Y_n)}{\log n} \to 0,$$ which can be written $$\frac{H(X_n\mid Y_n)}{H(X_n)} \to 0 \qquad (\ast)$$ in the particular case when $X_n$ is uniformly distributed on $A_n$.

As shown by @AnthonyQuas here, $(\ast)$ fails in general. Now I'd like to know whether $$\limsup \frac{H(X_n\mid Y_n)}{H(X_n)} <1 \qquad (\ast\ast)$$ holds true in general, in the case when $H(X_n)\to \infty$.

added 13 characters in body
Source Link
Stéphane Laurent
Stéphane Laurent
  • 2.6k
  • 16
  • 19

Let $X_n$ be a random variable distributed on $A_n:=\{1, \ldots, n\}$ and $g_n\colon A_n \to A_n$ such that $\Pr\big(X_n \neq g_n(X_n)\big) \to 0$. Putting $Y_n=g_n(X_n)$, then by Fano's inequality $$H(X_n\mid Y_n) = o(\log n),$$$$\frac{H(X_n\mid Y_n)}{\log n} \to 0,$$ which can be written $$H(X_n\mid Y_n) = o\bigl(H(X_n)\bigr) \qquad (\ast)$$$$\frac{H(X_n\mid Y_n)}{H(X_n)} \to 0 \qquad (\ast)$$ in the particular case when $X_n$ is uniformly distributed on $A_n$.

As shown by @AnthonyQuas here, $(\ast)$ fails in general. Now I'd like to know whether $$H(X_n\mid Y_n) = O\bigl(H(X_n)\bigr) \qquad (\ast\ast)$$$$\limsup \frac{H(X_n\mid Y_n)}{H(X_n)} <1 \qquad (\ast\ast)$$ holds true in general, in the case when $H(X_n)\to \infty$.

Let $X_n$ be a random variable distributed on $A_n:=\{1, \ldots, n\}$ and $g_n\colon A_n \to A_n$ such that $\Pr\big(X_n \neq g_n(X_n)\big) \to 0$. Putting $Y_n=g_n(X_n)$, then by Fano's inequality $$H(X_n\mid Y_n) = o(\log n),$$ which can be written $$H(X_n\mid Y_n) = o\bigl(H(X_n)\bigr) \qquad (\ast)$$ in the particular case when $X_n$ is uniformly distributed on $A_n$.

As shown by @AnthonyQuas here, $(\ast)$ fails in general. Now I'd like to know whether $$H(X_n\mid Y_n) = O\bigl(H(X_n)\bigr) \qquad (\ast\ast)$$ holds true in general, in the case when $H(X_n)\to \infty$.

Let $X_n$ be a random variable distributed on $A_n:=\{1, \ldots, n\}$ and $g_n\colon A_n \to A_n$ such that $\Pr\big(X_n \neq g_n(X_n)\big) \to 0$. Putting $Y_n=g_n(X_n)$, then by Fano's inequality $$\frac{H(X_n\mid Y_n)}{\log n} \to 0,$$ which can be written $$\frac{H(X_n\mid Y_n)}{H(X_n)} \to 0 \qquad (\ast)$$ in the particular case when $X_n$ is uniformly distributed on $A_n$.

As shown by @AnthonyQuas here, $(\ast)$ fails in general. Now I'd like to know whether $$\limsup \frac{H(X_n\mid Y_n)}{H(X_n)} <1 \qquad (\ast\ast)$$ holds true in general, in the case when $H(X_n)\to \infty$.

Source Link
Stéphane Laurent
Stéphane Laurent
  • 2.6k
  • 16
  • 19

order of convergence of the conditional entropy (2)

Let $X_n$ be a random variable distributed on $A_n:=\{1, \ldots, n\}$ and $g_n\colon A_n \to A_n$ such that $\Pr\big(X_n \neq g_n(X_n)\big) \to 0$. Putting $Y_n=g_n(X_n)$, then by Fano's inequality $$H(X_n\mid Y_n) = o(\log n),$$ which can be written $$H(X_n\mid Y_n) = o\bigl(H(X_n)\bigr) \qquad (\ast)$$ in the particular case when $X_n$ is uniformly distributed on $A_n$.

As shown by @AnthonyQuas here, $(\ast)$ fails in general. Now I'd like to know whether $$H(X_n\mid Y_n) = O\bigl(H(X_n)\bigr) \qquad (\ast\ast)$$ holds true in general, in the case when $H(X_n)\to \infty$.