On this episode of our podcast My Favorite Theorem, my cohost Kevin Knudson and I were happy to talk with Suresh Venkatasubramanian, who is in the computer science department at the University of Utah. You can listen here or at kpknudson.com, where there is also a transcript.

Dr. Venkatasubramanian likes to describe himself as a bias detective or computational philosopher. One of the main focuses of his work in the past few years has been on algorithmic bias, the idea that algorithms can reinforce human prejudices. I talked with him for an article I wrote about algorithmic bias for the children’s science magazine Muse, which is also available here, and you can find one of his recent papers about algorithmic fairness here. He chose to talk about Fano’s inequality, which is important to his work but has applications much more broadly in computer science and statistics.

Fano’s inequality begins as all good stories do, Dr. Venkatasubramanian says, with pigeons. Specifically, the pigeonhole principle, the intuitively obvious fact that if the number of pigeonholes is smaller than the number of pigeons you have, at least two pigeons will share one pigeonhole. He describes the way the pigeonhole principle forms the foundation for several other observations that underlie many lower bounds in computer science, including Fano’s inequality. (In computer science, a common goal is to find a lower bound for the number of steps in an algorithm: is there a theoretical minimum amount of time it can take?)

Fano’s inequality is about the amount of entropy, or uncertainty, in a relationship between two variables. Dr. Venkatasubramanian used the example of American Caucasian names and genders. Few if any people named Nancy are men, and few if any people named David are women, but there are fair numbers of both men and women (and people of other genders) named Dylan. So if an algorithm wants to predict a person’s gender based on their name, it is more likely to get it right if the name is Nancy or David than if it is Dylan. Fano’s inequality makes that, again intuitively obvious, observation precise. It puts limits on how accurately an algorithm can predict a variable x based on a variable y, based on the uncertainty in the function that associates those two variables. For more details on Fano’s inequality, see Dr. Venkatasubramanian’s post about it here. A more advanced introduction, by Bin Yu, is here (pdf).

In each episode of the podcast, we ask our guest to pair their theorem with food, beverage, art, music, or any delight in life. Dr. Venkatasubramanian picked goat cheese and jalapeño jelly. You’ll have to listen to the episode to find out why it’s the perfect accompaniment for Fano’s inequality. (For those who want to see the hot pepper-eating orchestra I mention in the episode, the video is here. But why would you want that?)