User r hahn - MathOverflow

sorting two paired lists of real numbers to minimize consecutive absolute differences

2013-01-23T16:55:58Z

Consider a set of $n$ real-valued number pairs: $(x_1,y_1), (x_2,y_2), \dots, (x_n,y_n)$. I want to find a permutation $p$ of the indices which minimizes the sum of consecutive absolute differences:

$$\sum_{j=1}^{n-1} |x_{p(j+1)} - x_{p(j)}| + \sum_{j=1}^{n-1} |y_{p(j+1)} - y_{p(j)}|.$$

I suspect this is reducible to a well known problem, so I'm looking for pointers to literature mainly, but would be happy to see a clever algorithm for doing this from scratch.

Intuitively, I want to shuffle the observations so that the graph of $x$ elements against the index is smooth looking and the same graph of the $y$ elements is also smooth looking. If I cared only about one or the other, I could simply sort with respect to those elements. I want to shuffle in such a way that I compromise between the two coordinates.

My motivation is a statistical problem of estimating a smooth curve in the plane by assuming that the coordinate dimensions are each smooth functions of an unrecorded "time index". The above problem is maximizing the smoothness of the observed data under the assumption of evenly spaced observations in time.

Answer by R Hahn for Interesting thesis topic on statistical inference that is sufficiently mathematical

2013-01-16T16:56:11Z

The intersection between computability theory and statistics is pretty interesting. From this paper by Vovk (2009): "It is widely accepted that advances in computing have brought about deep changes in the theory and practice of statistics. However, the use of the theory of computing, and, in particular, of its core notion of computability, has been very limited in the classical areas of statistics, such as parameter estimation and hypothesis testing."

Relatedly, Ackerman, et al. (2011) demonstrate a computable random variable $(X,Y)$ with non-computable conditional distribution $P(Y \mid X)$.

Certainly this area is pretty "mathy"; it remains to be seen if it has implications for statistical practice.

Which limit to take as a key applied math decision

2013-01-05T23:11:53Z

The Borel-Kolmogorov paradox refers to situations where non-uniqueness in the notion of conditioning on a set of measure zero leads to apparent contradictions. As a formal matter, one requires instead to condition on "the" generating sigma algebra, which vanquishes non-uniqueness by fiat. For a technical explanations see this paper. Billingsley's measure theory book has a nice treatment as well.

I am looking for examples where a formal non-uniqueness was resolved by applied considerations which suggested a natural "tie-breaker".

A simple example from this paper illustrates the idea. Let $X$ and $Y$ be independent standard normal random variables. What is the conditional distribution of $X$ given that you are on the (measure-zero) line where $X = Y$? The answer will vary depending on if you condition on $Z_1 = 0$ where $Z_1 \equiv X - Y$ or $Z_2 = 1$ where $Z_2 \equiv X/Y$, to give just two of an infinite number of examples. So in a given situation which $Z$ is the "right" one to use?

My question is not about the Borel paradox or modeling random phenomena per se.

I am interested broadly in hearing about situations where

we have a mathematically well defined condition ($x = y$ as above)

we want to study some applied model when that condition is satisfied

the conclusions we reach will differ depending on the way we approach (as taking a limit) that condition formally

Finally I am interested in how this ambiguity is resolved by "physical" considerations.

I would make the problem sharper if I could, but the reason I want examples is precisely to help focus my thinking. I find it intriguing that it is not enough to have a well defined condition and a well defined model, one must also justify (by way of interpretation) which limit to take!

I anticipate there are many examples from physics of which I am unaware and perhaps some from the literature on finite elements for solving PDEs.

(Apologies for the pay-wall links.)

Answer by R Hahn for Strange pattern in rounding errors?

2012-12-13T14:25:00Z

Apparently it's something to do with the "residuals" function in R.

If you do this

h <- fitted.values(lm(tan(c/2)~u))
plot(u,h-tan(c/2),ylim=c(-2e-16,2e-16),cex=0.1)

instead (with the previous code being the same) you get the following:

Answer by R Hahn for Non-rigorous reasoning in rigorous mathematics

2012-12-01T01:49:59Z

In mathematical statistics people often have experience about some method that works well in practice even though it "shouldn't" in all generality. The game is then to ask what conditions need to be satisfied to explain why the method works.

