Talk:Azuma's inequality

Hi, Steve notes that the 1963 JASA paper of Hoeffding is for independent random variables. This is just part of the story. The theorem in the paper is stated for independent random variables, but Hoeffding later comments in the text of the paper that the same argument applies to martingales --- and this is absolutely true. I have quoted "Azuma's inequality" in many papers, but I would not do so now. For years now, I have simply said "Hoeffding's inequality" and I would encourage others to do the same. Azuma's discovery was surely independent, but it was redundant at the time of publication. This happens all the time --- but not so often to stuff that is so important.

It's actually not easy to find Azuma's paper (Princeton has it), but you can snap Hoeffding off of JSTOR any day of the week --- and it is a gem.

Mike Steele (I have forgotten how to sign my post --- but this is me!) —Preceding unsigned comment added by 64.105.108.90 (talk) 21:24, 6 October 2007 (UTC)

This extremely important inequality was discovered independently by Hoffding and Azuma, and in fact Hoffding published it ten years earlier than Azuma did. Therefore a more accurate name would be the Azuma-Hoffding inequality. —The preceding unsigned comment was added by 128.97.4.100 (talk • contribs) 18:03, 1 May 2006 (UTC).

If so can someone add the actual references please? Jmath666 05:26, 25 March 2007 (UTC)

Hi.

The version by Hoeffding was derived for sums of independent random variables rather than martingales, in 1963. The reference is on the Hoeffding's inequality page. In statistical learning, the theorem is often referred to as the Hoeffding-Azuma inequality. --Steve Kroon 11:41, 25 March 2007 (UTC)

Merge with Hoeffding's inequality

I feel these articles shouldn't be merged: Hoeffding's inequality is tighter than the Azuma-Hoeffding inequality, at the price of a stronger assumption (independence). I think the two articles should reference each other, and leave it at that. --Steve Kroon 05:38, 30 March 2007 (UTC)

I second that. If your variables are not independent, then you can't use Hoeffding's inequality, hence those inequalities are different. In a search, an user wishing to employ techniques for dependent variables is less likely to select a page with "Hoeffding inequality" in the title. I know because I came here that way. 213.41.133.220 08:45, 1 July 2007 (UTC)

I would add the following argument against merging: The language required to understand the Azuma-Hoeffding result is much more sophisticated (ie, martingales) than the one used for Hoeffding's. Therefore, that result would be accessible to more people if left in its current formulation. Still, I've added a link to Azuma in the See also sectiono of Hoeffding. 189.136.147.43 15:50, 27 August 2007 (UTC)

A slightly better version?

The current version Azuma's inequality does not generalize Hoeffding's inequality for sum of zero-mean independent variables. The problem is the assumption that k-th increment lies in interval $[-c_{k},c_{k}]$. There is no reason for the interval to be symmetric. (In Hoeffding's inequality, the interval is allowed to be asymmetric and only its length matters.) A more general version of Azuma is that k-th increment lies in interval $[A_{k},A_{k}+c_{k}]$ where $A_{k}$ depends on $X_{1},X_{2},\ldots ,X_{k-1}$. This leads to a factor of 4 difference in the exponent, as compared to Hoeffding. I understand that this is more complicated and less understandable, though... --David Pal (talk) 03:19, 11 April 2011 (UTC)

Incorrect example

The example on azuma's inequality with coin tosses is incorrect. Check it for t=N/2. I think the problem is that the differences isn't a martingale. The differences are iid with expected value 1/2. And the previous difference could be 0 or 1. — Preceding unsigned comment added by 171.66.165.86 (talk) 20:02, 20 June 2011 (UTC)

Fixed. 16:39, 5 Oct 2011 — Preceding unsigned comment added by 128.6.23.7 (talk)

Condition may be stronger than necessary

The introduction of the article states that the theorem requires $|X_{k}-X_{k+1}|<c_{k}$. In the version that I am familiar with [Alon, N.; Spencer, J., (2000, 2nd Ed), The Probabilistic Method, New York: Wiley], the condition is stated as $|X_{k}-X_{k+1}|\leq c_{k}$, which weaker. So this seems to me like a typo or at least not the best possible.--Seabonn (talk) 19:24, 30 May 2014 (UTC)