14
$\begingroup$

Let A, B and C be finitely supported probability distributions with at most d nonzero probabilities each. Now consider the following simultaneous equations using p-norms, for each value of p≥1, given by

||A||p + ||B||p = ||C||p

where A, B and C are still non-negative, but we relax normalization on A and B. Imagine that C is fixed and, without loss of generality, normalized. We want to solve for A and B.

First, note that one obvious family of solutions is

A = (1-x) C , B = x C , 0≤x≤1 .

Question: Ignoring the obvious permutation symmetries, are these the only solutions?

Edit: By p-norm, I mean the vector p-norm: ||A||p = (∑j |aj|p )1/p. Although we don't really need the absolute values, since the aj are all non-negative.

$\endgroup$
9
  • $\begingroup$ Can you clarify somewhat? I'm not sure I understand what you mean A, B, and C to be. I thought at first you meant A, B, C to be discrete random variables taking on at most d values, and $\Vert A \Vert_p = (E |A|^p)^{1/p}$, but then I have no idea what you mean by "relax normalization on A and B". $\endgroup$ Dec 11, 2009 at 0:35
  • $\begingroup$ Mark: He means that the total measure of A need not be 1, and the same for B. $\endgroup$ Dec 11, 2009 at 14:41
  • $\begingroup$ Okay, so I guess $A,B,C$ are finite measures with finite support. Then what is $\Vert A \Vert_p$ supposed to be? $\endgroup$ Dec 11, 2009 at 14:47
  • $\begingroup$ It's just what you think: $\|A\|_p = (\sum_{j=1}^d |a_j|^p )^{1/p}$. $\endgroup$ Dec 12, 2009 at 2:28
  • $\begingroup$ That's actually completely different from what I originally thought. I was confused because that's not the kind of p-norm one usually sees in probability. $\endgroup$ Dec 12, 2009 at 15:12

2 Answers 2

12
$\begingroup$

Here is a proof that Steve's rescaling gives you all solutions, together with the trivial operation of permuting the components of $A$, $B$, and $C$ if you view them as vectors with positive coeifficients. (If you view them this way, then Steve's notation $||A||_p$ is just the usual $p$-norm.)

I first tried what Alekk tried: You can take the limit as $p \to \infty$ and eventually obtain certain power series expansions in $1/p$. Or you can take the limit $p \to 0$ and obtain certain power series expansions in $p$. The problem with both approaches is that the information in the terms of these expansions is complicated. To help understand the second limit, I observed that the two sides of Steve's equation are analytic in $p$, but it only helped so much.

Then I realized that when you have a complex analytic function of one variable, you can get a lot of information from looking at singularities. So let's look at that. Let $\alpha_k = \ln a_k$, so that $$||A||_p = \exp\left( \frac{\ln \bigl[\exp(\alpha_1 p) + \exp(\alpha_2 p) + \cdots + \exp(\alpha_d p) \bigr]}{p} \right).$$ The expression inside the logarithm has been called an exponential polynomial in the literature, which I'll call $a(p)$. As indicated, $||A||_p$ has a logarithmic singularity when $a(p) = 0$. $||A||_p$ has another kind of singularity when $p = 0$, but won't matter for anything. Also $a(p)$ is an entire function, which means in particular that it is univalent and has isolated zeroes. Also, none of the zeroes of $a(p)$ are on the real axis. Let $b(p)$ and $c(p)$ be the corresponding exponential polynomials for $B$ and $C$.

Suppose that you follow a loop that starts on the positive real axis, encircles an $m$-fold zero of $a(p)$ at $p_0$, and then retraces to its starting point. Then the value of $||A||_p$, which is non-zero for $p > 0$, gains a factor of $\exp(2m\pi i/p_0)$. Thus Steve's equation is not consistent unless all three of $a(p)$, $b(p)$ and, $c(p)$ have the same zeroes with the same multiplicity. (Since $\exp(2m\pi i/p_0)$ cannot have norm 1, geometric sequences with this ratio but with different values of $m$ are linearly independent.)

