Take $g_i$ to be a geometric random variable with parameter $1/2$, such that $$P(g_i = k) = \frac{1}{2^{k+1}}$$ for any integer $i$.

I'm surprised at how much more difficult it is to evaluate this sum (of independent variables)

$$\sigma \sim \sum_{i=1}^{N}ig_i = g_1 + 2g_2 + \dots + Ng_N$$

than this simpler, similar sum (also of independent variables)

$$\nu \sim \sum_{i=1}^{N}g_i = g_1 + g_2 + \dots + g_N$$

I understand that the distribution of $\sigma$ is related to the number of lattice paths from $(0,0)$ to $(N,k)$ which take only north or east steps and enclose an area $n$, summed over all $k$, i.e.

$$P(\sigma = n) = \sum_{k=1}^{\infty}\frac{1}{2^{N+k}}p(n,\{k\},N)$$

where $p(n,\{k\},N)$ is the number of integer partitions of $n$ into exactly $k$ parts none of which are larger than $N$. This is becuase $g_1 + 2g_2 + \dots + Ng_N$ is actually a Ferrer's diagram (whose boundary is a lattice path). Alternatively, write the generating function of $\sigma$ $$\mathbb{E}(z^{\sigma})=\prod_{i=1}^{N}\frac{1}{2-z^i}$$ and ask for the coefficient of $z^n$, which is $P(\sigma = n)$. I cannot find a closed form for this even in a limit. Can anyone advise?

Also, if $\nu$ has the negative binomial distribution, perhaps so does $\sigma$? If not, is there some limit where this is the case?

  • 1
    $\begingroup$ Hint: the generating function of $g_i$ is $G(t)=1/(2-t)$, while that of $ng_i$ is $G_n(t)=1/(2-t^n)$. $\endgroup$ – Yves Daoust Jun 16 '16 at 9:24
  • $\begingroup$ Yes, I have the generating function. The sum $\sigma$ is the product of what you write above. This leads to the lattice path idea. $\endgroup$ – Alexander Kartun-Giles Jun 16 '16 at 9:25
  • $\begingroup$ Is it impossible to get a closed form for the coefficients of the generating function? $\endgroup$ – Alexander Kartun-Giles Jun 16 '16 at 9:27
  • 1
    $\begingroup$ If I am right, all the roots are simple and decomposition in elementary fractions could be possible. $\endgroup$ – Yves Daoust Jun 16 '16 at 9:35
  • 1
    $\begingroup$ Impossible isn't English. :) $\endgroup$ – Yves Daoust Jun 16 '16 at 9:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.