Here are a few thoughts; see if they help.

1. This is the classic bias-variance trade-off problem: Too few bins result into too much bias (i.e., deviation from the true but unknown underlying density) but low variability (of the histogram) across different data realizations (from the same data-generating process), whereas too many bins lead to little bias but too much variability. The basis for dealing with such bias-variance trade-off problems is usually a squared loss between the histogram estimator and the true but unknown density, and the associated risk function (i.e., expected loss). All optimal binsize prescriptions (such as Freedman-Diaconis) attempt to balance the bias of a histogram with its variance. This standard formalism can be found in, e.g., Larry Wasserman's All of Statistics and All of Nonparametric Statistics (both Springer).

If you use an optimal binsize prescription, and the data meets the assumptions that the prescription is based on, then information loss is autoatically minimal according to that prescription.

2. Also remember that a histogram is just one estimator for the probability density of your data. That too a discrete one. If the underlying density is known to be continuous, then other density estimators (e.g., kernel density estimators) may be more appropriate.

3. The CDF need not be estimated from the histogram. There is, e.g., a nonparametric estimator called the empirical distribution function (EDF) that estimates the CDF directly from the data. The EDF does not depend on any adjustable parameter such as the bin size, and its formal properties are well-understood.

.

Marc Boullé: Optimal bin number for equal frequency discretizations in supervized learning. Intell. Data Anal. 9(2): 175-188 (2005)

might be of interest for you.

see also

Marc Boullé: Khiops: A Statistical Discretization Method of Continuous Attributes. Machine Learning 55(1): 53-69 (2004)

for more details

( should be available from the author's home page

http://perso.rd.francetelecom.fr/boulle/ )

.

Here are a few thoughts; see if they help.

1. This is the classic bias-variance trade-off problem: Too few bins result into too much bias (i.e., deviation from the true but unknown underlying density) but low variability (of the histogram) across different data realizations (from the same data-generating process), whereas too many bins lead to little bias but too much variability. The basis for dealing with such bias-variance trade-off problems is usually a squared loss between the histogram estimator and the true but unknown density, and the associated risk function (i.e., expected loss). All optimal binsize prescriptions (such as Freedman-Diaconis) attempt to balance the bias of a histogram with its variance. This standard formalism can be found in, e.g., Larry Wasserman's All of Statistics and All of Nonparametric Statistics (both Springer).

If you use an optimal binsize prescription, and the data meets the assumptions that the prescription is based on, then information loss is autoatically minimal according to that prescription.

2. Also remember that a histogram is just one estimator for the probability density of your data. That too a discrete one. If the underlying density is known to be continuous, then other density estimators (e.g., kernel density estimators) may be more appropriate.

3. The CDF need not be estimated from the histogram. There is, e.g., a nonparametric estimator called the empirical distribution function (EDF) that estimates the CDF directly from the data. The EDF does not depend on any adjustable parameter such as the bin size, and its formal properties are well-understood.

Naturally, KS statistics should be used in a non parametric test, that, (almost) always will reject the null hypothesis because the size of your sample is very large.

If you have no distribution hypothesis, almost all the suggested techniques like Kernel density estimation, or the Freedman and Diaconis rule, may not be so efficient as estimators.

However, my personal reply is: a density estimator is useful when you need to estimate densities, but in general distributions are made for estimate or predict probabilities once given a interval of values. So, an index for assessing if the histogram model is adequate to the data should be based on its capacity of predict such probabilities, maybe on not so large intervals of values.

I used a similar approach here:

http://link.springer.com/chapter/10.1007%2F978-3-642-13312-1_15

for the improvement of an algorithm for histogram definition, in that case I didn't use the equi-width constraint.

Let me add three small bits to the wisdom already transmitted. First, borrowing from Hamlet (or was it JFK?), Ich bin oder ich bin nicht, das ist der frage.

Sometimes keeping the data in their original form may be the only way to check if damage is done by binning for a future application that was not foreseen originally.

Second, see the attached short paper that shows how binning data unwisely can profoundly change the relationship between the binned variable and another. Indeed the authors of the attached show how the correlation can easily change signs depending only on the binning

Third, see Jim Ramsay's paper

Ramsay, J.O. (1973). The effect of number of categories in rating scales on precision of estimation of scale values. Psychometrika, 28, 513- 532.

That shows that under reasonable circumstances, you lose little from keeping the continuous data with 7 categories.

If you are asking about "information loss", I would try using information-theoretic quantities. And even there are many ways to look at the problem:

1) (The field I am working in.) You can treat the histogram as a function of the original data, i.e., compute the information loss as the conditional entropy H(original | histogram). Interestingly, with this both histograms in your example are equivalent; specifically, you do not loose any information at all, since the mapping is bijective if restricted to the support of your empirical probability mass function.

2) The second way would be to use relative entropy to measure the "distance" between the true (or empirical) distribution and the distribution estimated from the histogram. This of course needs to specify _how_ the distribution is estimated from the histogram, but I am sure you have already solved this problem. In case the relative entropy (or Kullback-Leibler divergence) is not adequate for your purposes, you can still use the total variation distance, the Vasershtein distance or some similar distances on the space of probability distributions. The great advantage here is that you do not need a statistical test (which in many cases makes assumptions on the distribution of the data), you can just define the histogram bins by minimizing the respective distance or divergence measure.