Here is an example which I was not personally involved in, so I can only speculate. This paper by Bickel and Li considers local polynomial regression methods and shows that they works as well as possible (in the sense of asymptotic optimality) when the data it is being used on has low dimensional structure. The idea is that people were finding that certain regression techniques were giving reasonable generalization performance in prediction problems even when the data was high dimensional so they figured that maybe the data wasn't actually high dimensional in some relevant aspect. But which relevant aspect, that's the challenging part.

To my mind, figuring out how to explicitly articulate the minimal conditions under which some ``obvious" fact is true is where the discover and understanding come in. It is a very different process than what a student does on problem set, where the statement and all the relevant conditions are laid out and the main job is deriving the stated implication.

Put another way: research has degrees of freedom on both ends -- you can find/create the answer and the question as pairs, rather than being handed the one and being asked to complete the set. This perspective of course doesn't cover all cases -- notably, that of people chasing down famous open problems. But it is a way in which one can develop a rigorous understanding from ``non"-rigorous reasoning. When one first starts thinking vaguely about a problem there is nothing there about which to be rigorous.

Answer by R Hahn for Maximum entropy priors in infinite dimensional spaces

2012-10-15T03:23:07Z

Cover and Thomas's Elements of Information Theory has a chapter on maximum entropy stochastic processes. The relevant quantity in that case is the entropy rate. See section 12.5, for example, which is visible in Google books.

Answer by R Hahn for bayes theorem on histogram

2012-10-01T01:15:19Z

You may treat the histogram as observations arising from a multinomial distribution. The conjugate prior for a multinomial likelihood is a Dirichlet distribution. If you want to allow the number of bins to grow as you collect more data, this leads to a Dirichlet process prior, as I mentioned in my early comment.

Answer by R Hahn for Distance metric between two sample distributions (histograms)

2012-07-26T05:33:56Z

Total variation and Hellinger distance are two standard ways to measure this.

Kullback-Leibler divergence is another standard way, as would be general $f$-divergences.

The Earth-Mover's distance (also called the Wasserstein metric) is another option.

Bear in mind that your data gives an empirical cdf, so you can use any of the standard metrics for probability distributions notwithstanding the fact that you have a data sample in hand rather than a formula.

(Wiki has decent entries for all of these, which I may link to later.)

Answer by R Hahn for Bayesian statistics for pure mathematicians

2012-06-21T22:36:31Z

Many hold that Bayesian statistics "from a purely mathematical point of view" is entirely coextensive with probability (however it is that you want to define its boundaries as a mathematical discipline). Nonetheless, if I interpret your request as being for a mathematically sophisticated and rigorous exposition on why the Bayesian approach is a worthy one, three book spring to mind.

Theory of Statistics by Mark Schervish
Bayes Theory by John Hartigan
The Bayesian Choice by Christian Robert

The first of these is a general graduate text in statistics, but the author gives uncommonly complete coverage of both Bayesian and frequentist methods.

The second is a smaller volume and, as I recall, is devoted to some of the more delicate issues surround finite versus countable additivity as relates to using probability distributions as priors in a Bayesian approach.

The final book is more general, but the style is more formal than the Bernardo and Smith book mentioned by PaPiro. (This is, in my experience, true of the style of French Bayesians :)

As I said, the distinctive elements of the Bayesian perspective are more philosophical than technical, but there are some technical areas that have received attention in the Bayesian community that may be of independent mathematical interest. One would be the role of so-called "improper" priors as mentioned above.

Another is the role of conditional distributions as a primitive rather than derived notion, leading to the idea of disintegration, as in this manuscript of Pollard.

Also, because of a keen interest in the application of Monte Carlo methods, Bayesian statisticians have to a lot of work on various aspects of computational methods for sampling from various distributions. Christian Robert is a prominent researcher in this area, and he has a blog. The current post happens to be about Bayesian foundations.

Finally, at the heart of a many arguments in favor of a Bayesian approach (early chapters in Bernardo and Smith and Robert are dedicated to it) are de Finetti type representation theorems, which sanction prior distributions via appeals to exchangeability. You can start with the wiki entry for de Finetti theorems and then look at the work of Persi Diaconis on the topic. In this vein see also Lauritzen's monograph, which (for me anyway) is the last word on the matter.

Answer by R Hahn for multivariate linear regression with dependent noise terms?

2012-06-21T12:54:27Z

One key word would be "seemingly unrelated regressions" or SUR. The dependence of the noise term leads to different estimates of the regression coefficients (your $A$): http://en.wikipedia.org/wiki/Seemingly_unrelated_regressions

