# Product of two random polynomials

Let $\alpha,\beta$ be two polynomials of the form $$\alpha(X)=\sum_{i=0}^{n}\alpha_iX^i,\quad \quad \beta(X)=\sum_{j=0}^n\beta_jX^j$$ where each coefficient is $1$ with a probability of $p$ and $0$ with probability $1-p$. The coefficients of $\alpha,\beta$ are all independent. Note that $\alpha,\beta$ are of degree at most $n$.

What can I say about the distribution of the polynomial $H(X)=\alpha(X)\cdot \beta (X)$?

Note that the $k$-th coefficient of $H$ is

$$h_k=\sum_{i=0}^k\alpha_i\beta_{k-i},$$

therefore it is distributed in $[0,k+1]$, but how ?

Note also that the variables $c_i^{(k)}:=\alpha_i\beta_{k-i}$ are $1$ with probability $p^2$ and $0$ with probability $1-p^2$, and are independent for fixed $k$ so I can treat $h_k$ as the sum of independent random discrete variables, which is fairly easy.

However, for different values of $k$ there is correlation between these variables, in other words $H$'s coefficients are not independent.

It looks complicated to characterize such correlation, is there any way to measure it ?

Thank you all

EDIT: As an easy example to see the correlation, note that the probability of $h_1=2$ knowing that $h_0=0$ is $0$.

• The correlation is indeed the tough part, but note for a minor correction that (the way I read the problem statement) $\alpha_n=1$ and $\beta_n=1$ with probability $1$ instead of $p$. – Hagen von Eitzen Apr 18 '16 at 10:47
• Oh I see your point. I will edit to avoid this confusion, the degree of $\alpha$ and $\beta$ being at most $n$. Thank you – Tal-Botvinnik Apr 18 '16 at 11:58

The correlation is actually not too hard to measure. For $k<l$, $\mathbb{E}[H_kH_l]=\sum_{i=0}^k\sum_{j=0}^l\mathbb{E}[\alpha_i\alpha_j\beta_{k-i}\beta_{l-j}]$. If $i=j$ this expectation is easily seen to be $p^3$. If $j=l-k+i$ the same is true. Otherwise the expectation is p^4. The first and second case occur $k+1$ times, and the last occurs $(k+1)(l-1)$ times. This adds up to $(k+1)(l+1)$, as a sanity check, so $\text{Cov}(H_k,H_l)=2(k+1)p^3+(k+1)(l-1)p^4-(k+1)p^2(l+1)p^2=2(k+1)(p^3-p^4)$. In terms of holistically characterising your dependence, you can think of $H_k$, $H_l$ as two Binomial random variables whose trials are actually two part trials, both requiring success, and whose first and last $k+1$ trials share a single dependent part (when we look at the trials individually).