Self-information
Definition
On a sample space $% shorthands \newcommand{\cl}{ \mathcal{#1} } \newcommand{\sc}{ \mathscr{#1} } \newcommand{\bb}{ \mathbb{#1} } \newcommand{\fk}{ \mathfrak{#1} } \renewcommand{\bf}{ \mathbf{#1} } \renewcommand{\sf}{ \mathsf{#1} } % category names \newcommand{\cat}{{ \sf{#1} }} % more shorthands \newcommand{\floor}{ { \lfloor {#1} \rfloor } } \newcommand{\ceil}{ { \lceil {#1} \rceil } } \newcommand{\ol}{ \overline{#1} } \newcommand{\t}{ \text{#1} } \newcommand{\norm}{ { \lvert {#1} \rvert } } % norm/magnitude \newcommand{\card}{ \t{cd} } % cardinality \newcommand{\dcup}{ \sqcup } % disjoint untion \newcommand{\tup}{ \langle {#1} \rangle } % tuples % turing machines \newcommand{\halts}{ {\downarrow} } \newcommand{\loops}{ {\uparrow} } % represents an anonymous parameter % eg. f(\apar) usually denotes the function x \mapsto f(x) \newcommand{\apar}{ {-} } % reverse-order composition %\newcommand{\then}{ \operatorname{\ ;\ } } \newcommand{\then}{ {\scriptsize\ \rhd\ } } % Like f' represents "f after modification", \pre{f} % represents "f before modification" \newcommand{\pre}{{ \small {#1} }} % hook arrows \newcommand{\injects}{ \hookrightarrow } \newcommand{\embeds}{ \hookrightarrow } \newcommand{\surjects}{ \twoheadrightarrow } \newcommand{\projects}{ \twoheadrightarrow } \langle \Omega, P \rangle$, the self-information of some event $% shorthands \newcommand{\cl}{ \mathcal{#1} } \newcommand{\sc}{ \mathscr{#1} } \newcommand{\bb}{ \mathbb{#1} } \newcommand{\fk}{ \mathfrak{#1} } \renewcommand{\bf}{ \mathbf{#1} } \renewcommand{\sf}{ \mathsf{#1} } % category names \newcommand{\cat}{{ \sf{#1} }} % more shorthands \newcommand{\floor}{ { \lfloor {#1} \rfloor } } \newcommand{\ceil}{ { \lceil {#1} \rceil } } \newcommand{\ol}{ \overline{#1} } \newcommand{\t}{ \text{#1} } \newcommand{\norm}{ { \lvert {#1} \rvert } } % norm/magnitude \newcommand{\card}{ \t{cd} } % cardinality \newcommand{\dcup}{ \sqcup } % disjoint untion \newcommand{\tup}{ \langle {#1} \rangle } % tuples % turing machines \newcommand{\halts}{ {\downarrow} } \newcommand{\loops}{ {\uparrow} } % represents an anonymous parameter % eg. f(\apar) usually denotes the function x \mapsto f(x) \newcommand{\apar}{ {-} } % reverse-order composition %\newcommand{\then}{ \operatorname{\ ;\ } } \newcommand{\then}{ {\scriptsize\ \rhd\ } } % Like f' represents "f after modification", \pre{f} % represents "f before modification" \newcommand{\pre}{{ \small {#1} }} % hook arrows \newcommand{\injects}{ \hookrightarrow } \newcommand{\embeds}{ \hookrightarrow } \newcommand{\surjects}{ \twoheadrightarrow } \newcommand{\projects}{ \twoheadrightarrow } \omega \in \Omega$ is a measure of how much “information” is gained when that event occurs. Alternatively, it’s a measure of how “surprising” it is for the event to occur. Intuition:
If $% shorthands \newcommand{\cl}{ \mathcal{#1} } \newcommand{\sc}{ \mathscr{#1} } \newcommand{\bb}{ \mathbb{#1} } \newcommand{\fk}{ \mathfrak{#1} } \renewcommand{\bf}{ \mathbf{#1} } \renewcommand{\sf}{ \mathsf{#1} } % category names \newcommand{\cat}{{ \sf{#1} }} % more shorthands \newcommand{\floor}{ { \lfloor {#1} \rfloor } } \newcommand{\ceil}{ { \lceil {#1} \rceil } } \newcommand{\ol}{ \overline{#1} } \newcommand{\t}{ \text{#1} } \newcommand{\norm}{ { \lvert {#1} \rvert } } % norm/magnitude \newcommand{\card}{ \t{cd} } % cardinality \newcommand{\dcup}{ \sqcup } % disjoint untion \newcommand{\tup}{ \langle {#1} \rangle } % tuples % turing machines \newcommand{\halts}{ {\downarrow} } \newcommand{\loops}{ {\uparrow} } % represents an anonymous parameter % eg. f(\apar) usually denotes the function x \mapsto f(x) \newcommand{\apar}{ {-} } % reverse-order composition %\newcommand{\then}{ \operatorname{\ ;\ } } \newcommand{\then}{ {\scriptsize\ \rhd\ } } % Like f' represents "f after modification", \pre{f} % represents "f before modification" \newcommand{\pre}{{ \small {#1} }} % hook arrows \newcommand{\injects}{ \hookrightarrow } \newcommand{\embeds}{ \hookrightarrow } \newcommand{\surjects}{ \twoheadrightarrow } \newcommand{\projects}{ \twoheadrightarrow } P(\omega) = 1$, then we gain no information from that event occurring; we already knew what would happen. Alternatively, it’s not surprising at all for the event to occur.
As $% shorthands \newcommand{\cl}{ \mathcal{#1} } \newcommand{\sc}{ \mathscr{#1} } \newcommand{\bb}{ \mathbb{#1} } \newcommand{\fk}{ \mathfrak{#1} } \renewcommand{\bf}{ \mathbf{#1} } \renewcommand{\sf}{ \mathsf{#1} } % category names \newcommand{\cat}{{ \sf{#1} }} % more shorthands \newcommand{\floor}{ { \lfloor {#1} \rfloor } } \newcommand{\ceil}{ { \lceil {#1} \rceil } } \newcommand{\ol}{ \overline{#1} } \newcommand{\t}{ \text{#1} } \newcommand{\norm}{ { \lvert {#1} \rvert } } % norm/magnitude \newcommand{\card}{ \t{cd} } % cardinality \newcommand{\dcup}{ \sqcup } % disjoint untion \newcommand{\tup}{ \langle {#1} \rangle } % tuples % turing machines \newcommand{\halts}{ {\downarrow} } \newcommand{\loops}{ {\uparrow} } % represents an anonymous parameter % eg. f(\apar) usually denotes the function x \mapsto f(x) \newcommand{\apar}{ {-} } % reverse-order composition %\newcommand{\then}{ \operatorname{\ ;\ } } \newcommand{\then}{ {\scriptsize\ \rhd\ } } % Like f' represents "f after modification", \pre{f} % represents "f before modification" \newcommand{\pre}{{ \small {#1} }} % hook arrows \newcommand{\injects}{ \hookrightarrow } \newcommand{\embeds}{ \hookrightarrow } \newcommand{\surjects}{ \twoheadrightarrow } \newcommand{\projects}{ \twoheadrightarrow } P(\omega)$ decreases, it’s more surprising for $% shorthands \newcommand{\cl}{ \mathcal{#1} } \newcommand{\sc}{ \mathscr{#1} } \newcommand{\bb}{ \mathbb{#1} } \newcommand{\fk}{ \mathfrak{#1} } \renewcommand{\bf}{ \mathbf{#1} } \renewcommand{\sf}{ \mathsf{#1} } % category names \newcommand{\cat}{{ \sf{#1} }} % more shorthands \newcommand{\floor}{ { \lfloor {#1} \rfloor } } \newcommand{\ceil}{ { \lceil {#1} \rceil } } \newcommand{\ol}{ \overline{#1} } \newcommand{\t}{ \text{#1} } \newcommand{\norm}{ { \lvert {#1} \rvert } } % norm/magnitude \newcommand{\card}{ \t{cd} } % cardinality \newcommand{\dcup}{ \sqcup } % disjoint untion \newcommand{\tup}{ \langle {#1} \rangle } % tuples % turing machines \newcommand{\halts}{ {\downarrow} } \newcommand{\loops}{ {\uparrow} } % represents an anonymous parameter % eg. f(\apar) usually denotes the function x \mapsto f(x) \newcommand{\apar}{ {-} } % reverse-order composition %\newcommand{\then}{ \operatorname{\ ;\ } } \newcommand{\then}{ {\scriptsize\ \rhd\ } } % Like f' represents "f after modification", \pre{f} % represents "f before modification" \newcommand{\pre}{{ \small {#1} }} % hook arrows \newcommand{\injects}{ \hookrightarrow } \newcommand{\embeds}{ \hookrightarrow } \newcommand{\surjects}{ \twoheadrightarrow } \newcommand{\projects}{ \twoheadrightarrow } \omega$ to occur, so we consider the event to contain more information
Consider the case of an event with $% shorthands \newcommand{\cl}{ \mathcal{#1} } \newcommand{\sc}{ \mathscr{#1} } \newcommand{\bb}{ \mathbb{#1} } \newcommand{\fk}{ \mathfrak{#1} } \renewcommand{\bf}{ \mathbf{#1} } \renewcommand{\sf}{ \mathsf{#1} } % category names \newcommand{\cat}{{ \sf{#1} }} % more shorthands \newcommand{\floor}{ { \lfloor {#1} \rfloor } } \newcommand{\ceil}{ { \lceil {#1} \rceil } } \newcommand{\ol}{ \overline{#1} } \newcommand{\t}{ \text{#1} } \newcommand{\norm}{ { \lvert {#1} \rvert } } % norm/magnitude \newcommand{\card}{ \t{cd} } % cardinality \newcommand{\dcup}{ \sqcup } % disjoint untion \newcommand{\tup}{ \langle {#1} \rangle } % tuples % turing machines \newcommand{\halts}{ {\downarrow} } \newcommand{\loops}{ {\uparrow} } % represents an anonymous parameter % eg. f(\apar) usually denotes the function x \mapsto f(x) \newcommand{\apar}{ {-} } % reverse-order composition %\newcommand{\then}{ \operatorname{\ ;\ } } \newcommand{\then}{ {\scriptsize\ \rhd\ } } % Like f' represents "f after modification", \pre{f} % represents "f before modification" \newcommand{\pre}{{ \small {#1} }} % hook arrows \newcommand{\injects}{ \hookrightarrow } \newcommand{\embeds}{ \hookrightarrow } \newcommand{\surjects}{ \twoheadrightarrow } \newcommand{\projects}{ \twoheadrightarrow } {50}\%$ probability, such as a coin toss or an incoming random bit. This serves as a nice unit for entropy. Let’s call it one bit of entropy. Then $% shorthands \newcommand{\cl}{ \mathcal{#1} } \newcommand{\sc}{ \mathscr{#1} } \newcommand{\bb}{ \mathbb{#1} } \newcommand{\fk}{ \mathfrak{#1} } \renewcommand{\bf}{ \mathbf{#1} } \renewcommand{\sf}{ \mathsf{#1} } % category names \newcommand{\cat}{{ \sf{#1} }} % more shorthands \newcommand{\floor}{ { \lfloor {#1} \rfloor } } \newcommand{\ceil}{ { \lceil {#1} \rceil } } \newcommand{\ol}{ \overline{#1} } \newcommand{\t}{ \text{#1} } \newcommand{\norm}{ { \lvert {#1} \rvert } } % norm/magnitude \newcommand{\card}{ \t{cd} } % cardinality \newcommand{\dcup}{ \sqcup } % disjoint untion \newcommand{\tup}{ \langle {#1} \rangle } % tuples % turing machines \newcommand{\halts}{ {\downarrow} } \newcommand{\loops}{ {\uparrow} } % represents an anonymous parameter % eg. f(\apar) usually denotes the function x \mapsto f(x) \newcommand{\apar}{ {-} } % reverse-order composition %\newcommand{\then}{ \operatorname{\ ;\ } } \newcommand{\then}{ {\scriptsize\ \rhd\ } } % Like f' represents "f after modification", \pre{f} % represents "f before modification" \newcommand{\pre}{{ \small {#1} }} % hook arrows \newcommand{\injects}{ \hookrightarrow } \newcommand{\embeds}{ \hookrightarrow } \newcommand{\surjects}{ \twoheadrightarrow } \newcommand{\projects}{ \twoheadrightarrow } n$ incoming independent random bits should have $% shorthands \newcommand{\cl}{ \mathcal{#1} } \newcommand{\sc}{ \mathscr{#1} } \newcommand{\bb}{ \mathbb{#1} } \newcommand{\fk}{ \mathfrak{#1} } \renewcommand{\bf}{ \mathbf{#1} } \renewcommand{\sf}{ \mathsf{#1} } % category names \newcommand{\cat}{{ \sf{#1} }} % more shorthands \newcommand{\floor}{ { \lfloor {#1} \rfloor } } \newcommand{\ceil}{ { \lceil {#1} \rceil } } \newcommand{\ol}{ \overline{#1} } \newcommand{\t}{ \text{#1} } \newcommand{\norm}{ { \lvert {#1} \rvert } } % norm/magnitude \newcommand{\card}{ \t{cd} } % cardinality \newcommand{\dcup}{ \sqcup } % disjoint untion \newcommand{\tup}{ \langle {#1} \rangle } % tuples % turing machines \newcommand{\halts}{ {\downarrow} } \newcommand{\loops}{ {\uparrow} } % represents an anonymous parameter % eg. f(\apar) usually denotes the function x \mapsto f(x) \newcommand{\apar}{ {-} } % reverse-order composition %\newcommand{\then}{ \operatorname{\ ;\ } } \newcommand{\then}{ {\scriptsize\ \rhd\ } } % Like f' represents "f after modification", \pre{f} % represents "f before modification" \newcommand{\pre}{{ \small {#1} }} % hook arrows \newcommand{\injects}{ \hookrightarrow } \newcommand{\embeds}{ \hookrightarrow } \newcommand{\surjects}{ \twoheadrightarrow } \newcommand{\projects}{ \twoheadrightarrow } n$ bits of entropy. Given that $% shorthands \newcommand{\cl}{ \mathcal{#1} } \newcommand{\sc}{ \mathscr{#1} } \newcommand{\bb}{ \mathbb{#1} } \newcommand{\fk}{ \mathfrak{#1} } \renewcommand{\bf}{ \mathbf{#1} } \renewcommand{\sf}{ \mathsf{#1} } % category names \newcommand{\cat}{{ \sf{#1} }} % more shorthands \newcommand{\floor}{ { \lfloor {#1} \rfloor } } \newcommand{\ceil}{ { \lceil {#1} \rceil } } \newcommand{\ol}{ \overline{#1} } \newcommand{\t}{ \text{#1} } \newcommand{\norm}{ { \lvert {#1} \rvert } } % norm/magnitude \newcommand{\card}{ \t{cd} } % cardinality \newcommand{\dcup}{ \sqcup } % disjoint untion \newcommand{\tup}{ \langle {#1} \rangle } % tuples % turing machines \newcommand{\halts}{ {\downarrow} } \newcommand{\loops}{ {\uparrow} } % represents an anonymous parameter % eg. f(\apar) usually denotes the function x \mapsto f(x) \newcommand{\apar}{ {-} } % reverse-order composition %\newcommand{\then}{ \operatorname{\ ;\ } } \newcommand{\then}{ {\scriptsize\ \rhd\ } } % Like f' represents "f after modification", \pre{f} % represents "f before modification" \newcommand{\pre}{{ \small {#1} }} % hook arrows \newcommand{\injects}{ \hookrightarrow } \newcommand{\embeds}{ \hookrightarrow } \newcommand{\surjects}{ \twoheadrightarrow } \newcommand{\projects}{ \twoheadrightarrow } n$ incoming independent random bits have a $% shorthands \newcommand{\cl}{ \mathcal{#1} } \newcommand{\sc}{ \mathscr{#1} } \newcommand{\bb}{ \mathbb{#1} } \newcommand{\fk}{ \mathfrak{#1} } \renewcommand{\bf}{ \mathbf{#1} } \renewcommand{\sf}{ \mathsf{#1} } % category names \newcommand{\cat}{{ \sf{#1} }} % more shorthands \newcommand{\floor}{ { \lfloor {#1} \rfloor } } \newcommand{\ceil}{ { \lceil {#1} \rceil } } \newcommand{\ol}{ \overline{#1} } \newcommand{\t}{ \text{#1} } \newcommand{\norm}{ { \lvert {#1} \rvert } } % norm/magnitude \newcommand{\card}{ \t{cd} } % cardinality \newcommand{\dcup}{ \sqcup } % disjoint untion \newcommand{\tup}{ \langle {#1} \rangle } % tuples % turing machines \newcommand{\halts}{ {\downarrow} } \newcommand{\loops}{ {\uparrow} } % represents an anonymous parameter % eg. f(\apar) usually denotes the function x \mapsto f(x) \newcommand{\apar}{ {-} } % reverse-order composition %\newcommand{\then}{ \operatorname{\ ;\ } } \newcommand{\then}{ {\scriptsize\ \rhd\ } } % Like f' represents "f after modification", \pre{f} % represents "f before modification" \newcommand{\pre}{{ \small {#1} }} % hook arrows \newcommand{\injects}{ \hookrightarrow } \newcommand{\embeds}{ \hookrightarrow } \newcommand{\surjects}{ \twoheadrightarrow } \newcommand{\projects}{ \twoheadrightarrow } 2^{-n}$ probability for each outcome, this motivates defining self-information to be $% shorthands \newcommand{\cl}{ \mathcal{#1} } \newcommand{\sc}{ \mathscr{#1} } \newcommand{\bb}{ \mathbb{#1} } \newcommand{\fk}{ \mathfrak{#1} } \renewcommand{\bf}{ \mathbf{#1} } \renewcommand{\sf}{ \mathsf{#1} } % category names \newcommand{\cat}{{ \sf{#1} }} % more shorthands \newcommand{\floor}{ { \lfloor {#1} \rfloor } } \newcommand{\ceil}{ { \lceil {#1} \rceil } } \newcommand{\ol}{ \overline{#1} } \newcommand{\t}{ \text{#1} } \newcommand{\norm}{ { \lvert {#1} \rvert } } % norm/magnitude \newcommand{\card}{ \t{cd} } % cardinality \newcommand{\dcup}{ \sqcup } % disjoint untion \newcommand{\tup}{ \langle {#1} \rangle } % tuples % turing machines \newcommand{\halts}{ {\downarrow} } \newcommand{\loops}{ {\uparrow} } % represents an anonymous parameter % eg. f(\apar) usually denotes the function x \mapsto f(x) \newcommand{\apar}{ {-} } % reverse-order composition %\newcommand{\then}{ \operatorname{\ ;\ } } \newcommand{\then}{ {\scriptsize\ \rhd\ } } % Like f' represents "f after modification", \pre{f} % represents "f before modification" \newcommand{\pre}{{ \small {#1} }} % hook arrows \newcommand{\injects}{ \hookrightarrow } \newcommand{\embeds}{ \hookrightarrow } \newcommand{\surjects}{ \twoheadrightarrow } \newcommand{\projects}{ \twoheadrightarrow } -\log_2{P(\omega)}$
Definition: The self-information of some $% shorthands \newcommand{\cl}{ \mathcal{#1} } \newcommand{\sc}{ \mathscr{#1} } \newcommand{\bb}{ \mathbb{#1} } \newcommand{\fk}{ \mathfrak{#1} } \renewcommand{\bf}{ \mathbf{#1} } \renewcommand{\sf}{ \mathsf{#1} } % category names \newcommand{\cat}{{ \sf{#1} }} % more shorthands \newcommand{\floor}{ { \lfloor {#1} \rfloor } } \newcommand{\ceil}{ { \lceil {#1} \rceil } } \newcommand{\ol}{ \overline{#1} } \newcommand{\t}{ \text{#1} } \newcommand{\norm}{ { \lvert {#1} \rvert } } % norm/magnitude \newcommand{\card}{ \t{cd} } % cardinality \newcommand{\dcup}{ \sqcup } % disjoint untion \newcommand{\tup}{ \langle {#1} \rangle } % tuples % turing machines \newcommand{\halts}{ {\downarrow} } \newcommand{\loops}{ {\uparrow} } % represents an anonymous parameter % eg. f(\apar) usually denotes the function x \mapsto f(x) \newcommand{\apar}{ {-} } % reverse-order composition %\newcommand{\then}{ \operatorname{\ ;\ } } \newcommand{\then}{ {\scriptsize\ \rhd\ } } % Like f' represents "f after modification", \pre{f} % represents "f before modification" \newcommand{\pre}{{ \small {#1} }} % hook arrows \newcommand{\injects}{ \hookrightarrow } \newcommand{\embeds}{ \hookrightarrow } \newcommand{\surjects}{ \twoheadrightarrow } \newcommand{\projects}{ \twoheadrightarrow } \omega \in \Omega$ is defined to be $% shorthands \newcommand{\cl}{ \mathcal{#1} } \newcommand{\sc}{ \mathscr{#1} } \newcommand{\bb}{ \mathbb{#1} } \newcommand{\fk}{ \mathfrak{#1} } \renewcommand{\bf}{ \mathbf{#1} } \renewcommand{\sf}{ \mathsf{#1} } % category names \newcommand{\cat}{{ \sf{#1} }} % more shorthands \newcommand{\floor}{ { \lfloor {#1} \rfloor } } \newcommand{\ceil}{ { \lceil {#1} \rceil } } \newcommand{\ol}{ \overline{#1} } \newcommand{\t}{ \text{#1} } \newcommand{\norm}{ { \lvert {#1} \rvert } } % norm/magnitude \newcommand{\card}{ \t{cd} } % cardinality \newcommand{\dcup}{ \sqcup } % disjoint untion \newcommand{\tup}{ \langle {#1} \rangle } % tuples % turing machines \newcommand{\halts}{ {\downarrow} } \newcommand{\loops}{ {\uparrow} } % represents an anonymous parameter % eg. f(\apar) usually denotes the function x \mapsto f(x) \newcommand{\apar}{ {-} } % reverse-order composition %\newcommand{\then}{ \operatorname{\ ;\ } } \newcommand{\then}{ {\scriptsize\ \rhd\ } } % Like f' represents "f after modification", \pre{f} % represents "f before modification" \newcommand{\pre}{{ \small {#1} }} % hook arrows \newcommand{\injects}{ \hookrightarrow } \newcommand{\embeds}{ \hookrightarrow } \newcommand{\surjects}{ \twoheadrightarrow } \newcommand{\projects}{ \twoheadrightarrow } I(\omega) := -\log_2(P(\omega))$. (The unit is bits) For two random variables $% shorthands \newcommand{\cl}{ \mathcal{#1} } \newcommand{\sc}{ \mathscr{#1} } \newcommand{\bb}{ \mathbb{#1} } \newcommand{\fk}{ \mathfrak{#1} } \renewcommand{\bf}{ \mathbf{#1} } \renewcommand{\sf}{ \mathsf{#1} } % category names \newcommand{\cat}{{ \sf{#1} }} % more shorthands \newcommand{\floor}{ { \lfloor {#1} \rfloor } } \newcommand{\ceil}{ { \lceil {#1} \rceil } } \newcommand{\ol}{ \overline{#1} } \newcommand{\t}{ \text{#1} } \newcommand{\norm}{ { \lvert {#1} \rvert } } % norm/magnitude \newcommand{\card}{ \t{cd} } % cardinality \newcommand{\dcup}{ \sqcup } % disjoint untion \newcommand{\tup}{ \langle {#1} \rangle } % tuples % turing machines \newcommand{\halts}{ {\downarrow} } \newcommand{\loops}{ {\uparrow} } % represents an anonymous parameter % eg. f(\apar) usually denotes the function x \mapsto f(x) \newcommand{\apar}{ {-} } % reverse-order composition %\newcommand{\then}{ \operatorname{\ ;\ } } \newcommand{\then}{ {\scriptsize\ \rhd\ } } % Like f' represents "f after modification", \pre{f} % represents "f before modification" \newcommand{\pre}{{ \small {#1} }} % hook arrows \newcommand{\injects}{ \hookrightarrow } \newcommand{\embeds}{ \hookrightarrow } \newcommand{\surjects}{ \twoheadrightarrow } \newcommand{\projects}{ \twoheadrightarrow } X, Y$, we define $% shorthands \newcommand{\cl}{ \mathcal{#1} } \newcommand{\sc}{ \mathscr{#1} } \newcommand{\bb}{ \mathbb{#1} } \newcommand{\fk}{ \mathfrak{#1} } \renewcommand{\bf}{ \mathbf{#1} } \renewcommand{\sf}{ \mathsf{#1} } % category names \newcommand{\cat}{{ \sf{#1} }} % more shorthands \newcommand{\floor}{ { \lfloor {#1} \rfloor } } \newcommand{\ceil}{ { \lceil {#1} \rceil } } \newcommand{\ol}{ \overline{#1} } \newcommand{\t}{ \text{#1} } \newcommand{\norm}{ { \lvert {#1} \rvert } } % norm/magnitude \newcommand{\card}{ \t{cd} } % cardinality \newcommand{\dcup}{ \sqcup } % disjoint untion \newcommand{\tup}{ \langle {#1} \rangle } % tuples % turing machines \newcommand{\halts}{ {\downarrow} } \newcommand{\loops}{ {\uparrow} } % represents an anonymous parameter % eg. f(\apar) usually denotes the function x \mapsto f(x) \newcommand{\apar}{ {-} } % reverse-order composition %\newcommand{\then}{ \operatorname{\ ;\ } } \newcommand{\then}{ {\scriptsize\ \rhd\ } } % Like f' represents "f after modification", \pre{f} % represents "f before modification" \newcommand{\pre}{{ \small `{#1} }} % hook arrows \newcommand{\injects}{ \hookrightarrow } \newcommand{\embeds}{ \hookrightarrow } \newcommand{\surjects}{ \twoheadrightarrow } \newcommand{\projects}{ \twoheadrightarrow } I(X \mid Y) := H(X) - H(X \mid Y)$