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


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$.

  • 2
    $\begingroup$ 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$. $\endgroup$ – Hagen von Eitzen Apr 18 '16 at 10:47
  • $\begingroup$ Oh I see your point. I will edit to avoid this confusion, the degree of $\alpha$ and $\beta$ being at most $n$. Thank you $\endgroup$ – 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).


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.