Camille Brugel matovitch

Information theory for pure math undergraduates

This text aims at intuitively explaining and proving the main definitions and theorems of Shannon's information theory with limited prerequisites; this includes: cross/conditional entropy, KL-divergence, mutual information, asymptotic codelength property, source and channel coding theorems . The target audience is "undergraduates or strong high school students" but I might throw in some non-essential notes for the more advanced reader. :)

Find the coin

As a formalist, I would like to introduce the subject with a small game...

A coin is hidden among four opaque cups. At each round, we ask yes/no questions to uncover the cup concealing the coin. Multiple rounds are played and we aim to minimize the number of questions asked.

	from __future__ import annotations
	from typing import List, Set, Tuple, Dict, Any
	from dataclasses import dataclass
	from enum import Enum
	import numpy as np
	from collections import deque
	import sys
	import time

	class State(Enum):

	#include <iostream>
	#include <iomanip>
	#include <chrono>

	// Use it with \| sort -n \| grep -P 'CLK[01]'

	namespace
	{
	void displayDuration(const std::chrono::nanoseconds duration)
	{

	#include <iostream>
	#include <cstdint>
	#include <vector>
	#include <queue>
	#include <list>

	template <class SizeType, uint8_t MIN_LOG_INDEX, uint8_t BALANCE_LOG_RATIO, class Type>
	struct TIndexedList
	{
	using Iterator = typename std::list<Type>::iterator;

	What is math concretely?

	From the outside, it resembles a group of people talking to each other. The theme of the discussion loosely depends on what was said before and no one really knows how it all started.

	You can join in if you want but you will need to speak some dialect first. An implicit algorithm is used such that the people can agree on the validity of what is being said.

	Some people have started to translate the discussion from the original set of evolving dialects into programming languages. In this new setting, the implicit algorithm can be made explicit and the translation checked mechanically. If no mistake is found in the algorithm or in the translation, we can be confident that what was said is indeed valid.

	Given such an explicit algorithm and a complete enough record of the discussion, we could store a full verified translation. But this translation would be fairly redundant and we could try to compress it. Doing so, we would see that the bytes with the highest compression ratio would ma

	{
	"node": "Program",
	"functions": [
	{
	"node": "Function",
	"name": {
	"node": "Identifier",
	"lexeme": {
	"node": "Lexeme",
	"index": 42

	#include <iostream>

	#include <vector>

	namespace node
	{

	enum class Kind
	{
	PROGRAM,

	#include <iostream>

	namespace type_flag
	{

	template <class TypeFlag, class Type>
	using THas = std::enable_if_t<std::is_base_of_v <TypeFlag, std::decay_t<Type>>, int>;

	template <class TypeFlag, class Type>
	using THasNot = std::enable_if_t<std::negation_v<std::is_base_of<TypeFlag, std::decay_t<Type>>>, int>;

	#include <algorithm>
	#include <iostream>
	#include <cstdint>
	#include <vector>
	#include <array>

	constexpr int log2(int x)
	{
	return x < 2 ? x : 1 + log2(x >> 1);
	}