At this point, the problem is solved by a very interesting paper of Ritt, On the zeros of exponential polynomials. Ritt reviews certain results of Tamarkin, Polya, and Schwengler, which imply in particular that if an exponential polynomial $f(z)$ does not have any zeroes, then it is a monomial $f_\alpha \exp(\alpha z)$. Ritt's own theorem is that if $f(z)$ and $g(z)$ are exponential polynomials, and if the roots of $f(z)$ are all roots of $g(z)$ (with multiplicity), then their ratio is another exponential polynomial. Thus in our situation $a(p)$, $b(p)$, and $c(p)$ are all proportional up to a constant and an exponential factor. Thus, $A$, $B$, and $C$ must be the same vectors up to permutation, repetition, and rescaling of the coordinates. Repetition is an operation that hasn't yet been analyzed. If $A^{\oplus n}$ denotes the $n$-fold repetition of $A$, then $||A^{\oplus n}||_p = n^{1/p}||A||_p$. Again, since geometric sequences with distinct ratios are linearly independent, Steve's equation is not consistent if $A$, $B$, and $C$ are repetitions of the same vector by different amounts.

The same argument works for the generalized equation $$x_1||A_1||_p + x_2||A_2||_p + \cdots + x_n||A_n||_p = 0.$$ The result is that any such linear dependence trivializes, after rescaling the vectors and permuting their coordinates.

Update (by J.O'Rourke): Greg's paper based on this solution was just published:

"Norms as a function of $p$ are linearly independent in finite dimensions," Amer. Math. Monthly, Vol. 119, No. 7, Aug-Sep 2012, pp. 601-3 (JSTOR link).

$\endgroup$
4
  • 1
    $\begingroup$ That's a very nice solution. I would have never guessed that expressing the p-norm in that way would be productive. $\endgroup$ Dec 21, 2009 at 20:38
  • 2
    $\begingroup$ Thanks for saying so! Note that the driving idea is analytic continuation in $p$. In my thinking, the specific expression appeared only as a corollary of that strategy. (On the other hand, there isn't any other direct definition of exponentiation with an irrational exponent.) $\endgroup$ Dec 21, 2009 at 21:11
  • $\begingroup$ Somehow the claim that "norms as a function of $p$ are linearly independent" reminds me of this question: mathoverflow.net/questions/31458/… Maybe your approach can actually also answer that question? (I might be wrong because I've read both only superficially) $\endgroup$
    – Suvrit
    Aug 18, 2012 at 10:30
  • 1
    $\begingroup$ For those (like me) who don't have an AMM subscription, Greg's preprint is on arXiv: arxiv.org/abs/1102.5026 $\endgroup$ Aug 22, 2012 at 12:12
0
$\begingroup$

if you suppose that all the $a_i$, all the $b_i$, and all the $c_i$ are distinct, can't you do that by induction ? One can assume wlog that $a_1 > \ldots > a_d > 0$ and $b_1 > \ldots > b_d > 0$ etc.. so that taking $p \to \infty$ you can see that $a_1+b_1=c_1$. Hence $$a_1\left(1+\sum_2^d \left(\frac{a_k}{a_1}\right)^p\right)^{1/p} + b_1\left(1+\sum_2^d \left(\frac{b_k}{b_1}\right)^p\right)^{1/p} = c_1\left(1+\sum_2^d \left(\frac{c_k}{c_1}\right)^p\right)^{1/p}$$ and a Taylor expansion for $p \to \infty$ tells you that $\frac{a_2}{a_1}=\frac{b_2}{b_1}=\frac{c_2}{c_1}$. Continuing this way, one can see that the only family of solutions is $A=\lambda C$ and $B=(1-\lambda) C$. Too simple to be true ?

$\endgroup$
2
  • $\begingroup$ Perhaps this is an entirely rigorous approach, but I just don't see it. (Sorry if I'm slow... I'm not a mathematician.) $\endgroup$ Dec 14, 2009 at 15:49
  • $\begingroup$ There's probably a way to make something like this approach work, but I don't know what Alekk means by "a Taylor expansion for $p\to \infty$" here. $\endgroup$ Dec 15, 2009 at 14:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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