Answer by R Hahn for Estimating joint and conditional probabilities with incomplete information

2012-06-12T19:02:06Z

This paper addresses a similar problem I think, although I believe they consider binary outcomes only:

Ramsahai, R.R. (2007). Causal bounds and instruments. In Proceedings of the 23rd Annual Conference on Uncertainty in Artifical Intelligence, 310-317.

The main result is a way to produce the sorts of upper and lower probabilities that Douglas Zare mentions in his comment. They additionally note a freely available software package that they use, called polymake.

Answer by R Hahn for The James–Stein estimator - counterintuitive estimation of the mean. What means it is better than least squares ? (Understanding Wikipedia)

2012-04-11T13:57:15Z

This has always bothered me. "One should use the price of tea in China to obtain a better estimate of the chance of rain in Melbourne" is not a good characterization at all. One should use the price of tea in China and the chance of rain in Melbourne to obtain a better estimate of the vector which includes both the average price of tea in China and the chance of rain in Melbourne. The Stein result only obtains if you care about a vector-valued parameter; that is the observations are assumed independent probabilistically but clearly interact with one another via the loss function being use.

The idea behind the quote is that you can hedge your bets on any given coordinate dimension by "shrinking" back towards the "global" mean (across all elements of the mean vector). But observe that the "shrinkage" need not in fact be towards the overall mean for the result to hold...you can shrink back towards any value at all and still get the result, which has to do with the definition of admissibility used. My favorite description of what is going on is here.

Is a parametric family which is universally consistent for multiple quantiles impossible?

2012-04-04T23:39:02Z

Suppose I am dead-set on using Bayesian inference on independent and identically distributed data, but I'm lazy and insist on using a parametric likelihood function come what may. I'd be reassured to know that as long as I stick to a particular class of parametric densities I can be sure to recover the true quantiles.

Is there a recipe to construct a parametric family given a vector $q \in (0, 1)^k$ such that the inferred quantiles at $q_1, \dots, q_k$ line up with the true quantiles at those points?

Here's my stab at formalizing this.

