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

If $p<1$ and $X$ is a random variable distributed according to the geometric distribution $P(X = k) = p (1-p)^{k-1}$ for all $k\in \mathbb{N}$, then it is easy to show that $E(X) = \frac 1p$, $\mathop{Var}(X)=\frac{1-p}{p^2}$ and $E(X^2) = \frac{2-p}{p^2}$.

Now consider a "conditional" geometric distribution, defined as follows (if there is standard terminology for this, let me know and I'll call it that):

  1. Fix a set $J\subset \mathbb{N}$ and a number $\mu>0$ (this will eventually be large).
  2. Let $P(X=k) = C \gamma^k$ if $k\in J$ and $P(X=k)=0$ otherwise, where $C>0$ and $\gamma<1$ are chosen so that probabilities sum to $1$ and $E(X) = \mu$.

I'm trying to understand how $E(X^2)$ (or equivalently, $\mathop{Var}(X)$) depends on $J$ and $\mu$. In the case where $J=\mathbb{N}$ the standard results show that $p=\frac 1\mu$ and so $E(X^2) = \mu^2(2-\frac 1\mu)$. I'm interested in the case where $\mu$ becomes very large and would like to obtain a similar estimate $E(X^2) \approx A\mu^2$, for some constant $A>1$, in a more general setting.

The example I'm working with at the moment is $J= \{2^n \mid n\in \mathbb{N}\}$, but ideally I'd like some conditions on the set $J$ that would guarantee an estimate of the above form.

Is there a standard name for these distributions, or a reference where I can read more about them? Are estimates of this form known?

Edit: As Brendan McKay pointed out below, this boils down to understanding the behaviour of the function $g(\gamma) = \sum_{j\in J} \gamma^j$, and in fact the issue that motivated the question I posed can be stated more directly in terms of this function.

The condition $E(X) = \mu$ is equivalent to the equation $\mu = \gamma g'(\gamma) / g(\gamma)$, which determines $\gamma$ implicitly as a function of $\mu$. We would like to understand how $g(\gamma)$ grows as $\mu\to\infty$, and hence $\gamma\to 1$. (In particular, this means we're really interested in the case where $J$ is infinite.)

In the case $J=\mathbb{N}$, one has $g(\gamma) = \frac\gamma{1-\gamma} = 1 - \frac 1{1-\gamma}$, and so $\mu = \gamma (\frac{\gamma}{(1-\gamma)^2}) (\frac{1-\gamma}\gamma) = \frac{\gamma}{1-\gamma}$, so that in fact $g(\gamma(\mu)) = \mu$ and the two quantities go to infinity together.

In the more general case a reasonably simple argument shows that $\lim_{\mu\to\infty} g(\gamma(\mu)) = \infty$ provided $J$ is infinite, but it's not at all clear to me how the rate at which $g$ grows (in terms of $\mu$) depends on $J$ for more general sets.

That's the original motivation -- after some messing around we decided that we could figure out the growth rate if we knew something about $E(X^2)$ as suggested above, and since it was phrased in terms of what seemed to be a reasonably natural probability distribution, we decided to ask it in that form. But now you have the whole story...

share|improve this question
add comment

3 Answers 3

up vote 3 down vote accepted

I'm not sure what you really want but here is a couple of simple minded inequalities that can serve as a baseline.

Below $g=\sum_{k\in J}\gamma^k$, $M=\sum_{k\in J}k\gamma^k$, so $\mu=\frac Mg$. We'll need the counting function $F(n)=\#\{k\in G: k\le n\}$ of the set $J$. I will assume that $F$ is extended as a continuous increasing function to the set $[1,+\infty)$ and that $g\ge 1$.

1) For every $N$, we have the trivial estimate $g\le F(N)+\frac MN$. Taking $N=2\mu$, we get $g\le F(2\mu)+\frac g2$, i.e.,

$$ g\le 2F(2\mu) $$

2) Let $\nu$ satisfy $F(\nu)=3g$. Since $g\ge F(\nu)\gamma^\nu$, we conclude that $\gamma^\nu\le \frac 13$ so $1-\gamma>\frac 1\nu$. Now, for every $N$, we have $$ M\le Ng+(N+\frac 1{1-\gamma})\frac 1{1-\gamma}\gamma^N\le Ng+(N+\nu)\nu e^{-N/\nu}\. $$ Since we clearly have $\nu\ge F(\nu)=3g$, we can choose $N=\nu\log\frac\nu g\ge \nu$. For this choice, the second term on the right is at most $2Ng$, so, dividing by $g$ we get $\mu\le 3N$, i.e., $$ \mu\le 3F^{-1}(3g)\log\frac{F^{-1}(3g)}{g} $$

Examples of what these inequalities yield:

1) Dense set ($F(n)\approx n$). Then $g\approx\mu$

