6
$\begingroup$

Let $p_n$ be a probability distribution on the positive integers $n$. Let $$ \frac{1}{1-\sum_{n\geq 1} p_nx^n}=\sum_{k\geq 0}a_kx^k. $$ Suppose there does not exist an integer $d>1$ such that $d|n$ whenever $p_n\neq 0$. I remember once seeing a proof of the result $$ \lim_{k\to\infty} a_k = \frac{1}{\sum_{n\geq 1}np_n}, $$ but I cannot recall the proof. Can someone provide such a proof? Problem A6 on the 1960 Putnam exam is the case $p_1=\cdots=p_6=1/6$. The result is intuitively clear, since if we pick integers $n_1,n_2,\dots$ from the distribution $p$, then $a_k$ is the probability that some $n_1+n_2+\cdots + n_j=k$. Now $E:=\sum_{n\geq 1}np_n$ is the expected value of $k$. Thus on the average we are picking every $E$th positive integer, so a proportion $1/E$ should be chosen.

Note. One way to prove the formula would be to show that the function $$ \frac{1}{1-\sum_{n\geq 1} p_nx^n} -\frac{1/E}{1-x} $$ has radius of convergence greater than 1.

$\endgroup$
1
  • $\begingroup$ The function may be unbounded when $x$ goes to $1 - 0$. Say, for $p_n=1/(n(n+1))$ it equals $1 /((x-1)\log(1-x))$. $\endgroup$ Mar 10, 2019 at 10:30

2 Answers 2

7
$\begingroup$

This is proved in Spitzer's "Principles of Random Walk", claim P3 of Section 9 (p.100 of the second edition).

$\endgroup$
7
$\begingroup$

This result belongs to P. Erdös, W. Feller, and H. Pollard (1949). It worth mention that if $\sum a_n p_n<\infty$, this follows from Wiener division theorem in the algebra of absolutely summable Fourier series (which has a famous Banach algebra proof proposed by Gelfand as the application of maximal ideals in Banach algebras theory): $$f(x):=\frac{1-\sum p_nx^n}{1-x}=\sum_n p_n(1+x+\dots+x^{n-1})$$ is absolutely summable and satisfies $f(e^{i\alpha})\ne 0$ for all real $\alpha$ (that is equivalent that no $d>1$ divides all $n$ with $p_n\ne 0$), by Wiener theorem it implies that $1/f=\sum (a_k-a_{k-1})x^k$ is also absolutely summable power series and $\sum_k (a_k-a_{k-1})=\lim a_k=1/f(1)=1/\sum np_n$.

According to Korevaar's book on Tauberian theory (2004), the analytic proof of the $\sum np_n=\infty$ case is still open. Korevaar refers to W. Feller (An introduction to probability theory and its applications, vol. 1, Chapter 15) and G. Grimmet and D. Stirzaker (Probability and random processes, 1992) for the probabilistic proof covering the cases both of finite and infinite expectation.

$\endgroup$

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.