Information Theory

By Prof. Himanshu Tyagi | IISc Bangalore

Learners enrolled: 1971

This is a graduate level introductory course in Information Theory where we will introduce the mathematical notion of information and justify it by various operational meanings. This basic theory builds on probability theory and allows us to quantitatively measure the uncertainty and randomnessin a random variable as well as information revealed on observing its value. We will encounter quantities such as entropy, mutual information, total variation distance, and KL divergence and explain how they play a role in important problems in communication, statistics, and computer science.Information theory was originally invented as a mathematical theory of communication, but has since found applications in many areas ranging from physics to biology. In fact, any field where people want to evaluate how much information about an unknown is revealed by a particular experiment, information theory can help. In this course, we will lay down the foundations of this fundamental field.

INTENDED AUDIENCE : Senior undergraduate and graduate students interested in probability, statistics, communication, theoretical computer science, machine learning, quantum information and statistical physics

PREREQUISITES : Undergraduate level probability (sets and events, probability distributions, probability density functions, probability mass functions, random variables, expected value, variance, popular probability laws, Markov inequality, Chebyshev in equality, central limit theorem, law of large numbers)

INDUSTRIES SUPPORT : None

Summary

Course Status :	Completed
Course Type :	Elective
Duration :	12 weeks
Category :	Electrical, Electronics and Communications Engineering Communication and Signal Processing
Credit Points :	3
Level :	Undergraduate/Postgraduate
Start Date :	14 Sep 2020
End Date :	04 Dec 2020
Enrollment Ends :	25 Sep 2020
Exam Date :	20 Dec 2020 IST

Note: This exam date is subjected to change based on seat availability. You can check final exam date on your hall ticket.

Page Visits

Course layout

This course is organised into multiple units. While I have tried my best to align units to weeks, but sometimes we will cover parts of multiple units in the same week. We will provide

Week 1: (Unit 1) Information and probabilistic modelling: information, uncertainty, basic concepts of probability, Markov inequality, limit theorems
Week 2: (Unit 2) Uncertainty, compression, and entropy: source model, motivating examples, a compression problem, Shannon entropy, random hash
Week 3: (Unit 3) Randomness and entropy: uncertainty and randomness, Total variation distance, generating uniform bits, generating from uniform bits, typicak sets and entropy
Week 4: (Unit 4)  Information and statistical inference-1: Hypothesis testing and estimation, examples, the log-likelihood ratio test, Kullback-Leibler divergence and Stein's lemma, properties of KL divergence
Week 5: (Unit 5)  Information and statistical inference-2: Information per coin toss, multiple hypothesis testing, mutual information, Fano's inequality
Week 6: (Unit 6)  Properties of measures of information-1: Definitions, chain rule, shape of information functions (boundedness, concavity/convexity, non negativity), data processing inequality
Week 7: (Unit 7)  Properties of measures of information-2: Proof of Fano's inequality, variational formulae, capacity as information radius, proof of Pinsker's inequality, continuity of entropy; (Unit 8) Information theoretic lower bounds: Lower bound for source coding, lower bound for Stein's lemma
Week 8: (Unit 8 continued) lower bound for randomness generation, strong converse, lower bound for minmax estimation; (Unit 9) Compression 1: Variable length source codes

Week 9-12: We will post the exact plan soon. Basically, we will cover compression, channel coding, and quantisation in the remaining 4 weeks.

Books and references

1. T. Cover and J. Thomas, Elements of Information Theory, Second edition, Wiley, 2006

2. I. Csiszar and J. Korner, Information Theory: Coding Theorems for Discrete Memoryless Systems, Second edition, Cambridge, 2011.

3. T. S. Han, Information spectrum methods in Information Theory, Stochastic Modeling and Applied Probability series, Springer, 2003.

4. J. Wolfowitz, Coding Theorems of Information Theory, Probability Theory and Stochastic Processes series, Springer, 1978.

5. A. Khinchin, Mathematical foundations of information theory, Dover,2001 edition.

Instructor bio

Prof. Himanshu Tyagi

IISc Bangalore

Assistant Professor Department of Electrical Communication Engineering Participating Faculty Robert Bosch Center for Cyber Physical Systems Member Faculty Analysis and Probability Research Group (APRG)

Course certificate

•The course is free to enroll and learn from. But if you want a certificate, you have to register and write the proctored exam conducted by us in person at any of the designated exam centres.
•The exam is optional for a fee of Rs 1000/- (Rupees one thousand only).
• Date and Time of Exams: 20 December 2020, Morning session 9am to 12 noon; Afternoon Session 2pm to 5pm.
•Registration url: Announcements will be made when the registration form is open for registrations.
• The online registration form has to be filled and the certification exam fee needs to be paid. More details will be made available when the exam registration form is published. If there are any changes, it will be mentioned then.
•Please check the form for more details on the cities where the exams will be held, the conditions you agree to when you fill the form etc.

CRITERIA TO GET A CERTIFICATE:
• Average assignment score = 25% of average of best 8 assignments out of the total 12 assignments given in the course.
• Exam score = 75% of the proctored certification exam score out of 100
•Final score = Average assignment score + Exam score

YOU WILL BE ELIGIBLE FOR A CERTIFICATE ONLY IF AVERAGE ASSIGNMENT SCORE >=10/25 AND EXAM SCORE >= 30/75.
•If one of the 2 criteria is not met, you will not get the certificate even if the Final score >= 40/100.
• Certificate will have your name, photograph and the score in the final exam with the breakup.It will have the logos of NPTEL and IISc Bangalore. It will be e-verifiable at nptel.ac.in/noc
•Only the e-certificate will be made available. Hard copies will not be dispatched.

SWAYAM Helpline / Support