2) Power lacunarity ($F(n)\approx n^p$, $0<p<1$). Then $g$ is between $\mu^p(\log\mu)^{-p}$ and $\mu^p$ up to a constant factor.

3) Geometric lacunarity ($F(n)\approx\log n$). Then $g\approx \log\mu$.

As you see, one can lose a logarithm sometimes but the advantage is that I do not make any regularity assumptions here. Of course, if $F$ is regular enough, you can, probably, do a bit better.

share|improve this answer
    
I like these estimates -- this is the sort of thing I was looking for. The truth is that I didn't have a particularly clear idea of exactly what I wanted when I asked the question, which is why it never really came out as clearly as I'd have liked. It came up in some work a colleague and I are doing, where we started by maximising the entropy of a probability distribution on $\mathbb{N}$ with a fixed mean -- which led to the geometric distribution -- and then wanted to consider the case where the support of the distribution was forced to lie in $J$. (ctd...) –  Vaughn Climenhaga Nov 28 '11 at 5:45
    
(ctd...) In order to get the sorts of estimates we wanted for the application we had in mind, we thought we'd need some more detailed information about the relationship between $g$ and $\mu$ in terms of the structure of $J$, and so I asked this question in a rather vague and open-ended attempt to see what might be true. In the end we found another way to deal with the issue we were faced with, that doesn't require dealing with conditional geometric distributions, but I still find this question interesting for its own sake. –  Vaughn Climenhaga Nov 28 '11 at 5:48
add comment

Define $g(\gamma) = \sum_{j\in J} \gamma^j$. The condition $E(X^2)\sim A\mu^2$ as $\mu\to\infty$ seems to be equivalent to $$ \frac{g(\gamma) g''(\gamma)}{(g'(\gamma))^2} \to A $$ as $\gamma\to 1$ from below. Alternatively define $h(x)=\sum_{j\in J} ~e^{-jx}$ and then you want $$ \frac{h(x)h''(x)}{(h'(x))^2} \to A$$ as $x\to 0$ from above.

Of course these are translations of the problem rather than solutions, but I mention them as someone will probably see what to do next.

share|improve this answer
    
If $J$ is finite then this is obviously a closed-form solution. Otherwise the answer depend heavily on what form $J$ is in. e.g. if $J$ is not a decidable set then very few digits of $A$ should be computable. For any set whose generating function has a nice closed form, there will be a nice formula for $A$. It seems like the only fully general question left is whether $A$ is always defined. –  Will Sawin Nov 18 '11 at 7:41
    
@Brendan: I seem to recall seeing one or two equations like this as we derived the question that I posed from the question that originally motivated it... I'll edit the original question to include the motivation as well. Certainly we'd be very happy to understand the limits you point out, and that would suffice... –  Vaughn Climenhaga Nov 18 '11 at 18:05
    
@Will: We're mostly interested in what happens when $J$ is infinite, and in particular in quantifying the behaviour under some conditions on (say) the growth rate of the gaps in $J$, or something like that. (If $J$ has bounded gap size then this should be more or less comparable to the case $J=\mathbb{N}$.) –  Vaughn Climenhaga Nov 18 '11 at 18:07
    
As a consequence, in the case of a $J$ obtained repeating a finite set $F\subset [0,n)$ with periodicity $n$, i.e. $J=F+n\mathbb{N}$, we have $g(x)=(1-x^n)^{-1}P(x)$ with $P(x):=\sum_ {k\in F} x^k$; so for $x\to1$, $g'(x)=nx^{n-1}(1-x^n)^{-2}P(x)+O((1-x)^{-1})$ and $g''(x)=n^2x^{2n-2}(1-x^n)^{-3}P(x)+O((1-x)^{-2})$, whence by Brendan's formula $g''g/(g')^2\to 2$ as $x\to 1$. So every periodic $J$ has $A=2$. –  Pietro Majer Nov 19 '11 at 21:16
add comment

Can you estimate $C$ and $\mu$ etc...using the first term say $j=\min J$?

It seems to me for instance that $1/C=\gamma^j+\gamma^{j_2}+\cdots\leq \sum_{k=j}^\infty \gamma^k=\gamma^j/(1-\gamma)$.

share|improve this answer
    
The issue is that we're really interested in an estimate from the other direction, of the form $1/C \geq$ some function of $\gamma$; in other words, we want a lower bound on how $E(X^2)$ grows in terms of $E(X)$, which is going to depend much more on the behaviour of the tail of $J$ then on the initial terms. –  Vaughn Climenhaga Nov 18 '11 at 18:02
    
Thanks. There's a typo in our edit. It's $g(\gamma)=\frac{1}{1-\gamma}-1$ –  Pietro Poggi-Corradini Nov 19 '11 at 1:41
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.