0

I'm trying to solve a tough balls-in-bins problem by working with generating functions for the distributions of balls in bins at different times. So I have the probability that $k$ bins have some property as $V_k$ and I am working with the generating function for the sequence $v_k$, namely $$ U(x) = \sum_k V_k x^k $$ What is happening when you do that is you are taking whatever equation dictates the behavior of the $V_k$, multiplying by $x^k$ and summing over $k$.

So for example, if I needed a term of the form $\sum_k kV_kx^k$ I could express that as $xU'$ (that is, as $x\frac{dU(x)}{dx}$).

Once you have turned the equations relating $V_k$ into equations (often differential equations) involving $U(x)$ you can solve for $U(x)$ and read off the $V_k$ from the series expansion, for example.

The tough step I have encountered is that the conditions of the problem lead to a term of the form $$ T = \sum_{k,r} rV_rV_{k-1}x^k $$ The obvious thing to try is something like $$ U'U = \sum_{k,r}rV_r V_{k+1-r} x^k $$ and if the difference between $k+1-r$ and $r$ were a constant I could multiply by the approriate power of $x$. But it is not a constant, so this does not work out.

How can I express $\sum_{k,r} rV_rV_{k-1}x^k$ in terms of $U(x)\equiv \sum_k V_k x^k$ and its derivatives and functions of $x$?

Greg Martin
  • 78,820
Mark Fischler
  • 41,743

1 Answers1

0

We can factor the expression for $T$ as follows:

$T(x) = \sum_{k,r} r V_r V_{k-1} x^k = \left( \sum_k V_{k-1} x^k \right) \left( \sum_r r V_r \right).$

For the first factor, we have $\sum_k V_{k-1} x^k = x \sum_k V_{k-1} x^{k-1} = xU(x)$ (I presume this sum is over $k \ge 1$).

Now, as you've noted, $\sum_r r V_r x^r = x U'(x)$. However, in the above factorisation we do not have the term $x^r$. We can get rid of the $x$-dependence by substituting $x = 1$; that is, $\sum_r r V_r = 1 \times U'(1) = U'(1)$.

Hence we have $T(x) = x U(x) U'(1)$.

Shagnik
  • 3,613