Special Case of Bernoulli Random Variables
Hoeffding's inequality can be applied to the important special case of identically distributed Bernoulli random variables, and this is how the inequality is often used in combinatorics and computer science. We consider a biased coin that shows heads with probability and tails with probability . We toss the coin times. The expected number of times the coin comes up heads is . Furthermore, the probability that the coin comes up heads at most times can be exactly quantified by the following expression:
In the case that for some, Hoeffding's inequality bounds this probability by a term that is exponentially small in :
Similarly, in the case that for some, Hoeffding's inequality bounds the probability that we see at least more tosses that show heads than we would expect:
Hence Hoeffding's inequality implies that the number of heads that we see is concentrated around its mean, with exponentially small tail.
Read more about this topic: Hoeffding's Inequality
Famous quotes containing the words special, case, random and/or variables:
“Friendship is learned by watching and listening to you. If she sees that your friends are people you like and trust and don’t pretend with—people who suit you—she probably won’t pick friends who just pass by, or people who can help her or improve her status. If you treat friends in a special way, if you are kinder, more generous, more sympathetic, more forgiving with friends, she probably will be, too.”
—Stella Chess (20th century)
“The function of muscle is to pull and not to push, except in the case of the genitals and the tongue.”
—Leonardo Da Vinci (1425–1519)
“There is a potential 4-6 percentage point net gain for the President [George Bush] by replacing Dan Quayle on the ticket with someone of neutral stature.”
—Mary Matalin, U.S. Republican political advisor, author, and James Carville b. 1946, U.S. Democratic political advisor, author. All’s Fair: Love, War, and Running for President, p. 205, Random House (1994)
“The variables of quantification, ‘something,’ ‘nothing,’ ‘everything,’ range over our whole ontology, whatever it may be; and we are convicted of a particular ontological presupposition if, and only if, the alleged presuppositum has to be reckoned among the entities over which our variables range in order to render one of our affirmations true.”
—Willard Van Orman Quine (b. 1908)