To keep things simple I don't mind working with probability distributions over the real line with continuous density with respect to Lebesgue measure, a class we can call $\mathcal{P}$.
The restriction to parametric models can be done by assuming that $\mathcal{G} \subset \mathcal{P}$ can be indexed (smoothly) by a compact subset of $\mathbb{R}^d$, for $d$ finite (so that $\mathcal{G}$ is a smooth manifold as per ArthurB's comment). We can call the parameters $\theta \in \mathbb{R}^d$.
Finally, we have that the Bayesian machinery will converge to the so-called "pseudo-true" parameter values, meaning that we eventually converge to the value $\theta^*$ minimizing the Kullback-Leibler divergence $$\int_{-\infty}^{\infty} \log{\left(\frac{f(x)}{g_{q,\theta}(x)}\right)}f(x) dx$$ for true distribution $F \in \mathcal{P}$ with density $f(x)$.

Now the question reads: for $k > 1$ and for any $F \in \mathcal{P}$ does there exist $\mathcal{G_q} \subset \mathcal{P}$ with $G_{\theta^*}^{-1}(q_j) = F^{-1}(q_j)$ for all $j = 1, \dots, k$ ?

(Here $G^{-1}$ denotes the inverse cumulative distribution function of the distribution $G \in \mathcal{G}$ with density $g(x)$, and similarly for $F$.)

Further, to get to the heart of the issue, I need $\mathcal{G_q}$ to be computable given $q$ as input.

I suspect there is a non-existence result of some kind to be had here. Note that for $k = 1$ this is actually doable, which is the motivation behind the use of the asymmetric Laplace density for this purpose. The trick used there is that the likelihood is maximized at the sample quantile, which is consistent for the true quantile. This does not work naively in the case of $k>1$ because the normalizing constant messes things up so that the parameters are still consistent for the quantiles but they no longer "represent" the corresponding quantiles of the density being used.

Answer by R Hahn for What does it mean to sample a value x* from f(x)?

2012-03-29T23:05:41Z

In the simple case that $X$ is a real valued random variable, the first thing I would reach for is the inverse-cdf method, especially since you have mentioned "runif" which gives draws from a uniform distribution.

There is a pretty extensive literature on ways to sample from a variety of distributions, with names like Gibbs sampling, Metropolis-Hastings, slice samplers, perfect samplers, etc. A Google search of any of these should bring up a wealth of info. Did you want something more specific?

Is the solution bounded Diophantine problem NP-complete?

2010-08-23T01:58:33Z

Let a problem instance be given as $(\phi(x_1,x_2,\dots, x_J),M)$ where $\phi$ is a diophantine equation, $J\leq 9$, and $M$ is a natural number. The decision problem is whether or not a given instance has a solution in natural numbers such that $\sum_{j=1}^J x_j \leq M$. With no upper bound M, the problem is undecidable (if I have the literature correct). With the bound, what is the computational complexity? If the equation does have such a solution, then the solution itself serves as a polytime certificate, putting it in NP. What else can be said about the complexity of this problem?

Answer by R Hahn for Gibbs sampling step size

2012-03-24T20:13:01Z

To expand a bit on Arthur B.'s comment that you can use samples even if they are dependent, consider this quote from Andrew Gelman and Kenneth Shirley:

The purpose of thinning (i.e. setting n to some integer greater than 1) is computational, not statistical. If we have a model with 2000 parameters and we are running three chains with a million iterations each, we do not want to be carrying around 6 billion numbers in our simulation. The key is to realize that, if we really needed a million iterations, they must be so highly autocorrelated that little is gained by saving them all. In practice, we ﬁnd it is generally more than enough to save 1000 iterations in total, and so we thin accordingly. But ultimately this will depend on the size of the model and computational constraints.

The full article is full of great practical recommendations for using MCMC for inference.

Answer by R Hahn for Maximum entropy probability distribution with known quantile

2012-03-20T21:20:33Z

The quantile alone is insufficient to define a maximum entropy density. Intuitively this is because the quantile is a single point and is not enough to prescribe an entire density; you must specify additional moments.

A related fact is that quantiles are not sufficient statistics for any distributions on $\mathbb{R}$, as noted here on page 17.

Software for symbolic matrix calculus?

2012-03-02T01:43:39Z

Is it possible to get widely available math software (Maple/Matlab/Mathematica, etc) to symbolically differentiate vector and scalar functions of matrices, returning the result in terms of the original matrices and vectors involved? I have in mind the simple sort of rules collected here for example.

On a few separate occasions I've scoured around the internet for such a thing and only turned up a bunch of incomplete threads of various vintage (like this or this or this).

So my main question is if I am missing the right keywords to find what is obvious to people who use this sort of functionality all the time, and what platform it is available on if so.

If in fact this sort of functionality is not available in any of the commonly used software my question is if this is because of some sort of practical obstruction I am not seeing or simply because the problems for which it would be useful are simple enough to be done by hand (which is what I've ended up doing after I spend 4 hours searching for the "easy" way).

Answer by R Hahn for Measure of progress towards a proof

2012-02-18T18:01:11Z

I'm not an all an expert on this, but here is what I hope is a relevant paper by Haim Gaifman:

Reasoning with limited resources and assigning probabilities to arithmetical statements

The paper describes how to develop a "local" logic involving a set of axioms and using modus ponens as the inference rule, from which one can assign probabilities to the event that arithmetical statements are true or false. This is very much along the lines of your stated intuition about satisfiability formulas and in fact he has an example concerning primality testing.

Answer by R Hahn for Sampling uniformly from a sphere

2012-02-07T21:34:18Z

The result you want, I think, is in Stationarity, Isotropy and Sphericity in $l_p^*$. It is behind a pay-wall, but the form of the distribution is stated in the abstract.

Answer by R Hahn for refrence for simple statistics question: estimation of variance of $n$, for known $r=s+n$, for $s= \pm1$, $n=N(0,\sigma)$

2011-12-09T20:28:07Z

You could try a moment-matching approach. In particular, define $\hat{s}$ to be the value of $s$ such that

$$\mbox{Pr}_{s}(-1 < r < 1) = \frac{\sum_i I(-1 < r_i < 1)}{N}$$

where $N$ is the number of observations. You can calculate the left hand side explicitly as $$\mbox{Pr}_s(-1 < r <1 \mid S = 1)\mbox{Pr}(S = 1) + \mbox{Pr}_s(-1< r <1 \mid S = -1)\mbox{Pr}(S = -1)$$

which simplifies (I think) to

$$\Phi(2/s) - 1/2,$$

where $\Phi(\cdot)$ denotes the cumulative distribution function for a standard normal random variable. Inverting this gets

$$\hat{s} = \frac{2}{\Phi^{-1}\left(\frac{\sum_i I(-1 < r_i < 1)}{N} + 1/2\right)}.$$

I'm not sure if this differs much from your Solution 3 in terms of complexity, but one evaluation of the inverse CDF of a Gaussian isn't so bad.

Answer by R Hahn for An inequality on Difference of Entropies

2011-09-22T16:29:38Z

EDIT: This is wrong -- careless mistake as noted in the comments. I thought I had deleted it, but here it still is.

Working with the RHS of your inequality we have

\begin{eqnarray}\sum_i (P_i - Q_i) \log{\left(\frac{1}{\frac{P_i}{e} + (1-\frac{1}{e})Q_i}\right)} &=& \sum_i (P_i - Q_i)\log{\left(\frac{e}{P_i + (e-1)Q_i}\right)}\\ & = & \sum_i (P_i - Q_i) (1 - \log{(P_i + (e-1)Q_i)})\\ & = & \sum_i (P_i - Q_i) + \sum_i (Q_i - P_i)\log{(P_i + (e-1)Q_i)}\\ & = & 1 - 1 + \sum_i (Q_i - P_i)\log{(P_i + (e-1)Q_i)}\\\ & = & \sum_i Q_i \log{(P_i + (e-1)Q_i)} - \sum_i P_i \log{(P_i + (e-1)Q_i)}\\\ & \geq & \sum Q_i \log{(Q_i)} - \sum_i P_i \log{(P_i)}\\ & =& -\mbox{H}(Q) + \mbox{H}(P). \end{eqnarray} The inequality follows from $\log{(P_i)} \leq \log{(P_i + (e-1)Q_i)}$ and $\log{(Q_i)} \leq \log{(P_i + (e-1)Q_i)}$.

Answer by R Hahn for Why is the Fast Fourier Transform efficient?

2011-09-21T01:17:57Z

Conceptually the FFT takes advantage of a shortcut similar to the distributive law for multiplication. To compute $$(x_1 + x_2)(x_3 + x_4)$$ on could either add first (twice) and then multiply (once), or one could expand $$sx_1x_3 + x_1x_4 + x_2x_3 + x_2x_4$$ and multiply (four times) and then add (three times). This idea has been spelled out in the paper The Generalized Distributive Law.

Answer by R Hahn for exchangeable normal r.v.s

2011-09-08T01:36:33Z

I will expand on this answer later if there is interest and when I have some references handy. But for now you may be interested in the following way of thinking about the problem.

One way to characterize the Gaussian distribution is as the unique distribution on $\mathbb{R}$ satisfying spherical symmetry. More precisely, for $N$ observations, consider the two-dimensional statistic $$T(X_{1:N}) = \left(\sum_{i=1}^N X_i, \sum_{i=1}^N X_j^2 \right).$$ Assume that the conditional distribution of the vector $X_{1:N}$ is uniform on the hypersphere with center $(T_1, \dots, T_1)$ and radius $\sqrt{(T_2 - T_1^2/N)}$. This implies that the density for $X_{1:N}$ may be written as $$f(X_{1:N}) = \int \prod_{j=1}^N \left[(2\pi)^{-\frac{1}{2}}\sigma^{-1} \exp{\left\lbrace\frac{(x_j - \mu)^2}{\sigma^2}\right\rbrace}\right] dP(\sigma, \mu)$$ for some density $dP(\sigma,\mu)$. (This sort of representation theorem motivates the use of prior distributions in Bayesian statistics.) Note that as $N \rightarrow \infty$, $T$ converges to the true first and second moments, which gives back another common characterization of the normal distribution as being specifiable using only them.

So, when you say that "usually 'exchangeable normal random variables' means jointly normal random variables" it makes me wonder what is the more critical property, the permutation invariance -- which does not uniquely define the distribution -- or the underlying symmetry -- which in the case of the normal distribution does. The reason I brought up the copula earlier is that I think getting your necessary marginals to be whatever is not much of a barrier, because you can always transform things elementwise. This makes me think that you are really asking whether or not there are other forms of exchangeable distributions of real-valued vectors, and there definitely are. Following the example of the spherical symmetry, the basic recipe is to specify a statistic and then specify a uniform transition kernel given the value of that statistic. This approach has been systematized by Steffen Lauritzen in a monograph S. L. Lauritzen. Extremal Families and Systems of Sufficient Statistics. Lecture Notes in Statistics, No. 49. A good textbook treatment of this is given in section 2.4 of Mark Schervish's Theory of Statistics (available on Google Books, but my toolbar for providing links seems to have vanished).

Apologies if you knew all of the above and I missed the point of your question, but your comment to Yuri makes me think that this stuff would be of interest. The keywords you'd want to include to dig around more include "de Finetti theorems", "extremal families", and "partial exchangeability".

Answer by R Hahn for Are all probabilities conditional probabilities?

2011-09-03T06:54:57Z

It is possible to develop probability theory taking conditional probability as one of the basic definitions; see section 3.2 in this book and the references mention there. Renyi was one of the first mathematicians to favor this approach, which is described in his book Probability Theory. Part of the motivation for this approach is to directly build in the ability to condition on measure-zero events without having to make a limiting argument. Another key word related to this idea is disintegration.

So, as Kjetil mentions, it all depends on what one takes as axioms. But certainly it is possible to develop theories that take conditional probability as the centerpiece.

Answer by R Hahn for A test for randomness of direction of vector data

2011-08-27T04:38:19Z

Here is one approach to consider.

Treating the data as points on the surface of the unit sphere, consider the collection of convex subsets on this surface that contain all of your observations. Then, define $S$ to be minimum area among such sets. One way to interpret the idea of "having no preferred direction" is that this set $S$ should be almost as big as the entire surface; conversely a preferred direction would manifest as the data being tightly concentrated in a small area on the sphere.

This is just a rough idea -- figuring out how to operationalize "almost as big as the entire surface" would depend on your statistical needs. Hope I haven't missed the mark too badly.

Answer by R Hahn for Statistical calculations over algebraic structures

2011-07-17T11:59:56Z

There is a whole research area called Algebraic Statistics, although its boundaries are pretty blurry in my opinion. But you could do worse than to start with Seth Sullivant's web page for some idea of what it is all about:

http://www4.ncsu.edu/~smsulli2/Pubs/publications.html

Titles like "Algebraic factor analysis: tetrads, pentads, and beyond" and "Algebraic statistical models" suggest to me that this may be what you are looking for.

Answer by R Hahn for Is there a problem with the Wishart distribution?

2011-07-04T21:36:37Z

If you are interested in constructive distributions that you can simulate from (as opposed to something simpler with a known expression for the density) you have a lot of flexibility in constructing positive semi-definite matrices "from scratch". One popular way to do this is to use a "factor decomposition" which sets $$S = BB^t + \Psi$$ where $B$ is a $p$-by-$k$ matrix for $0 < k \leq p$ and $\Psi$ is a diagonal matrix with positive elements. A distribution on $S$ is induced by a distribution over the elements of $b_{ij}$ of $B$ and $\psi_{ii}$ of $\Psi$. One could draw the columns of $B$ to be orthogonal if desired (from say the Bingham-von-Mises-Fisher distribution). The recipe would be to 1.) draw $k$ between 0 and $p$ with some probabilities, 2.) draw $k$ columns of $B$, 3.) draw the elements of $\Psi$ iid and 4.) construct $S$. In this setting it seems like it would be easy to avoid the concentration phenomenon you note simply by modulating the distribution over $k$ and $\Psi$ as $p$ grows.

