# Tag Info

2

Use Jensen's inequality with $f(t) = \log t$. $$H(X) = \sum_{i=1}^n p_i \log \frac{1}{p_i}\leq \log\left(\sum_{i=1}^n p_i \frac{1}{p_i}\right) = \log n$$ $\log t$ is strictly concave, so equality requires $p_i = 1/n$, for all $i$, (in other words, a uniform distribution).

1

Consider $e^{H(x)} = \prod (\frac{1}{p_i})^{p_i}$ By weighted AM-GM Inequality $\prod (\frac{1}{p_i})^{p_i} \leq \sum \frac{1}{p_i} \times p_i$ $\implies$ $\prod (\frac{1}{p_i})^{p_i} \leq n$ For the equality to hold $\frac{1}{p_i} = \frac{1}{p_j}$ for any $i,j$ And hence $$p_i=\frac{1}{n}$$

1

This can be solved numerically as a Markov Chain with an absorbing state (all limes picked). Assuming that at each step one has $0<x_t<n$ limes, and a number of those limes are dropped (according to a Binomial with $p=g(x)$) and a lime is picked (and hence one is always holding at least one lime), an example for $n=6$ and $p = x/24$ (arbitrary), one ...

1

Hint: You can come up with a recurrence for the expected waiting time assuming you have $m$ limes, in terms of the expected waiting time when you have $m' < m$ limes for all $m'$. $E(t) = n$ will not have a finite solution for the expected number of limes held at time $t$ because at any point in time there is always a chance you will have less than $n$ ...

1

This is just using the fact that $\log(a\cdot b) = \log a + \log b$ (true for any particular base of the logarithm). Stated more generally, it becomes $\log \prod_{\alpha}x_{\alpha} = \sum_{\alpha}\log x_{\alpha}$. That particular law of logarithms is a restatement of the fact that $x^u\cdot x^v = x^{u+v}$.

1

Entropy $H$ as stated is per source symbol. A source output of $n$ symbols has entropy $nH$. Note that the Theorem on p. 15 states that you're encoding a message of length $n.$

1

"Given a set of known statements one could define the difficulty of a theorem as the minimum length among all its proofs deduced from known statements. One could also define the importance of a theorem T in a set of statements as the inverse of the sum of the difficulty of all the remaining theorems known T." In even axiomatic propositional calculi it's ...

1

"Channel codes - Classical and Modern" by William E. Ryan and Shu Lin should be a great place to learn about both linear codes and LDPC codes in particular as the book devotes a huge part to the latter topic with a self-contained introduction to the former.

Only top voted, non community-wiki answers of a minimum length are eligible