Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I have a polynomial $p(x)=a_Nx^N+a_{N-1}x^{N-1}+\dots+a_0$. I want to convert this into another polynomial of same order, say $b_Ny^N+b_{N-1}y^{N-1}+\dots+b_0$. Is it possible to find a transformation $y=f(x)$ that will transform the coefficients $a_n$ into $b_n$? For the case of second order polynomial, a linear transform does the job.

I am asking this in order to generate random variables. For gaussian random variable case I can sample from $N(0,1)$, density of which is a second order polynomial inside an exponential. By a linear transformation $ax+b$, I can get samples from $N(b,a^2)$. What I am trying to do is assuming I have samples from $x \sim density\propto \exp(a_Nx^N+a_{N-1}x^{N-1}+\dots+a_0)$, whether or not I can get samples from $y \sim \exp(b_Ny^N+b_{N-1}y^{N-1}+\dots+b_0)$ just by a deterministic transform $y=f(x)$.

Btw, $a_N$ is a negative constant and $N$ is always even, so that $\exp(polynomial)$ makes a sensible probability density function. Thanks a lot in advance.

edit As Robert Israel stated in his comment, the constant term is to be a proper normalization term. The basic question is this, a gaussian corresponds to a log-polynomial density where the polynomial is of 2nd order, and one can sample $N(\mu,\sigma^2)$ from $N(0,1)$ just by the transform $\mu+\sigma x$. Hence this corresponds to converting a polynomial into another one. Constant term is not of importance as it is just a normalization term. So for an higher order polynomial of degree N is there a possible way to do such a thing?

share|improve this question
    
I don't understand the question. What relationship do you want the first and second polynomial to have? –  Qiaochu Yuan Dec 2 '12 at 22:46
    
so in $p(x)$ if I replace x with f(x), or x with a y, I will get the polynomial with new coefficients. –  YBE Dec 2 '12 at 22:50
3  
You are given the $a_n$'s and the $b_n$'s? In general, this is not possible. E.g., $p(x) = -x^2$, $q(y) = -x^2-1$. Assuming that you are only interested in real parameters, $p(x)$ assumes the value $0$, but $q(y)$ never does, so there is no $f$ such that $p(x) = q(f(x))$ for all $x$. –  Goldstern Dec 2 '12 at 23:20
    
In the quadratic case a linear transformation is not enough, even over the complex numbers. The reason being that you have only two parameters to chose (a and b), while you have to solve for three equations. To be concrete $p(ax+b)=a_{2} a^{2} x^{2} + (2 a_{2} a b + a_{1} a) x + a_{2} b^{2} + a_{1} b + a_{0}$ so in order for the linear transformation to turn one polynomial into the other you have to have $a_{2} a^{2}=b_2$, $(2 a_{2} a b + a_{1} a)=b_1$ and $ a_{2} b^{2} + a_{1} b + a_{0}=b_0$. These three equations will be rarely solvable at the same time. –  Maarten Derickx Dec 3 '12 at 0:50
1  
Perhaps the confusion is due to the fact that YBE is implicitly allowing the constant term in the quadratic polynomial to be adjusted to obtain a probability density function. So for $p(x)$ and $q(y)$ quadratics with negative leading coefficient, you can get $p(ax+b) = q(x) + c$ for some constant $c$ by solving two equations in two unknowns. –  Robert Israel Dec 3 '12 at 1:16
add comment

1 Answer 1

It is possible to do that using the algorithm known as the Independent Metropolis-Hastings sampler without having to do any transformation and without having to compute the constant normalizing terms.

Assume you can sample from the density $q(x)\propto \exp(g(x))$ where $g(x)$ is a polynomial (say, you are sampling from the normal distribution) and your objective is to get a sample from the density $p(x)\propto \exp(f(x))$ where $f(x)$ is another polynomial (naturally both polynomials need to have negative leading term to insure those densities exist). Then the algorithm will produce a Markov process whose invariant distribution is $p(x)$. Starting from some arbitrary initial value, say $X^0$, let's say that you have already $M$ draws. To get a new sample draw $X^{M+1}$, draw a random variable from $q$. Let's call that draw $X'$. Then accept or rejet $X'$ with probability $$1 \wedge \exp[f(X')-f(X^M)+g(X^M)-g(X')]$$ If you have accepted then set $X^{M+1}=X'$ otherwise set $X^{M+1}=X^M$.

Eventually that Markov process would have converged and you could consider say the last $N$ draws as such a sample from the desired distribution.

A very good introduction to that algorithm is section 7.4 of this excellent book


Edit As indicated by the author of the question in a comment below, if the question is to transform a sample from one continuous distribution having density $q(x)$ into a sample from another continuous distribution having density $p(x)$, then this could be achieved in the following way.

Let $Q$ and $P$ be the CDF's associated with $q$ and $p$ respectively. Assume we have an i.i.d. sample $X_1$,...,$X_n$ from $q$, then $P^{-1}(Q(X_1))$,...,$P^{-1}(Q(X_n))$ is an i.i.d. sample from $p$. (this is straightforward to prove).

Now, the issue in your case is that $P$ and the quantile function $P^{-1}$ may not be known in closed-form (even the normalizing constant of the density associated with $P$ may be not be known in closed form.) However, numerical integration and interpolation could work here.

share|improve this answer
    
Thanks for the answer, I know that I can achieve sampling from arbitrary densities by Metropolis-Hastings algorithm. My question is more on the order of, if I have samples from $exp(polynomial_1)$ can I get the samples from $exp(polynomial_2)$ just by transforming the samples I get from the first log-polynomial density. I will be sampling from such densities in an online fashion so speed is a concern and I cannot wait for the M-H chain to mix. I pretty much want a way to sample directly from such densities. I already sample from log-polynomial densities using slice sampling. –  YBE Dec 4 '12 at 8:39
    
I edited my answer to reply to your comment about transforming a sample from one continuous distribution into a sample from another. –  an12 Dec 4 '12 at 9:11
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.