# cardinality of subset and entropy [closed]

(edited) I am considering the problem about the cardinality of a proper subset, $A\subset\{0,1\}^d$ where $d$ is an integer. Of course, $|A|<2^d$. I am wondering if there is a tighter bound for it. As suggested by Ashok, I suspect the subset cardinality has some thing to do with the entropy, $H(p^*)$ , where $P^*=\sum _{x\in A}P(x)$, and $P(x)$ is the (empirical distribution) type of x. Maybe be the form of $|A|<2^{d*H(P^*)}$, which is similar to the form suggested by Ashok,

any idea will be appreciated. Thanks

-
It doesn't make any sense when you write $P^*=\sum _{x\in A}P(x)$. What do we know about $A$? If $A$ is set of all sequences of a particular type $P$, then $|A|\le 2^{nH(P)}$. – Ashok Mar 1 '12 at 6:53
I think that [cardinals] is aimed to infinite cardinals sort of questions. – Asaf Karagila Mar 1 '12 at 8:38
$A$ is a general subset of the d-dimensional binary set. We know the distribution of each elements in the binary set. Is this sufficient to bound the size of the subset? – johnniac Mar 1 '12 at 16:08

2
I don't understand. If A is ANY proper subset, then the best estimate without knowing more information is $|A|<2^d$ – you Mar 1 '12 at 17:22
@johnniac: You need to make things clear here. If $P$ is the type of a sequence $x$, then $P$ would be a Prob. distribution on $\{0,1\}$, so what do you mean by $P(x)$, for $x\in A$? – Ashok Mar 2 '12 at 6:04

## closed as not a real question by Asaf Karagila, Micah, Brandon Carter, Calvin Lin, NorbertJan 30 at 7:30

It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical and cannot be reasonably answered in its current form. For help clarifying this question so that it can be reopened, see the FAQ.

## 1 Answer

I can only think about the cardinality of the typical set $A_\epsilon^{(d)}$ with respect to your distribution on the random variable $X$. If that is what you mean, then it is well known that: \begin{equation} 2^{n(H(X)+\epsilon)}\geq |A_\epsilon^{(d)}|\geq (1-\epsilon)2^{n(H(X)-\epsilon)} \end{equation}

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 22, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9295528531074524, "perplexity_flag": "head"}