The following is a heuristic for the situation where a decision algorithm or a human, might solve a problem by reducing the entropy of the "search space" at every computation step $i$:


Let $X\_{i+1} \subset X\_i$ for $i = 1,\cdots,t-1$ be finite subsets contained all in a finite set $X\_1$.


We assume that there are given functions $f\_i: X\_i \rightarrow X\_{i+1}$ which are surjective and also we assume that $|X\_{i}| > |X\_{i+1}|$.
In each step $i=1,\cdots,t-1$ we might define an entropy ([the idea is borrowed from David Ellerman](http://philsci-archive.pitt.edu/13213/1/Logic-to-information-theory3.pdf)):


$$H\_{f\_i}:=H\_{i} := - \sum\_{x \in X\_{i+1}} \frac{|f\_i^{-1}(x)|}{|X\_i|} \log\_2\left[\frac{|f\_i^{-1}(x)|}{|X\_i|}\right].$$


We can also consider the function $\hat{f} = f\_t \circ f\_{t-1} \circ \cdots f\_2 \circ f\_1$ which maps from $X\_1$ to $X\_t$.
and consider the corresponding entropy:


$$\hat{H} = H\_{\hat{f}}$$


My question is, if it can be proved that: $H\_i \ge \hat{H}$ and $H\_i \ge H\_{i+1}$?


I did a few small [experiments in Sagemath](https://sagecell.sagemath.org/?z=eJzdU8tugzAQvCPxD5ZysSmkIX0qau703AsR4kCDHbkFg2yIkr_vrjENNPmC-mDZs7O7s2OQddvojqi-bs-kMES1vldyQaT56PUX33fyyKkI03DHNr5HYFUp2ZKKK5qyARDv6ghQKfcdzXIHLsi-qdu-40SqI9eGE9ErqNYoV0Y0mpwgSFIH4DpDHUFP7IJIASCwsMnym58NZRP-2D4758uiLGeZvDL8NhWaGA5aT6NYzbteK1JUFb3qZoVacMfGOpeqg1mJ-PcWJYBEpq9phnM5Fruv0kC1y6o50D_w1DcAHGk9NzyZ9_a9wU5R0nIcwTGrov4sC3LakMMeZghLhuSFMgR0ZevgIXgKXoI4Du0R93Cd-x7EbTh4BSh4xg2DwSNua0sBEnCUyVa5e9DhGsUQFGg2qvG91L7fUZpGG6oA2E0BZCTo0e-n4HutlqqjSWKlJhKCK6gIrkh0RRfqwK1ryrAoHud1YmQ-XJ0YeRc7YKIIr1eqELxShuCg5sZvPT6wbOO5_klWiNEQOBEe3rZ2qCELcwD7ASWMFSw=&lang=sage&interacts=eJyLjgUAARUAuQ==) with divisor sets, but although it seems that the answer is yes, I have no idea if it is true or how it can be proved.


Thanks for your help.



Entropy reduction?
Suppose $X\_1=\{1,\dots,m+n\}$, where $m,n\to\infty$ and $\frac mn\,\log\_2 n\to0$. Suppose that $f\_1(x)=x$ for $x\in\{1,\dots,m\}$ and $f\_1(x)=m+1$ for $x\in\{m+1,\dots,m+n\}$, so that $X\_2=\{1,\dots,m+1\}$. Suppose also that $f\_2(x)=x$ for $x\in\{1,\dots,m-1\}$ and $f\_2(x)=m$ for $x\in\{m,m+1\}$. Then
$$H\_1=\frac n{n+m}\,\log\_2\frac{n+m}n
+m\frac 1{n+m}\,\log\_2\frac{n+m}1\to0,$$
whereas
$$H\_2=\frac2{m+1}\,\log\_2\frac{m+1}2
+(m-1)\frac 1{m+1}\,\log\_2\frac{m+1}1\to\infty,$$
so that $H\_i\not\ge H\_{i+1}$ for $i=1$.




---


However, letting $\hat f\_s:=f\_s\circ \cdots\circ f\_1$, we of course will have
$$H\_{\hat f\_s}\ge H\_{\hat f\_{s+1}} $$
for all $s=1,2,\dots$.


This follows because $l(p):=-p\log\_2 p$ (with $l(0):=0$) is concave in $p\in[0,1]$, so that $l(p+q)\le l(p)+l(q)$ if $0\le q\le1-p\le1$.