For what sub-$\sigma$-algebra are these two measures equivalent?

2011-01-06T04:40:16Z

In two statistics papers (linked inline below) I have come across two definitions of certain probability measures. I conjecture that for particular choices of the construction that they are equivalent but am struggling to show so in the most general case.

MOTIVATION
I'm studying generalizations of conditioning for updating subjective probability distributions. My goal is to adapt these methods for practical statistical analysis; the previous literature is primarily scholarly/academic. My measure theory not being what it should, I'm running into a technical difficulty and I think the audience here can help.

I will begin by describing the case of a finite partition before moving on to the case that is bothering me, the uncountable setting.

THE GIBBS POSTERIOR (see Jiang and Tanner tech report)
One definitions I'm dealing with is that of a Gibbs posterior, which has density w.r.t. Lebesgue measure: $$\omega(d\beta) = \exp{(-R_Y(\beta))}\pi(d\beta) / \int_{\beta \in \Omega} \exp{(-R_Y(\beta))}\pi(d\beta),$$ where $\beta \in \Omega \subseteq \mathbb{R}^k$ and $R$ is a function from $\Omega \rightarrow \mathbb{R}$. The subscript $Y$ attached to $R$ is just a reminder that $R$ is usually defined in terms of some fixed set of observed data $Y = (y_1, y_2, \cdots, y_n)$. A typical example would be $R_Y(\beta) = \sum_{j=1}^n (y_j - \beta)^2$, the mean square error. You'll notice that if $R$ is the negative log-likelihood of $Y$, this expression gives the usual Bayesian posterior distribution. However, we may use this for general loss functions to get a so-called empirical risk based posterior. This expression provides a recipe for moving from $\pi(\beta)$ to $\pi^{\star}(\beta) = \omega(d\beta \mid Y)$, provided we specify the form of $R_Y$.

