Self-information
Definition
On a sample space ⟨Ω,P⟩ %% general %% % shorthands \newcommand{\cl}[1]{ \mathcal{#1} } \newcommand{\sc}[1]{ \mathscr{#1} } \newcommand{\bb}[1]{ \mathbb{#1} } \newcommand{\fk}[1]{ \mathfrak{#1} } \renewcommand{\bf}[1]{ \mathbf{#1} } \renewcommand{\sf}[1]{ \mathsf{#1} } \renewcommand{\rm}[1]{ \mathrm{#1} } \newcommand{\floor}[1]{ { \lfloor {#1} \rfloor } } \newcommand{\ceil}[1]{ { \lceil {#1} \rceil } } \newcommand{\ol}[1]{ \overline{#1} } \newcommand{\t}[1]{ \text{#1} } \newcommand{\norm}[1]{ { \lvert {#1} \rvert } } % norm/magnitude (REMOVE) \newcommand{\mag}[1]{ { \left\lvert {#1} \right\rvert } } % magnitude \newcommand{\smag}[1]{ { \lvert {#1} \rvert } } % short mag \newcommand{\card}{ \t{cd} } % cardinality \newcommand{\dcup}{ \sqcup } % disjoint untion \newcommand{\tup}[1]{ \langle {#1} \rangle } % tuples \newcommand{\tl}{ \tilde } \newcommand{\wt}{ \widetilde } \newcommand{\To}{ \Rightarrow } % draw a box outlining some math \newcommand{\box}[1]{ \fbox{$ #1 $} } % f \onall X = { f(x) : x ∈ X } \newcommand{\onall}[1]{ { \llbracket {#1} \rrbracket } } % shorthands: various brackets \newcommand{\tpar}[1]{ \left( {#1} \right) } % "tall parens" \newcommand{\tbrak}[1]{ \left[ {#1} \right] } % "tall brackets" \newcommand{\tbrac}[1]{ \left\{ {#1} \right\} } % "tall braces" % reverse \mapsto (FIXME: make better) %\newcommand{\mapsfrom}{ \mathop{\leftarrow\!\mid} } \newcommand{\mapsfrom}{ \mathrel{↤} } % reverse-order composition \newcommand{\then}{ \operatorname{\ ;\ } } % Like f' represents "f after modification", \pre{f} % represents "f before modification" % TODO: remove this? \newcommand{\pre}[1]{{ \small `{#1} }} % hook arrows \newcommand{\injects}{ \hookrightarrow } \newcommand{\embeds}{ \hookrightarrow } \newcommand{\surjects}{ \twoheadrightarrow } \newcommand{\projects}{ \twoheadrightarrow } \newcommand{\id}{ \,\mathrm d } % integration d % derivatives: use {\ddn n x y} for (dy/dx) \newcommand{\ddn}[3]{ \frac{ {\mathrm d}^{#1} {#2} }{ {\mathrm d} {#3}^{#1} } } % nth derivative \newcommand{\dd}{ \ddn{} } % first derivative \newcommand{\d}{ \dd{} } % first derivative (no numerator) \newcommand{\dn}[1]{ \ddn{#1}{} } % nth derivative (no numerator) % derivatives: use {\D n x y} for (∂_x y) \newcommand{\Dn}[2]{ \partial^{#1}_{#2} } \newcommand{\D}{ \Dn{} } % no power \newcommand{\ig}[2]{ \int {#2} \, \mathrm d {#1} } % first integral %% category theory %% % category names \newcommand{\cat}[1]{{ \sf{#1} }} % yoneda embedding \newcommand{\yo}{よ} % extra long right-arrows \newcommand{\X}{-\!\!\!-\!\!\!} \newcommand{\xlongrightarrow}{ \mathop{ \, \X\longrightarrow \, } } \newcommand{\xxlongrightarrow}{ \mathop{ \, \X\X\longrightarrow \, } } \newcommand{\xxxlongrightarrow}{ \mathop{ \, \X\X\X\longrightarrow \, } } \newcommand{\takenby}[1]{ \overset{#1}{\rightarrow} } \newcommand{\longtakenby}[1]{ \overset{#1}{\longrightarrow} } \newcommand{\xlongtakenby}[1]{ \overset{#1}{\xlongrightarrow} } \newcommand{\xxlongtakenby}[1]{ \overset{#1}{\xxlongrightarrow} } \newcommand{\xxxlongtakenby}[1]{ \overset{#1}{\xxxlongrightarrow} } % represents an anonymous parameter % eg. $f(\apar)$ usually denotes the function $x \mapsto f(x)$ % TODO: remove this? \newcommand{\apar}{ {-} } %% computability %% % turing machines \newcommand{\halts}{ {\downarrow} } \newcommand{\loops}{ {\uparrow} } \langle \Omega, P \rangle, the self-information of some event ω∈Ω %% general %% % shorthands \newcommand{\cl}[1]{ \mathcal{#1} } \newcommand{\sc}[1]{ \mathscr{#1} } \newcommand{\bb}[1]{ \mathbb{#1} } \newcommand{\fk}[1]{ \mathfrak{#1} } \renewcommand{\bf}[1]{ \mathbf{#1} } \renewcommand{\sf}[1]{ \mathsf{#1} } \renewcommand{\rm}[1]{ \mathrm{#1} } \newcommand{\floor}[1]{ { \lfloor {#1} \rfloor } } \newcommand{\ceil}[1]{ { \lceil {#1} \rceil } } \newcommand{\ol}[1]{ \overline{#1} } \newcommand{\t}[1]{ \text{#1} } \newcommand{\norm}[1]{ { \lvert {#1} \rvert } } % norm/magnitude (REMOVE) \newcommand{\mag}[1]{ { \left\lvert {#1} \right\rvert } } % magnitude \newcommand{\smag}[1]{ { \lvert {#1} \rvert } } % short mag \newcommand{\card}{ \t{cd} } % cardinality \newcommand{\dcup}{ \sqcup } % disjoint untion \newcommand{\tup}[1]{ \langle {#1} \rangle } % tuples \newcommand{\tl}{ \tilde } \newcommand{\wt}{ \widetilde } \newcommand{\To}{ \Rightarrow } % draw a box outlining some math \newcommand{\box}[1]{ \fbox{$ #1 $} } % f \onall X = { f(x) : x ∈ X } \newcommand{\onall}[1]{ { \llbracket {#1} \rrbracket } } % shorthands: various brackets \newcommand{\tpar}[1]{ \left( {#1} \right) } % "tall parens" \newcommand{\tbrak}[1]{ \left[ {#1} \right] } % "tall brackets" \newcommand{\tbrac}[1]{ \left\{ {#1} \right\} } % "tall braces" % reverse \mapsto (FIXME: make better) %\newcommand{\mapsfrom}{ \mathop{\leftarrow\!\mid} } \newcommand{\mapsfrom}{ \mathrel{↤} } % reverse-order composition \newcommand{\then}{ \operatorname{\ ;\ } } % Like f' represents "f after modification", \pre{f} % represents "f before modification" % TODO: remove this? \newcommand{\pre}[1]{{ \small `{#1} }} % hook arrows \newcommand{\injects}{ \hookrightarrow } \newcommand{\embeds}{ \hookrightarrow } \newcommand{\surjects}{ \twoheadrightarrow } \newcommand{\projects}{ \twoheadrightarrow } \newcommand{\id}{ \,\mathrm d } % integration d % derivatives: use {\ddn n x y} for (dy/dx) \newcommand{\ddn}[3]{ \frac{ {\mathrm d}^{#1} {#2} }{ {\mathrm d} {#3}^{#1} } } % nth derivative \newcommand{\dd}{ \ddn{} } % first derivative \newcommand{\d}{ \dd{} } % first derivative (no numerator) \newcommand{\dn}[1]{ \ddn{#1}{} } % nth derivative (no numerator) % derivatives: use {\D n x y} for (∂_x y) \newcommand{\Dn}[2]{ \partial^{#1}_{#2} } \newcommand{\D}{ \Dn{} } % no power \newcommand{\ig}[2]{ \int {#2} \, \mathrm d {#1} } % first integral %% category theory %% % category names \newcommand{\cat}[1]{{ \sf{#1} }} % yoneda embedding \newcommand{\yo}{よ} % extra long right-arrows \newcommand{\X}{-\!\!\!-\!\!\!} \newcommand{\xlongrightarrow}{ \mathop{ \, \X\longrightarrow \, } } \newcommand{\xxlongrightarrow}{ \mathop{ \, \X\X\longrightarrow \, } } \newcommand{\xxxlongrightarrow}{ \mathop{ \, \X\X\X\longrightarrow \, } } \newcommand{\takenby}[1]{ \overset{#1}{\rightarrow} } \newcommand{\longtakenby}[1]{ \overset{#1}{\longrightarrow} } \newcommand{\xlongtakenby}[1]{ \overset{#1}{\xlongrightarrow} } \newcommand{\xxlongtakenby}[1]{ \overset{#1}{\xxlongrightarrow} } \newcommand{\xxxlongtakenby}[1]{ \overset{#1}{\xxxlongrightarrow} } % represents an anonymous parameter % eg. $f(\apar)$ usually denotes the function $x \mapsto f(x)$ % TODO: remove this? \newcommand{\apar}{ {-} } %% computability %% % turing machines \newcommand{\halts}{ {\downarrow} } \newcommand{\loops}{ {\uparrow} } \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 P(ω)=1 %% general %% % shorthands \newcommand{\cl}[1]{ \mathcal{#1} } \newcommand{\sc}[1]{ \mathscr{#1} } \newcommand{\bb}[1]{ \mathbb{#1} } \newcommand{\fk}[1]{ \mathfrak{#1} } \renewcommand{\bf}[1]{ \mathbf{#1} } \renewcommand{\sf}[1]{ \mathsf{#1} } \renewcommand{\rm}[1]{ \mathrm{#1} } \newcommand{\floor}[1]{ { \lfloor {#1} \rfloor } } \newcommand{\ceil}[1]{ { \lceil {#1} \rceil } } \newcommand{\ol}[1]{ \overline{#1} } \newcommand{\t}[1]{ \text{#1} } \newcommand{\norm}[1]{ { \lvert {#1} \rvert } } % norm/magnitude (REMOVE) \newcommand{\mag}[1]{ { \left\lvert {#1} \right\rvert } } % magnitude \newcommand{\smag}[1]{ { \lvert {#1} \rvert } } % short mag \newcommand{\card}{ \t{cd} } % cardinality \newcommand{\dcup}{ \sqcup } % disjoint untion \newcommand{\tup}[1]{ \langle {#1} \rangle } % tuples \newcommand{\tl}{ \tilde } \newcommand{\wt}{ \widetilde } \newcommand{\To}{ \Rightarrow } % draw a box outlining some math \newcommand{\box}[1]{ \fbox{$ #1 $} } % f \onall X = { f(x) : x ∈ X } \newcommand{\onall}[1]{ { \llbracket {#1} \rrbracket } } % shorthands: various brackets \newcommand{\tpar}[1]{ \left( {#1} \right) } % "tall parens" \newcommand{\tbrak}[1]{ \left[ {#1} \right] } % "tall brackets" \newcommand{\tbrac}[1]{ \left\{ {#1} \right\} } % "tall braces" % reverse \mapsto (FIXME: make better) %\newcommand{\mapsfrom}{ \mathop{\leftarrow\!\mid} } \newcommand{\mapsfrom}{ \mathrel{↤} } % reverse-order composition \newcommand{\then}{ \operatorname{\ ;\ } } % Like f' represents "f after modification", \pre{f} % represents "f before modification" % TODO: remove this? \newcommand{\pre}[1]{{ \small `{#1} }} % hook arrows \newcommand{\injects}{ \hookrightarrow } \newcommand{\embeds}{ \hookrightarrow } \newcommand{\surjects}{ \twoheadrightarrow } \newcommand{\projects}{ \twoheadrightarrow } \newcommand{\id}{ \,\mathrm d } % integration d % derivatives: use {\ddn n x y} for (dy/dx) \newcommand{\ddn}[3]{ \frac{ {\mathrm d}^{#1} {#2} }{ {\mathrm d} {#3}^{#1} } } % nth derivative \newcommand{\dd}{ \ddn{} } % first derivative \newcommand{\d}{ \dd{} } % first derivative (no numerator) \newcommand{\dn}[1]{ \ddn{#1}{} } % nth derivative (no numerator) % derivatives: use {\D n x y} for (∂_x y) \newcommand{\Dn}[2]{ \partial^{#1}_{#2} } \newcommand{\D}{ \Dn{} } % no power \newcommand{\ig}[2]{ \int {#2} \, \mathrm d {#1} } % first integral %% category theory %% % category names \newcommand{\cat}[1]{{ \sf{#1} }} % yoneda embedding \newcommand{\yo}{よ} % extra long right-arrows \newcommand{\X}{-\!\!\!-\!\!\!} \newcommand{\xlongrightarrow}{ \mathop{ \, \X\longrightarrow \, } } \newcommand{\xxlongrightarrow}{ \mathop{ \, \X\X\longrightarrow \, } } \newcommand{\xxxlongrightarrow}{ \mathop{ \, \X\X\X\longrightarrow \, } } \newcommand{\takenby}[1]{ \overset{#1}{\rightarrow} } \newcommand{\longtakenby}[1]{ \overset{#1}{\longrightarrow} } \newcommand{\xlongtakenby}[1]{ \overset{#1}{\xlongrightarrow} } \newcommand{\xxlongtakenby}[1]{ \overset{#1}{\xxlongrightarrow} } \newcommand{\xxxlongtakenby}[1]{ \overset{#1}{\xxxlongrightarrow} } % represents an anonymous parameter % eg. $f(\apar)$ usually denotes the function $x \mapsto f(x)$ % TODO: remove this? \newcommand{\apar}{ {-} } %% computability %% % turing machines \newcommand{\halts}{ {\downarrow} } \newcommand{\loops}{ {\uparrow} } 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 P(ω) %% general %% % shorthands \newcommand{\cl}[1]{ \mathcal{#1} } \newcommand{\sc}[1]{ \mathscr{#1} } \newcommand{\bb}[1]{ \mathbb{#1} } \newcommand{\fk}[1]{ \mathfrak{#1} } \renewcommand{\bf}[1]{ \mathbf{#1} } \renewcommand{\sf}[1]{ \mathsf{#1} } \renewcommand{\rm}[1]{ \mathrm{#1} } \newcommand{\floor}[1]{ { \lfloor {#1} \rfloor } } \newcommand{\ceil}[1]{ { \lceil {#1} \rceil } } \newcommand{\ol}[1]{ \overline{#1} } \newcommand{\t}[1]{ \text{#1} } \newcommand{\norm}[1]{ { \lvert {#1} \rvert } } % norm/magnitude (REMOVE) \newcommand{\mag}[1]{ { \left\lvert {#1} \right\rvert } } % magnitude \newcommand{\smag}[1]{ { \lvert {#1} \rvert } } % short mag \newcommand{\card}{ \t{cd} } % cardinality \newcommand{\dcup}{ \sqcup } % disjoint untion \newcommand{\tup}[1]{ \langle {#1} \rangle } % tuples \newcommand{\tl}{ \tilde } \newcommand{\wt}{ \widetilde } \newcommand{\To}{ \Rightarrow } % draw a box outlining some math \newcommand{\box}[1]{ \fbox{$ #1 $} } % f \onall X = { f(x) : x ∈ X } \newcommand{\onall}[1]{ { \llbracket {#1} \rrbracket } } % shorthands: various brackets \newcommand{\tpar}[1]{ \left( {#1} \right) } % "tall parens" \newcommand{\tbrak}[1]{ \left[ {#1} \right] } % "tall brackets" \newcommand{\tbrac}[1]{ \left\{ {#1} \right\} } % "tall braces" % reverse \mapsto (FIXME: make better) %\newcommand{\mapsfrom}{ \mathop{\leftarrow\!\mid} } \newcommand{\mapsfrom}{ \mathrel{↤} } % reverse-order composition \newcommand{\then}{ \operatorname{\ ;\ } } % Like f' represents "f after modification", \pre{f} % represents "f before modification" % TODO: remove this? \newcommand{\pre}[1]{{ \small `{#1} }} % hook arrows \newcommand{\injects}{ \hookrightarrow } \newcommand{\embeds}{ \hookrightarrow } \newcommand{\surjects}{ \twoheadrightarrow } \newcommand{\projects}{ \twoheadrightarrow } \newcommand{\id}{ \,\mathrm d } % integration d % derivatives: use {\ddn n x y} for (dy/dx) \newcommand{\ddn}[3]{ \frac{ {\mathrm d}^{#1} {#2} }{ {\mathrm d} {#3}^{#1} } } % nth derivative \newcommand{\dd}{ \ddn{} } % first derivative \newcommand{\d}{ \dd{} } % first derivative (no numerator) \newcommand{\dn}[1]{ \ddn{#1}{} } % nth derivative (no numerator) % derivatives: use {\D n x y} for (∂_x y) \newcommand{\Dn}[2]{ \partial^{#1}_{#2} } \newcommand{\D}{ \Dn{} } % no power \newcommand{\ig}[2]{ \int {#2} \, \mathrm d {#1} } % first integral %% category theory %% % category names \newcommand{\cat}[1]{{ \sf{#1} }} % yoneda embedding \newcommand{\yo}{よ} % extra long right-arrows \newcommand{\X}{-\!\!\!-\!\!\!} \newcommand{\xlongrightarrow}{ \mathop{ \, \X\longrightarrow \, } } \newcommand{\xxlongrightarrow}{ \mathop{ \, \X\X\longrightarrow \, } } \newcommand{\xxxlongrightarrow}{ \mathop{ \, \X\X\X\longrightarrow \, } } \newcommand{\takenby}[1]{ \overset{#1}{\rightarrow} } \newcommand{\longtakenby}[1]{ \overset{#1}{\longrightarrow} } \newcommand{\xlongtakenby}[1]{ \overset{#1}{\xlongrightarrow} } \newcommand{\xxlongtakenby}[1]{ \overset{#1}{\xxlongrightarrow} } \newcommand{\xxxlongtakenby}[1]{ \overset{#1}{\xxxlongrightarrow} } % represents an anonymous parameter % eg. $f(\apar)$ usually denotes the function $x \mapsto f(x)$ % TODO: remove this? \newcommand{\apar}{ {-} } %% computability %% % turing machines \newcommand{\halts}{ {\downarrow} } \newcommand{\loops}{ {\uparrow} } P(\omega) decreases, it’s more surprising for ω %% general %% % shorthands \newcommand{\cl}[1]{ \mathcal{#1} } \newcommand{\sc}[1]{ \mathscr{#1} } \newcommand{\bb}[1]{ \mathbb{#1} } \newcommand{\fk}[1]{ \mathfrak{#1} } \renewcommand{\bf}[1]{ \mathbf{#1} } \renewcommand{\sf}[1]{ \mathsf{#1} } \renewcommand{\rm}[1]{ \mathrm{#1} } \newcommand{\floor}[1]{ { \lfloor {#1} \rfloor } } \newcommand{\ceil}[1]{ { \lceil {#1} \rceil } } \newcommand{\ol}[1]{ \overline{#1} } \newcommand{\t}[1]{ \text{#1} } \newcommand{\norm}[1]{ { \lvert {#1} \rvert } } % norm/magnitude (REMOVE) \newcommand{\mag}[1]{ { \left\lvert {#1} \right\rvert } } % magnitude \newcommand{\smag}[1]{ { \lvert {#1} \rvert } } % short mag \newcommand{\card}{ \t{cd} } % cardinality \newcommand{\dcup}{ \sqcup } % disjoint untion \newcommand{\tup}[1]{ \langle {#1} \rangle } % tuples \newcommand{\tl}{ \tilde } \newcommand{\wt}{ \widetilde } \newcommand{\To}{ \Rightarrow } % draw a box outlining some math \newcommand{\box}[1]{ \fbox{$ #1 $} } % f \onall X = { f(x) : x ∈ X } \newcommand{\onall}[1]{ { \llbracket {#1} \rrbracket } } % shorthands: various brackets \newcommand{\tpar}[1]{ \left( {#1} \right) } % "tall parens" \newcommand{\tbrak}[1]{ \left[ {#1} \right] } % "tall brackets" \newcommand{\tbrac}[1]{ \left\{ {#1} \right\} } % "tall braces" % reverse \mapsto (FIXME: make better) %\newcommand{\mapsfrom}{ \mathop{\leftarrow\!\mid} } \newcommand{\mapsfrom}{ \mathrel{↤} } % reverse-order composition \newcommand{\then}{ \operatorname{\ ;\ } } % Like f' represents "f after modification", \pre{f} % represents "f before modification" % TODO: remove this? \newcommand{\pre}[1]{{ \small `{#1} }} % hook arrows \newcommand{\injects}{ \hookrightarrow } \newcommand{\embeds}{ \hookrightarrow } \newcommand{\surjects}{ \twoheadrightarrow } \newcommand{\projects}{ \twoheadrightarrow } \newcommand{\id}{ \,\mathrm d } % integration d % derivatives: use {\ddn n x y} for (dy/dx) \newcommand{\ddn}[3]{ \frac{ {\mathrm d}^{#1} {#2} }{ {\mathrm d} {#3}^{#1} } } % nth derivative \newcommand{\dd}{ \ddn{} } % first derivative \newcommand{\d}{ \dd{} } % first derivative (no numerator) \newcommand{\dn}[1]{ \ddn{#1}{} } % nth derivative (no numerator) % derivatives: use {\D n x y} for (∂_x y) \newcommand{\Dn}[2]{ \partial^{#1}_{#2} } \newcommand{\D}{ \Dn{} } % no power \newcommand{\ig}[2]{ \int {#2} \, \mathrm d {#1} } % first integral %% category theory %% % category names \newcommand{\cat}[1]{{ \sf{#1} }} % yoneda embedding \newcommand{\yo}{よ} % extra long right-arrows \newcommand{\X}{-\!\!\!-\!\!\!} \newcommand{\xlongrightarrow}{ \mathop{ \, \X\longrightarrow \, } } \newcommand{\xxlongrightarrow}{ \mathop{ \, \X\X\longrightarrow \, } } \newcommand{\xxxlongrightarrow}{ \mathop{ \, \X\X\X\longrightarrow \, } } \newcommand{\takenby}[1]{ \overset{#1}{\rightarrow} } \newcommand{\longtakenby}[1]{ \overset{#1}{\longrightarrow} } \newcommand{\xlongtakenby}[1]{ \overset{#1}{\xlongrightarrow} } \newcommand{\xxlongtakenby}[1]{ \overset{#1}{\xxlongrightarrow} } \newcommand{\xxxlongtakenby}[1]{ \overset{#1}{\xxxlongrightarrow} } % represents an anonymous parameter % eg. $f(\apar)$ usually denotes the function $x \mapsto f(x)$ % TODO: remove this? \newcommand{\apar}{ {-} } %% computability %% % turing machines \newcommand{\halts}{ {\downarrow} } \newcommand{\loops}{ {\uparrow} } \omega to occur, so we consider the event to contain more information
Consider the case of an event with 50% %% general %% % shorthands \newcommand{\cl}[1]{ \mathcal{#1} } \newcommand{\sc}[1]{ \mathscr{#1} } \newcommand{\bb}[1]{ \mathbb{#1} } \newcommand{\fk}[1]{ \mathfrak{#1} } \renewcommand{\bf}[1]{ \mathbf{#1} } \renewcommand{\sf}[1]{ \mathsf{#1} } \renewcommand{\rm}[1]{ \mathrm{#1} } \newcommand{\floor}[1]{ { \lfloor {#1} \rfloor } } \newcommand{\ceil}[1]{ { \lceil {#1} \rceil } } \newcommand{\ol}[1]{ \overline{#1} } \newcommand{\t}[1]{ \text{#1} } \newcommand{\norm}[1]{ { \lvert {#1} \rvert } } % norm/magnitude (REMOVE) \newcommand{\mag}[1]{ { \left\lvert {#1} \right\rvert } } % magnitude \newcommand{\smag}[1]{ { \lvert {#1} \rvert } } % short mag \newcommand{\card}{ \t{cd} } % cardinality \newcommand{\dcup}{ \sqcup } % disjoint untion \newcommand{\tup}[1]{ \langle {#1} \rangle } % tuples \newcommand{\tl}{ \tilde } \newcommand{\wt}{ \widetilde } \newcommand{\To}{ \Rightarrow } % draw a box outlining some math \newcommand{\box}[1]{ \fbox{$ #1 $} } % f \onall X = { f(x) : x ∈ X } \newcommand{\onall}[1]{ { \llbracket {#1} \rrbracket } } % shorthands: various brackets \newcommand{\tpar}[1]{ \left( {#1} \right) } % "tall parens" \newcommand{\tbrak}[1]{ \left[ {#1} \right] } % "tall brackets" \newcommand{\tbrac}[1]{ \left\{ {#1} \right\} } % "tall braces" % reverse \mapsto (FIXME: make better) %\newcommand{\mapsfrom}{ \mathop{\leftarrow\!\mid} } \newcommand{\mapsfrom}{ \mathrel{↤} } % reverse-order composition \newcommand{\then}{ \operatorname{\ ;\ } } % Like f' represents "f after modification", \pre{f} % represents "f before modification" % TODO: remove this? \newcommand{\pre}[1]{{ \small `{#1} }} % hook arrows \newcommand{\injects}{ \hookrightarrow } \newcommand{\embeds}{ \hookrightarrow } \newcommand{\surjects}{ \twoheadrightarrow } \newcommand{\projects}{ \twoheadrightarrow } \newcommand{\id}{ \,\mathrm d } % integration d % derivatives: use {\ddn n x y} for (dy/dx) \newcommand{\ddn}[3]{ \frac{ {\mathrm d}^{#1} {#2} }{ {\mathrm d} {#3}^{#1} } } % nth derivative \newcommand{\dd}{ \ddn{} } % first derivative \newcommand{\d}{ \dd{} } % first derivative (no numerator) \newcommand{\dn}[1]{ \ddn{#1}{} } % nth derivative (no numerator) % derivatives: use {\D n x y} for (∂_x y) \newcommand{\Dn}[2]{ \partial^{#1}_{#2} } \newcommand{\D}{ \Dn{} } % no power \newcommand{\ig}[2]{ \int {#2} \, \mathrm d {#1} } % first integral %% category theory %% % category names \newcommand{\cat}[1]{{ \sf{#1} }} % yoneda embedding \newcommand{\yo}{よ} % extra long right-arrows \newcommand{\X}{-\!\!\!-\!\!\!} \newcommand{\xlongrightarrow}{ \mathop{ \, \X\longrightarrow \, } } \newcommand{\xxlongrightarrow}{ \mathop{ \, \X\X\longrightarrow \, } } \newcommand{\xxxlongrightarrow}{ \mathop{ \, \X\X\X\longrightarrow \, } } \newcommand{\takenby}[1]{ \overset{#1}{\rightarrow} } \newcommand{\longtakenby}[1]{ \overset{#1}{\longrightarrow} } \newcommand{\xlongtakenby}[1]{ \overset{#1}{\xlongrightarrow} } \newcommand{\xxlongtakenby}[1]{ \overset{#1}{\xxlongrightarrow} } \newcommand{\xxxlongtakenby}[1]{ \overset{#1}{\xxxlongrightarrow} } % represents an anonymous parameter % eg. $f(\apar)$ usually denotes the function $x \mapsto f(x)$ % TODO: remove this? \newcommand{\apar}{ {-} } %% computability %% % turing machines \newcommand{\halts}{ {\downarrow} } \newcommand{\loops}{ {\uparrow} } {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 n %% general %% % shorthands \newcommand{\cl}[1]{ \mathcal{#1} } \newcommand{\sc}[1]{ \mathscr{#1} } \newcommand{\bb}[1]{ \mathbb{#1} } \newcommand{\fk}[1]{ \mathfrak{#1} } \renewcommand{\bf}[1]{ \mathbf{#1} } \renewcommand{\sf}[1]{ \mathsf{#1} } \renewcommand{\rm}[1]{ \mathrm{#1} } \newcommand{\floor}[1]{ { \lfloor {#1} \rfloor } } \newcommand{\ceil}[1]{ { \lceil {#1} \rceil } } \newcommand{\ol}[1]{ \overline{#1} } \newcommand{\t}[1]{ \text{#1} } \newcommand{\norm}[1]{ { \lvert {#1} \rvert } } % norm/magnitude (REMOVE) \newcommand{\mag}[1]{ { \left\lvert {#1} \right\rvert } } % magnitude \newcommand{\smag}[1]{ { \lvert {#1} \rvert } } % short mag \newcommand{\card}{ \t{cd} } % cardinality \newcommand{\dcup}{ \sqcup } % disjoint untion \newcommand{\tup}[1]{ \langle {#1} \rangle } % tuples \newcommand{\tl}{ \tilde } \newcommand{\wt}{ \widetilde } \newcommand{\To}{ \Rightarrow } % draw a box outlining some math \newcommand{\box}[1]{ \fbox{$ #1 $} } % f \onall X = { f(x) : x ∈ X } \newcommand{\onall}[1]{ { \llbracket {#1} \rrbracket } } % shorthands: various brackets \newcommand{\tpar}[1]{ \left( {#1} \right) } % "tall parens" \newcommand{\tbrak}[1]{ \left[ {#1} \right] } % "tall brackets" \newcommand{\tbrac}[1]{ \left\{ {#1} \right\} } % "tall braces" % reverse \mapsto (FIXME: make better) %\newcommand{\mapsfrom}{ \mathop{\leftarrow\!\mid} } \newcommand{\mapsfrom}{ \mathrel{↤} } % reverse-order composition \newcommand{\then}{ \operatorname{\ ;\ } } % Like f' represents "f after modification", \pre{f} % represents "f before modification" % TODO: remove this? \newcommand{\pre}[1]{{ \small `{#1} }} % hook arrows \newcommand{\injects}{ \hookrightarrow } \newcommand{\embeds}{ \hookrightarrow } \newcommand{\surjects}{ \twoheadrightarrow } \newcommand{\projects}{ \twoheadrightarrow } \newcommand{\id}{ \,\mathrm d } % integration d % derivatives: use {\ddn n x y} for (dy/dx) \newcommand{\ddn}[3]{ \frac{ {\mathrm d}^{#1} {#2} }{ {\mathrm d} {#3}^{#1} } } % nth derivative \newcommand{\dd}{ \ddn{} } % first derivative \newcommand{\d}{ \dd{} } % first derivative (no numerator) \newcommand{\dn}[1]{ \ddn{#1}{} } % nth derivative (no numerator) % derivatives: use {\D n x y} for (∂_x y) \newcommand{\Dn}[2]{ \partial^{#1}_{#2} } \newcommand{\D}{ \Dn{} } % no power \newcommand{\ig}[2]{ \int {#2} \, \mathrm d {#1} } % first integral %% category theory %% % category names \newcommand{\cat}[1]{{ \sf{#1} }} % yoneda embedding \newcommand{\yo}{よ} % extra long right-arrows \newcommand{\X}{-\!\!\!-\!\!\!} \newcommand{\xlongrightarrow}{ \mathop{ \, \X\longrightarrow \, } } \newcommand{\xxlongrightarrow}{ \mathop{ \, \X\X\longrightarrow \, } } \newcommand{\xxxlongrightarrow}{ \mathop{ \, \X\X\X\longrightarrow \, } } \newcommand{\takenby}[1]{ \overset{#1}{\rightarrow} } \newcommand{\longtakenby}[1]{ \overset{#1}{\longrightarrow} } \newcommand{\xlongtakenby}[1]{ \overset{#1}{\xlongrightarrow} } \newcommand{\xxlongtakenby}[1]{ \overset{#1}{\xxlongrightarrow} } \newcommand{\xxxlongtakenby}[1]{ \overset{#1}{\xxxlongrightarrow} } % represents an anonymous parameter % eg. $f(\apar)$ usually denotes the function $x \mapsto f(x)$ % TODO: remove this? \newcommand{\apar}{ {-} } %% computability %% % turing machines \newcommand{\halts}{ {\downarrow} } \newcommand{\loops}{ {\uparrow} } n incoming independent random bits should have n %% general %% % shorthands \newcommand{\cl}[1]{ \mathcal{#1} } \newcommand{\sc}[1]{ \mathscr{#1} } \newcommand{\bb}[1]{ \mathbb{#1} } \newcommand{\fk}[1]{ \mathfrak{#1} } \renewcommand{\bf}[1]{ \mathbf{#1} } \renewcommand{\sf}[1]{ \mathsf{#1} } \renewcommand{\rm}[1]{ \mathrm{#1} } \newcommand{\floor}[1]{ { \lfloor {#1} \rfloor } } \newcommand{\ceil}[1]{ { \lceil {#1} \rceil } } \newcommand{\ol}[1]{ \overline{#1} } \newcommand{\t}[1]{ \text{#1} } \newcommand{\norm}[1]{ { \lvert {#1} \rvert } } % norm/magnitude (REMOVE) \newcommand{\mag}[1]{ { \left\lvert {#1} \right\rvert } } % magnitude \newcommand{\smag}[1]{ { \lvert {#1} \rvert } } % short mag \newcommand{\card}{ \t{cd} } % cardinality \newcommand{\dcup}{ \sqcup } % disjoint untion \newcommand{\tup}[1]{ \langle {#1} \rangle } % tuples \newcommand{\tl}{ \tilde } \newcommand{\wt}{ \widetilde } \newcommand{\To}{ \Rightarrow } % draw a box outlining some math \newcommand{\box}[1]{ \fbox{$ #1 $} } % f \onall X = { f(x) : x ∈ X } \newcommand{\onall}[1]{ { \llbracket {#1} \rrbracket } } % shorthands: various brackets \newcommand{\tpar}[1]{ \left( {#1} \right) } % "tall parens" \newcommand{\tbrak}[1]{ \left[ {#1} \right] } % "tall brackets" \newcommand{\tbrac}[1]{ \left\{ {#1} \right\} } % "tall braces" % reverse \mapsto (FIXME: make better) %\newcommand{\mapsfrom}{ \mathop{\leftarrow\!\mid} } \newcommand{\mapsfrom}{ \mathrel{↤} } % reverse-order composition \newcommand{\then}{ \operatorname{\ ;\ } } % Like f' represents "f after modification", \pre{f} % represents "f before modification" % TODO: remove this? \newcommand{\pre}[1]{{ \small `{#1} }} % hook arrows \newcommand{\injects}{ \hookrightarrow } \newcommand{\embeds}{ \hookrightarrow } \newcommand{\surjects}{ \twoheadrightarrow } \newcommand{\projects}{ \twoheadrightarrow } \newcommand{\id}{ \,\mathrm d } % integration d % derivatives: use {\ddn n x y} for (dy/dx) \newcommand{\ddn}[3]{ \frac{ {\mathrm d}^{#1} {#2} }{ {\mathrm d} {#3}^{#1} } } % nth derivative \newcommand{\dd}{ \ddn{} } % first derivative \newcommand{\d}{ \dd{} } % first derivative (no numerator) \newcommand{\dn}[1]{ \ddn{#1}{} } % nth derivative (no numerator) % derivatives: use {\D n x y} for (∂_x y) \newcommand{\Dn}[2]{ \partial^{#1}_{#2} } \newcommand{\D}{ \Dn{} } % no power \newcommand{\ig}[2]{ \int {#2} \, \mathrm d {#1} } % first integral %% category theory %% % category names \newcommand{\cat}[1]{{ \sf{#1} }} % yoneda embedding \newcommand{\yo}{よ} % extra long right-arrows \newcommand{\X}{-\!\!\!-\!\!\!} \newcommand{\xlongrightarrow}{ \mathop{ \, \X\longrightarrow \, } } \newcommand{\xxlongrightarrow}{ \mathop{ \, \X\X\longrightarrow \, } } \newcommand{\xxxlongrightarrow}{ \mathop{ \, \X\X\X\longrightarrow \, } } \newcommand{\takenby}[1]{ \overset{#1}{\rightarrow} } \newcommand{\longtakenby}[1]{ \overset{#1}{\longrightarrow} } \newcommand{\xlongtakenby}[1]{ \overset{#1}{\xlongrightarrow} } \newcommand{\xxlongtakenby}[1]{ \overset{#1}{\xxlongrightarrow} } \newcommand{\xxxlongtakenby}[1]{ \overset{#1}{\xxxlongrightarrow} } % represents an anonymous parameter % eg. $f(\apar)$ usually denotes the function $x \mapsto f(x)$ % TODO: remove this? \newcommand{\apar}{ {-} } %% computability %% % turing machines \newcommand{\halts}{ {\downarrow} } \newcommand{\loops}{ {\uparrow} } n bits of entropy. Given that n %% general %% % shorthands \newcommand{\cl}[1]{ \mathcal{#1} } \newcommand{\sc}[1]{ \mathscr{#1} } \newcommand{\bb}[1]{ \mathbb{#1} } \newcommand{\fk}[1]{ \mathfrak{#1} } \renewcommand{\bf}[1]{ \mathbf{#1} } \renewcommand{\sf}[1]{ \mathsf{#1} } \renewcommand{\rm}[1]{ \mathrm{#1} } \newcommand{\floor}[1]{ { \lfloor {#1} \rfloor } } \newcommand{\ceil}[1]{ { \lceil {#1} \rceil } } \newcommand{\ol}[1]{ \overline{#1} } \newcommand{\t}[1]{ \text{#1} } \newcommand{\norm}[1]{ { \lvert {#1} \rvert } } % norm/magnitude (REMOVE) \newcommand{\mag}[1]{ { \left\lvert {#1} \right\rvert } } % magnitude \newcommand{\smag}[1]{ { \lvert {#1} \rvert } } % short mag \newcommand{\card}{ \t{cd} } % cardinality \newcommand{\dcup}{ \sqcup } % disjoint untion \newcommand{\tup}[1]{ \langle {#1} \rangle } % tuples \newcommand{\tl}{ \tilde } \newcommand{\wt}{ \widetilde } \newcommand{\To}{ \Rightarrow } % draw a box outlining some math \newcommand{\box}[1]{ \fbox{$ #1 $} } % f \onall X = { f(x) : x ∈ X } \newcommand{\onall}[1]{ { \llbracket {#1} \rrbracket } } % shorthands: various brackets \newcommand{\tpar}[1]{ \left( {#1} \right) } % "tall parens" \newcommand{\tbrak}[1]{ \left[ {#1} \right] } % "tall brackets" \newcommand{\tbrac}[1]{ \left\{ {#1} \right\} } % "tall braces" % reverse \mapsto (FIXME: make better) %\newcommand{\mapsfrom}{ \mathop{\leftarrow\!\mid} } \newcommand{\mapsfrom}{ \mathrel{↤} } % reverse-order composition \newcommand{\then}{ \operatorname{\ ;\ } } % Like f' represents "f after modification", \pre{f} % represents "f before modification" % TODO: remove this? \newcommand{\pre}[1]{{ \small `{#1} }} % hook arrows \newcommand{\injects}{ \hookrightarrow } \newcommand{\embeds}{ \hookrightarrow } \newcommand{\surjects}{ \twoheadrightarrow } \newcommand{\projects}{ \twoheadrightarrow } \newcommand{\id}{ \,\mathrm d } % integration d % derivatives: use {\ddn n x y} for (dy/dx) \newcommand{\ddn}[3]{ \frac{ {\mathrm d}^{#1} {#2} }{ {\mathrm d} {#3}^{#1} } } % nth derivative \newcommand{\dd}{ \ddn{} } % first derivative \newcommand{\d}{ \dd{} } % first derivative (no numerator) \newcommand{\dn}[1]{ \ddn{#1}{} } % nth derivative (no numerator) % derivatives: use {\D n x y} for (∂_x y) \newcommand{\Dn}[2]{ \partial^{#1}_{#2} } \newcommand{\D}{ \Dn{} } % no power \newcommand{\ig}[2]{ \int {#2} \, \mathrm d {#1} } % first integral %% category theory %% % category names \newcommand{\cat}[1]{{ \sf{#1} }} % yoneda embedding \newcommand{\yo}{よ} % extra long right-arrows \newcommand{\X}{-\!\!\!-\!\!\!} \newcommand{\xlongrightarrow}{ \mathop{ \, \X\longrightarrow \, } } \newcommand{\xxlongrightarrow}{ \mathop{ \, \X\X\longrightarrow \, } } \newcommand{\xxxlongrightarrow}{ \mathop{ \, \X\X\X\longrightarrow \, } } \newcommand{\takenby}[1]{ \overset{#1}{\rightarrow} } \newcommand{\longtakenby}[1]{ \overset{#1}{\longrightarrow} } \newcommand{\xlongtakenby}[1]{ \overset{#1}{\xlongrightarrow} } \newcommand{\xxlongtakenby}[1]{ \overset{#1}{\xxlongrightarrow} } \newcommand{\xxxlongtakenby}[1]{ \overset{#1}{\xxxlongrightarrow} } % represents an anonymous parameter % eg. $f(\apar)$ usually denotes the function $x \mapsto f(x)$ % TODO: remove this? \newcommand{\apar}{ {-} } %% computability %% % turing machines \newcommand{\halts}{ {\downarrow} } \newcommand{\loops}{ {\uparrow} } n incoming independent random bits have a 2−n %% general %% % shorthands \newcommand{\cl}[1]{ \mathcal{#1} } \newcommand{\sc}[1]{ \mathscr{#1} } \newcommand{\bb}[1]{ \mathbb{#1} } \newcommand{\fk}[1]{ \mathfrak{#1} } \renewcommand{\bf}[1]{ \mathbf{#1} } \renewcommand{\sf}[1]{ \mathsf{#1} } \renewcommand{\rm}[1]{ \mathrm{#1} } \newcommand{\floor}[1]{ { \lfloor {#1} \rfloor } } \newcommand{\ceil}[1]{ { \lceil {#1} \rceil } } \newcommand{\ol}[1]{ \overline{#1} } \newcommand{\t}[1]{ \text{#1} } \newcommand{\norm}[1]{ { \lvert {#1} \rvert } } % norm/magnitude (REMOVE) \newcommand{\mag}[1]{ { \left\lvert {#1} \right\rvert } } % magnitude \newcommand{\smag}[1]{ { \lvert {#1} \rvert } } % short mag \newcommand{\card}{ \t{cd} } % cardinality \newcommand{\dcup}{ \sqcup } % disjoint untion \newcommand{\tup}[1]{ \langle {#1} \rangle } % tuples \newcommand{\tl}{ \tilde } \newcommand{\wt}{ \widetilde } \newcommand{\To}{ \Rightarrow } % draw a box outlining some math \newcommand{\box}[1]{ \fbox{$ #1 $} } % f \onall X = { f(x) : x ∈ X } \newcommand{\onall}[1]{ { \llbracket {#1} \rrbracket } } % shorthands: various brackets \newcommand{\tpar}[1]{ \left( {#1} \right) } % "tall parens" \newcommand{\tbrak}[1]{ \left[ {#1} \right] } % "tall brackets" \newcommand{\tbrac}[1]{ \left\{ {#1} \right\} } % "tall braces" % reverse \mapsto (FIXME: make better) %\newcommand{\mapsfrom}{ \mathop{\leftarrow\!\mid} } \newcommand{\mapsfrom}{ \mathrel{↤} } % reverse-order composition \newcommand{\then}{ \operatorname{\ ;\ } } % Like f' represents "f after modification", \pre{f} % represents "f before modification" % TODO: remove this? \newcommand{\pre}[1]{{ \small `{#1} }} % hook arrows \newcommand{\injects}{ \hookrightarrow } \newcommand{\embeds}{ \hookrightarrow } \newcommand{\surjects}{ \twoheadrightarrow } \newcommand{\projects}{ \twoheadrightarrow } \newcommand{\id}{ \,\mathrm d } % integration d % derivatives: use {\ddn n x y} for (dy/dx) \newcommand{\ddn}[3]{ \frac{ {\mathrm d}^{#1} {#2} }{ {\mathrm d} {#3}^{#1} } } % nth derivative \newcommand{\dd}{ \ddn{} } % first derivative \newcommand{\d}{ \dd{} } % first derivative (no numerator) \newcommand{\dn}[1]{ \ddn{#1}{} } % nth derivative (no numerator) % derivatives: use {\D n x y} for (∂_x y) \newcommand{\Dn}[2]{ \partial^{#1}_{#2} } \newcommand{\D}{ \Dn{} } % no power \newcommand{\ig}[2]{ \int {#2} \, \mathrm d {#1} } % first integral %% category theory %% % category names \newcommand{\cat}[1]{{ \sf{#1} }} % yoneda embedding \newcommand{\yo}{よ} % extra long right-arrows \newcommand{\X}{-\!\!\!-\!\!\!} \newcommand{\xlongrightarrow}{ \mathop{ \, \X\longrightarrow \, } } \newcommand{\xxlongrightarrow}{ \mathop{ \, \X\X\longrightarrow \, } } \newcommand{\xxxlongrightarrow}{ \mathop{ \, \X\X\X\longrightarrow \, } } \newcommand{\takenby}[1]{ \overset{#1}{\rightarrow} } \newcommand{\longtakenby}[1]{ \overset{#1}{\longrightarrow} } \newcommand{\xlongtakenby}[1]{ \overset{#1}{\xlongrightarrow} } \newcommand{\xxlongtakenby}[1]{ \overset{#1}{\xxlongrightarrow} } \newcommand{\xxxlongtakenby}[1]{ \overset{#1}{\xxxlongrightarrow} } % represents an anonymous parameter % eg. $f(\apar)$ usually denotes the function $x \mapsto f(x)$ % TODO: remove this? \newcommand{\apar}{ {-} } %% computability %% % turing machines \newcommand{\halts}{ {\downarrow} } \newcommand{\loops}{ {\uparrow} } 2^{-n} probability for each outcome, this motivates defining self-information to be −log⁡2P(ω) %% general %% % shorthands \newcommand{\cl}[1]{ \mathcal{#1} } \newcommand{\sc}[1]{ \mathscr{#1} } \newcommand{\bb}[1]{ \mathbb{#1} } \newcommand{\fk}[1]{ \mathfrak{#1} } \renewcommand{\bf}[1]{ \mathbf{#1} } \renewcommand{\sf}[1]{ \mathsf{#1} } \renewcommand{\rm}[1]{ \mathrm{#1} } \newcommand{\floor}[1]{ { \lfloor {#1} \rfloor } } \newcommand{\ceil}[1]{ { \lceil {#1} \rceil } } \newcommand{\ol}[1]{ \overline{#1} } \newcommand{\t}[1]{ \text{#1} } \newcommand{\norm}[1]{ { \lvert {#1} \rvert } } % norm/magnitude (REMOVE) \newcommand{\mag}[1]{ { \left\lvert {#1} \right\rvert } } % magnitude \newcommand{\smag}[1]{ { \lvert {#1} \rvert } } % short mag \newcommand{\card}{ \t{cd} } % cardinality \newcommand{\dcup}{ \sqcup } % disjoint untion \newcommand{\tup}[1]{ \langle {#1} \rangle } % tuples \newcommand{\tl}{ \tilde } \newcommand{\wt}{ \widetilde } \newcommand{\To}{ \Rightarrow } % draw a box outlining some math \newcommand{\box}[1]{ \fbox{$ #1 $} } % f \onall X = { f(x) : x ∈ X } \newcommand{\onall}[1]{ { \llbracket {#1} \rrbracket } } % shorthands: various brackets \newcommand{\tpar}[1]{ \left( {#1} \right) } % "tall parens" \newcommand{\tbrak}[1]{ \left[ {#1} \right] } % "tall brackets" \newcommand{\tbrac}[1]{ \left\{ {#1} \right\} } % "tall braces" % reverse \mapsto (FIXME: make better) %\newcommand{\mapsfrom}{ \mathop{\leftarrow\!\mid} } \newcommand{\mapsfrom}{ \mathrel{↤} } % reverse-order composition \newcommand{\then}{ \operatorname{\ ;\ } } % Like f' represents "f after modification", \pre{f} % represents "f before modification" % TODO: remove this? \newcommand{\pre}[1]{{ \small `{#1} }} % hook arrows \newcommand{\injects}{ \hookrightarrow } \newcommand{\embeds}{ \hookrightarrow } \newcommand{\surjects}{ \twoheadrightarrow } \newcommand{\projects}{ \twoheadrightarrow } \newcommand{\id}{ \,\mathrm d } % integration d % derivatives: use {\ddn n x y} for (dy/dx) \newcommand{\ddn}[3]{ \frac{ {\mathrm d}^{#1} {#2} }{ {\mathrm d} {#3}^{#1} } } % nth derivative \newcommand{\dd}{ \ddn{} } % first derivative \newcommand{\d}{ \dd{} } % first derivative (no numerator) \newcommand{\dn}[1]{ \ddn{#1}{} } % nth derivative (no numerator) % derivatives: use {\D n x y} for (∂_x y) \newcommand{\Dn}[2]{ \partial^{#1}_{#2} } \newcommand{\D}{ \Dn{} } % no power \newcommand{\ig}[2]{ \int {#2} \, \mathrm d {#1} } % first integral %% category theory %% % category names \newcommand{\cat}[1]{{ \sf{#1} }} % yoneda embedding \newcommand{\yo}{よ} % extra long right-arrows \newcommand{\X}{-\!\!\!-\!\!\!} \newcommand{\xlongrightarrow}{ \mathop{ \, \X\longrightarrow \, } } \newcommand{\xxlongrightarrow}{ \mathop{ \, \X\X\longrightarrow \, } } \newcommand{\xxxlongrightarrow}{ \mathop{ \, \X\X\X\longrightarrow \, } } \newcommand{\takenby}[1]{ \overset{#1}{\rightarrow} } \newcommand{\longtakenby}[1]{ \overset{#1}{\longrightarrow} } \newcommand{\xlongtakenby}[1]{ \overset{#1}{\xlongrightarrow} } \newcommand{\xxlongtakenby}[1]{ \overset{#1}{\xxlongrightarrow} } \newcommand{\xxxlongtakenby}[1]{ \overset{#1}{\xxxlongrightarrow} } % represents an anonymous parameter % eg. $f(\apar)$ usually denotes the function $x \mapsto f(x)$ % TODO: remove this? \newcommand{\apar}{ {-} } %% computability %% % turing machines \newcommand{\halts}{ {\downarrow} } \newcommand{\loops}{ {\uparrow} } -\log_2{P(\omega)}
Definition: The self-information of some ω∈Ω %% general %% % shorthands \newcommand{\cl}[1]{ \mathcal{#1} } \newcommand{\sc}[1]{ \mathscr{#1} } \newcommand{\bb}[1]{ \mathbb{#1} } \newcommand{\fk}[1]{ \mathfrak{#1} } \renewcommand{\bf}[1]{ \mathbf{#1} } \renewcommand{\sf}[1]{ \mathsf{#1} } \renewcommand{\rm}[1]{ \mathrm{#1} } \newcommand{\floor}[1]{ { \lfloor {#1} \rfloor } } \newcommand{\ceil}[1]{ { \lceil {#1} \rceil } } \newcommand{\ol}[1]{ \overline{#1} } \newcommand{\t}[1]{ \text{#1} } \newcommand{\norm}[1]{ { \lvert {#1} \rvert } } % norm/magnitude (REMOVE) \newcommand{\mag}[1]{ { \left\lvert {#1} \right\rvert } } % magnitude \newcommand{\smag}[1]{ { \lvert {#1} \rvert } } % short mag \newcommand{\card}{ \t{cd} } % cardinality \newcommand{\dcup}{ \sqcup } % disjoint untion \newcommand{\tup}[1]{ \langle {#1} \rangle } % tuples \newcommand{\tl}{ \tilde } \newcommand{\wt}{ \widetilde } \newcommand{\To}{ \Rightarrow } % draw a box outlining some math \newcommand{\box}[1]{ \fbox{$ #1 $} } % f \onall X = { f(x) : x ∈ X } \newcommand{\onall}[1]{ { \llbracket {#1} \rrbracket } } % shorthands: various brackets \newcommand{\tpar}[1]{ \left( {#1} \right) } % "tall parens" \newcommand{\tbrak}[1]{ \left[ {#1} \right] } % "tall brackets" \newcommand{\tbrac}[1]{ \left\{ {#1} \right\} } % "tall braces" % reverse \mapsto (FIXME: make better) %\newcommand{\mapsfrom}{ \mathop{\leftarrow\!\mid} } \newcommand{\mapsfrom}{ \mathrel{↤} } % reverse-order composition \newcommand{\then}{ \operatorname{\ ;\ } } % Like f' represents "f after modification", \pre{f} % represents "f before modification" % TODO: remove this? \newcommand{\pre}[1]{{ \small `{#1} }} % hook arrows \newcommand{\injects}{ \hookrightarrow } \newcommand{\embeds}{ \hookrightarrow } \newcommand{\surjects}{ \twoheadrightarrow } \newcommand{\projects}{ \twoheadrightarrow } \newcommand{\id}{ \,\mathrm d } % integration d % derivatives: use {\ddn n x y} for (dy/dx) \newcommand{\ddn}[3]{ \frac{ {\mathrm d}^{#1} {#2} }{ {\mathrm d} {#3}^{#1} } } % nth derivative \newcommand{\dd}{ \ddn{} } % first derivative \newcommand{\d}{ \dd{} } % first derivative (no numerator) \newcommand{\dn}[1]{ \ddn{#1}{} } % nth derivative (no numerator) % derivatives: use {\D n x y} for (∂_x y) \newcommand{\Dn}[2]{ \partial^{#1}_{#2} } \newcommand{\D}{ \Dn{} } % no power \newcommand{\ig}[2]{ \int {#2} \, \mathrm d {#1} } % first integral %% category theory %% % category names \newcommand{\cat}[1]{{ \sf{#1} }} % yoneda embedding \newcommand{\yo}{よ} % extra long right-arrows \newcommand{\X}{-\!\!\!-\!\!\!} \newcommand{\xlongrightarrow}{ \mathop{ \, \X\longrightarrow \, } } \newcommand{\xxlongrightarrow}{ \mathop{ \, \X\X\longrightarrow \, } } \newcommand{\xxxlongrightarrow}{ \mathop{ \, \X\X\X\longrightarrow \, } } \newcommand{\takenby}[1]{ \overset{#1}{\rightarrow} } \newcommand{\longtakenby}[1]{ \overset{#1}{\longrightarrow} } \newcommand{\xlongtakenby}[1]{ \overset{#1}{\xlongrightarrow} } \newcommand{\xxlongtakenby}[1]{ \overset{#1}{\xxlongrightarrow} } \newcommand{\xxxlongtakenby}[1]{ \overset{#1}{\xxxlongrightarrow} } % represents an anonymous parameter % eg. $f(\apar)$ usually denotes the function $x \mapsto f(x)$ % TODO: remove this? \newcommand{\apar}{ {-} } %% computability %% % turing machines \newcommand{\halts}{ {\downarrow} } \newcommand{\loops}{ {\uparrow} } \omega \in \Omega is defined to be I(ω):=−log⁡2(P(ω)) %% general %% % shorthands \newcommand{\cl}[1]{ \mathcal{#1} } \newcommand{\sc}[1]{ \mathscr{#1} } \newcommand{\bb}[1]{ \mathbb{#1} } \newcommand{\fk}[1]{ \mathfrak{#1} } \renewcommand{\bf}[1]{ \mathbf{#1} } \renewcommand{\sf}[1]{ \mathsf{#1} } \renewcommand{\rm}[1]{ \mathrm{#1} } \newcommand{\floor}[1]{ { \lfloor {#1} \rfloor } } \newcommand{\ceil}[1]{ { \lceil {#1} \rceil } } \newcommand{\ol}[1]{ \overline{#1} } \newcommand{\t}[1]{ \text{#1} } \newcommand{\norm}[1]{ { \lvert {#1} \rvert } } % norm/magnitude (REMOVE) \newcommand{\mag}[1]{ { \left\lvert {#1} \right\rvert } } % magnitude \newcommand{\smag}[1]{ { \lvert {#1} \rvert } } % short mag \newcommand{\card}{ \t{cd} } % cardinality \newcommand{\dcup}{ \sqcup } % disjoint untion \newcommand{\tup}[1]{ \langle {#1} \rangle } % tuples \newcommand{\tl}{ \tilde } \newcommand{\wt}{ \widetilde } \newcommand{\To}{ \Rightarrow } % draw a box outlining some math \newcommand{\box}[1]{ \fbox{$ #1 $} } % f \onall X = { f(x) : x ∈ X } \newcommand{\onall}[1]{ { \llbracket {#1} \rrbracket } } % shorthands: various brackets \newcommand{\tpar}[1]{ \left( {#1} \right) } % "tall parens" \newcommand{\tbrak}[1]{ \left[ {#1} \right] } % "tall brackets" \newcommand{\tbrac}[1]{ \left\{ {#1} \right\} } % "tall braces" % reverse \mapsto (FIXME: make better) %\newcommand{\mapsfrom}{ \mathop{\leftarrow\!\mid} } \newcommand{\mapsfrom}{ \mathrel{↤} } % reverse-order composition \newcommand{\then}{ \operatorname{\ ;\ } } % Like f' represents "f after modification", \pre{f} % represents "f before modification" % TODO: remove this? \newcommand{\pre}[1]{{ \small `{#1} }} % hook arrows \newcommand{\injects}{ \hookrightarrow } \newcommand{\embeds}{ \hookrightarrow } \newcommand{\surjects}{ \twoheadrightarrow } \newcommand{\projects}{ \twoheadrightarrow } \newcommand{\id}{ \,\mathrm d } % integration d % derivatives: use {\ddn n x y} for (dy/dx) \newcommand{\ddn}[3]{ \frac{ {\mathrm d}^{#1} {#2} }{ {\mathrm d} {#3}^{#1} } } % nth derivative \newcommand{\dd}{ \ddn{} } % first derivative \newcommand{\d}{ \dd{} } % first derivative (no numerator) \newcommand{\dn}[1]{ \ddn{#1}{} } % nth derivative (no numerator) % derivatives: use {\D n x y} for (∂_x y) \newcommand{\Dn}[2]{ \partial^{#1}_{#2} } \newcommand{\D}{ \Dn{} } % no power \newcommand{\ig}[2]{ \int {#2} \, \mathrm d {#1} } % first integral %% category theory %% % category names \newcommand{\cat}[1]{{ \sf{#1} }} % yoneda embedding \newcommand{\yo}{よ} % extra long right-arrows \newcommand{\X}{-\!\!\!-\!\!\!} \newcommand{\xlongrightarrow}{ \mathop{ \, \X\longrightarrow \, } } \newcommand{\xxlongrightarrow}{ \mathop{ \, \X\X\longrightarrow \, } } \newcommand{\xxxlongrightarrow}{ \mathop{ \, \X\X\X\longrightarrow \, } } \newcommand{\takenby}[1]{ \overset{#1}{\rightarrow} } \newcommand{\longtakenby}[1]{ \overset{#1}{\longrightarrow} } \newcommand{\xlongtakenby}[1]{ \overset{#1}{\xlongrightarrow} } \newcommand{\xxlongtakenby}[1]{ \overset{#1}{\xxlongrightarrow} } \newcommand{\xxxlongtakenby}[1]{ \overset{#1}{\xxxlongrightarrow} } % represents an anonymous parameter % eg. $f(\apar)$ usually denotes the function $x \mapsto f(x)$ % TODO: remove this? \newcommand{\apar}{ {-} } %% computability %% % turing machines \newcommand{\halts}{ {\downarrow} } \newcommand{\loops}{ {\uparrow} } I(\omega) := -\log_2(P(\omega)). (The unit is bits) For two random variables X,Y %% general %% % shorthands \newcommand{\cl}[1]{ \mathcal{#1} } \newcommand{\sc}[1]{ \mathscr{#1} } \newcommand{\bb}[1]{ \mathbb{#1} } \newcommand{\fk}[1]{ \mathfrak{#1} } \renewcommand{\bf}[1]{ \mathbf{#1} } \renewcommand{\sf}[1]{ \mathsf{#1} } \renewcommand{\rm}[1]{ \mathrm{#1} } \newcommand{\floor}[1]{ { \lfloor {#1} \rfloor } } \newcommand{\ceil}[1]{ { \lceil {#1} \rceil } } \newcommand{\ol}[1]{ \overline{#1} } \newcommand{\t}[1]{ \text{#1} } \newcommand{\norm}[1]{ { \lvert {#1} \rvert } } % norm/magnitude (REMOVE) \newcommand{\mag}[1]{ { \left\lvert {#1} \right\rvert } } % magnitude \newcommand{\smag}[1]{ { \lvert {#1} \rvert } } % short mag \newcommand{\card}{ \t{cd} } % cardinality \newcommand{\dcup}{ \sqcup } % disjoint untion \newcommand{\tup}[1]{ \langle {#1} \rangle } % tuples \newcommand{\tl}{ \tilde } \newcommand{\wt}{ \widetilde } \newcommand{\To}{ \Rightarrow } % draw a box outlining some math \newcommand{\box}[1]{ \fbox{$ #1 $} } % f \onall X = { f(x) : x ∈ X } \newcommand{\onall}[1]{ { \llbracket {#1} \rrbracket } } % shorthands: various brackets \newcommand{\tpar}[1]{ \left( {#1} \right) } % "tall parens" \newcommand{\tbrak}[1]{ \left[ {#1} \right] } % "tall brackets" \newcommand{\tbrac}[1]{ \left\{ {#1} \right\} } % "tall braces" % reverse \mapsto (FIXME: make better) %\newcommand{\mapsfrom}{ \mathop{\leftarrow\!\mid} } \newcommand{\mapsfrom}{ \mathrel{↤} } % reverse-order composition \newcommand{\then}{ \operatorname{\ ;\ } } % Like f' represents "f after modification", \pre{f} % represents "f before modification" % TODO: remove this? \newcommand{\pre}[1]{{ \small `{#1} }} % hook arrows \newcommand{\injects}{ \hookrightarrow } \newcommand{\embeds}{ \hookrightarrow } \newcommand{\surjects}{ \twoheadrightarrow } \newcommand{\projects}{ \twoheadrightarrow } \newcommand{\id}{ \,\mathrm d } % integration d % derivatives: use {\ddn n x y} for (dy/dx) \newcommand{\ddn}[3]{ \frac{ {\mathrm d}^{#1} {#2} }{ {\mathrm d} {#3}^{#1} } } % nth derivative \newcommand{\dd}{ \ddn{} } % first derivative \newcommand{\d}{ \dd{} } % first derivative (no numerator) \newcommand{\dn}[1]{ \ddn{#1}{} } % nth derivative (no numerator) % derivatives: use {\D n x y} for (∂_x y) \newcommand{\Dn}[2]{ \partial^{#1}_{#2} } \newcommand{\D}{ \Dn{} } % no power \newcommand{\ig}[2]{ \int {#2} \, \mathrm d {#1} } % first integral %% category theory %% % category names \newcommand{\cat}[1]{{ \sf{#1} }} % yoneda embedding \newcommand{\yo}{よ} % extra long right-arrows \newcommand{\X}{-\!\!\!-\!\!\!} \newcommand{\xlongrightarrow}{ \mathop{ \, \X\longrightarrow \, } } \newcommand{\xxlongrightarrow}{ \mathop{ \, \X\X\longrightarrow \, } } \newcommand{\xxxlongrightarrow}{ \mathop{ \, \X\X\X\longrightarrow \, } } \newcommand{\takenby}[1]{ \overset{#1}{\rightarrow} } \newcommand{\longtakenby}[1]{ \overset{#1}{\longrightarrow} } \newcommand{\xlongtakenby}[1]{ \overset{#1}{\xlongrightarrow} } \newcommand{\xxlongtakenby}[1]{ \overset{#1}{\xxlongrightarrow} } \newcommand{\xxxlongtakenby}[1]{ \overset{#1}{\xxxlongrightarrow} } % represents an anonymous parameter % eg. $f(\apar)$ usually denotes the function $x \mapsto f(x)$ % TODO: remove this? \newcommand{\apar}{ {-} } %% computability %% % turing machines \newcommand{\halts}{ {\downarrow} } \newcommand{\loops}{ {\uparrow} } X, Y, we define I(X∣Y):=H(X)−H(X∣Y) %% general %% % shorthands \newcommand{\cl}[1]{ \mathcal{#1} } \newcommand{\sc}[1]{ \mathscr{#1} } \newcommand{\bb}[1]{ \mathbb{#1} } \newcommand{\fk}[1]{ \mathfrak{#1} } \renewcommand{\bf}[1]{ \mathbf{#1} } \renewcommand{\sf}[1]{ \mathsf{#1} } \renewcommand{\rm}[1]{ \mathrm{#1} } \newcommand{\floor}[1]{ { \lfloor {#1} \rfloor } } \newcommand{\ceil}[1]{ { \lceil {#1} \rceil } } \newcommand{\ol}[1]{ \overline{#1} } \newcommand{\t}[1]{ \text{#1} } \newcommand{\norm}[1]{ { \lvert {#1} \rvert } } % norm/magnitude (REMOVE) \newcommand{\mag}[1]{ { \left\lvert {#1} \right\rvert } } % magnitude \newcommand{\smag}[1]{ { \lvert {#1} \rvert } } % short mag \newcommand{\card}{ \t{cd} } % cardinality \newcommand{\dcup}{ \sqcup } % disjoint untion \newcommand{\tup}[1]{ \langle {#1} \rangle } % tuples \newcommand{\tl}{ \tilde } \newcommand{\wt}{ \widetilde } \newcommand{\To}{ \Rightarrow } % draw a box outlining some math \newcommand{\box}[1]{ \fbox{$ #1 $} } % f \onall X = { f(x) : x ∈ X } \newcommand{\onall}[1]{ { \llbracket {#1} \rrbracket } } % shorthands: various brackets \newcommand{\tpar}[1]{ \left( {#1} \right) } % "tall parens" \newcommand{\tbrak}[1]{ \left[ {#1} \right] } % "tall brackets" \newcommand{\tbrac}[1]{ \left\{ {#1} \right\} } % "tall braces" % reverse \mapsto (FIXME: make better) %\newcommand{\mapsfrom}{ \mathop{\leftarrow\!\mid} } \newcommand{\mapsfrom}{ \mathrel{↤} } % reverse-order composition \newcommand{\then}{ \operatorname{\ ;\ } } % Like f' represents "f after modification", \pre{f} % represents "f before modification" % TODO: remove this? \newcommand{\pre}[1]{{ \small `{#1} }} % hook arrows \newcommand{\injects}{ \hookrightarrow } \newcommand{\embeds}{ \hookrightarrow } \newcommand{\surjects}{ \twoheadrightarrow } \newcommand{\projects}{ \twoheadrightarrow } \newcommand{\id}{ \,\mathrm d } % integration d % derivatives: use {\ddn n x y} for (dy/dx) \newcommand{\ddn}[3]{ \frac{ {\mathrm d}^{#1} {#2} }{ {\mathrm d} {#3}^{#1} } } % nth derivative \newcommand{\dd}{ \ddn{} } % first derivative \newcommand{\d}{ \dd{} } % first derivative (no numerator) \newcommand{\dn}[1]{ \ddn{#1}{} } % nth derivative (no numerator) % derivatives: use {\D n x y} for (∂_x y) \newcommand{\Dn}[2]{ \partial^{#1}_{#2} } \newcommand{\D}{ \Dn{} } % no power \newcommand{\ig}[2]{ \int {#2} \, \mathrm d {#1} } % first integral %% category theory %% % category names \newcommand{\cat}[1]{{ \sf{#1} }} % yoneda embedding \newcommand{\yo}{よ} % extra long right-arrows \newcommand{\X}{-\!\!\!-\!\!\!} \newcommand{\xlongrightarrow}{ \mathop{ \, \X\longrightarrow \, } } \newcommand{\xxlongrightarrow}{ \mathop{ \, \X\X\longrightarrow \, } } \newcommand{\xxxlongrightarrow}{ \mathop{ \, \X\X\X\longrightarrow \, } } \newcommand{\takenby}[1]{ \overset{#1}{\rightarrow} } \newcommand{\longtakenby}[1]{ \overset{#1}{\longrightarrow} } \newcommand{\xlongtakenby}[1]{ \overset{#1}{\xlongrightarrow} } \newcommand{\xxlongtakenby}[1]{ \overset{#1}{\xxlongrightarrow} } \newcommand{\xxxlongtakenby}[1]{ \overset{#1}{\xxxlongrightarrow} } % represents an anonymous parameter % eg. $f(\apar)$ usually denotes the function $x \mapsto f(x)$ % TODO: remove this? \newcommand{\apar}{ {-} } %% computability %% % turing machines \newcommand{\halts}{ {\downarrow} } \newcommand{\loops}{ {\uparrow} } I(X \mid Y) := H(X) - H(X \mid Y)