JEFFREY UPDATING (the easy case)
Another alternative to Bayes rule is something called Jeffrey updating. In the easy case, Jeffrey updating calls on us to find a "sufficient partition" of the parameter space. So if our parameter $\beta$ lives on the real line, we may partition it into finitely many disjoint subsets $E = (E_1, E_2, \cdots, E_n)$. The partition is judged to be sufficient in that within any of these subsets our prior beliefs/distribution $\pi(\beta)$ doesn't change. All that will change is the relative values of the subsets. Specifically for any set $A$ we have $$P^{\star}(A) = \sum_{j=1}^n P(A \mid E_j)P^{\star}(E_j).$$

If $\pi(\beta)$ is a Normal distribution then $\pi^{\star}(\beta)$ would look something like this. The prior is in red, the posterior in black and the partition is defined by 20 observed data values (I won't describe how $P^{\star}(E_i)$ was determined.)

This approach is motivated by the idea of "conditioning on partial information". If you don't know for sure what partition the true parameter falls in, but you are handed some information about those relative probabilities (the $P^{\star}(E_j)$), this is how you would update. This should be equivalent to the Gibbs posterior in the case that $R$ is defined to be a simple/step function ranging over $\beta$. The finite jumps in $R$ corresponds to the partitions and $P^{\star}(E_j) \propto \exp(-R(\beta \in E_j))$.

JEFFREY UPDATING (the harder case)
Expression 6.1 from Diaconis and S.L. Zabell extends Jeffrey updating to the case where instead of a finite partition you have a presumed sufficient sub-$\sigma$-algebra. I'm reproducing the relevant section here.

We start with a probability space $(\Omega, \mathcal{A}, P)$. We want to move from $P$ to $P^{\star}$, a new probability measure on $\mathcal{A}$. We assume that we have a sub-$\sigma$-algebra $\mathcal{A}_0 \subseteq \mathcal{A}$. Let $C$ be an $\mathcal{A}_0$-measurable set with $P(C) = 0$ and $\bar{P} \ll \bar{P}^{\star}$ on $\Omega - C$, where the bar denotes restriction to $\mathcal{A}_0$. Then we define $$ P^{*}(A) = \int_{\Omega-C} P(A \mid \mathcal{A}_0) P^{\star}(d \omega) + P^{*}(A \cap C).$$

FINALLY, THE QUESTION(S)

Are there definitions of $\mathcal{A}_0$ and $R(\beta)$ that would make the Jeffrey updated posterior in the continuous case equivalent to the Gibbs posterior?

If I do this naively, by letting $R$ be a continuous loss function (such as mean square error above) and let $\mathcal{A}_0$ be the $\sigma$-algebra generated by $R$ I think I get back all of the Borel sets, or all of $\mathcal{A}$. (A terminological question: does a sub-$\sigma$-algebra have to be strictly contained within the larger $\sigma$-algebra or is any $\sigma$-algebra a trivial sub-algebra of itself?) As a constructive matter I find that the clean correspondence in the simple function case loses its charm when one rather considers $\mathcal{A}_0$.

If one cannot directly specify $R(\beta)$ and $\mathcal{A}_0$ to make the two measures equivalent, can one define a (unique?) limiting equivalence by specifying a sequence of simple functions $R^i$ with limit $R$ and a sequence of finite partitions $E^i$ which generate $\mathcal{A}$ in the limit such that for every pair $(R^i, E^i)$ the Jeffrey and Gibbs posterior measures coincide?

And finally...

To help my intuition with the uncountable case, can anyone come up with a plausible candidate $\mathcal{A}_0$ in the simple case that $\Omega = \mathbb{R}$ and $\beta$ has density wrt the Lebesgue measure (perhaps by analogy to the discrete case I described)?

I hope some of you find this interesting enough!

Answer by R Hahn for What would you want to see at the Museum of Mathematics?

2010-12-26T06:19:13Z

I come across "mind reading" games based on elementary number theory from time to time; e.g. http://www.digicc.com/fido/. It bugs me a bit when people are wowed by such tricks, but not enough to sit down and figure out the mechanics of the thing. But the surprise factor may make a good museum activity -- where the second part of the activity is teaching why the trick works the way it does.

In general, math-based magic tricks would be good for an interactive exhibit: http://mathoverflow.net/questions/9754/magic-trick-based-on-deep-mathematics

Comment by R Hahn

2013-02-27T16:42:40Z

If you changed your title to reflect your geometric interpretation I suspect you'd get more traffic.

Comment by R Hahn

2013-02-26T02:35:52Z

Cool. If you want to skip the derivations, you can invoke the property of derivatives of Bernstein polynomials; in the notation from the problem $$b'(x,n)(p)=n(b(x−1,n−1)(p)−b(x,n−1)(p))$$.

Comment by R Hahn

2013-01-23T18:21:22Z

Yeah, I just remembered that the last time I thought about this I realized it could be formulated as a traveling salesman type problem. I need to go look at algorithms tailored to the version in the plane.

Comment by R Hahn

2013-01-06T00:29:35Z

Qiaochu, your nice observation underscores my curiosity: why should our understanding of a physical problem depend on which of two measurements we make, when both measurements reflect the same physical state in the limit? Generically I do not expect an answer, but I am asking for actual examples where something concrete can be said.

Comment by R Hahn

2013-01-06T00:00:23Z

Thanks Michael. I haven't looked through the book yet, but was going to pick it up on Monday from the library.

Comment by R Hahn

2012-12-18T02:16:55Z

It may be helpful to think of this as a truncated exponential distribution...which direction it "faces" depends on if $\mu$ is bigger or smaller than the midpoint of the interval. When $\mu$ exactly equals the midpoint the max entropy distribution is clearly the uniform distribution on that interval.

Comment by R Hahn

2012-12-13T03:18:27Z

You can get the same effect with seq(93,177,length.out=5000) instead of the random number generation step, right? That would point to purely numerical explanations and not pseudorandomization quirks

Comment by R Hahn

2012-12-04T18:32:16Z

Title should be "The geometry of undecidable diophantine equations: WWNED?"

Comment by R Hahn

2012-11-27T15:30:48Z

I think this is a question of sufficiency. Depending on what you are estimating, there is only so much information in the initial sample $x$ whether you extract it via simulation or otherwise. Certainly in cases of symmetry you can find that a given statistic is sufficient where, absent that symmetry, it wouldn't be. Take a uniform random variable with unknown support $[a,b]$; then $\max(|x_{1:n}|)$ is not sufficient for $a$. But if you knew that $a=-b$, then it would be.

Comment by R Hahn

2012-11-23T21:17:07Z

In what sense is $\hat{S}$ not a "bona fide" estimator?

Comment by R Hahn

2012-11-23T21:09:20Z

Paul & Emil: such "beauty contest" experiments reveal baffling play: for r = 0, not everyone plays 0. Some do not play increasing functions of r. Many people seems to play roughly linearly in r relative to their play at r=1. Here is my analysis of some data I recently collected from web surveys: faculty.chicagobooth.edu/richard.hahn/…. Plots of observed strategies: faculty.chicagobooth.edu/richard.hahn/…

Comment by R Hahn

2012-10-27T15:37:39Z

@Brendan, I guess as an applied statistician I'm usually happy to rule out the kind of degeneracy you mention, but your point is well taken. On a separate note, several years ago I used your nauty program when doing my masters degree on a branch-and-bound algorithm for the maximum independent set problem. So thanks for that!

Comment by R Hahn

2012-10-09T05:01:02Z

Presumably the intended link is pages.bangor.ac.uk/~mas010/hdaweb2.htm

Comment by R Hahn

2012-10-01T00:49:24Z

Search "Dirichlet processes" or "Bayesian density estimation".

Comment by R Hahn

2012-09-24T03:13:28Z

I speculate from Geyer's intro that this approach mainly appeals to a relatively smallish group: statisticians with a desire for rigor and simultaneously very specific applications (stat inference) in mind. Learning this new approach may pay off in licensing the heuristic of thinking about all integrals as sums and all conditioning as division. I do wonder how this approach squares with recent results to the effect that there exist computable joint distributions which yield non-computable conditionals.