3
$\begingroup$

Let $v_1,v_2 \in \{0,1\}^n$. Denote $v_1v_2=((v_1)_1 (v_2)_1, \ldots, (v_1)_n (v_2)_n)$ and $|v|=\sum v_{i}$. \begin{align} {\scriptsize f(v_1, v_2) = \sum_{x_1=0}^{|v_1|} \sum_{x_2=0}^{|v_2|} \sum_{d=0}^{|v_1 v_2|} \frac{1}{2^{|v_1|+|v_2|-|v_1 v_2|}} \biggl| {|v_1| - |v_1 v_2| \choose x_1 - d} {|v_2| - |v_1 v_2| \choose x_2 - d} - {|v_1| - |v_1 v_2| \choose x_1 + 1 - d} {|v_2| - |v_1 v_2| \choose x_2 + 1 - d} \biggr|.} \end{align} I want to estimate $f(v_1, v_2)$ when $|v_1|, |v_2| \to \infty$.

As a first step, I obtain \begin{align} { \scriptsize f(v_1, v_2) = \sum_{x_1=0}^{|v_1|} \sum_{x_2=0}^{|v_2|} \sum_{d=0}^{|v_1v_2|} \frac{1}{2^{|v_1|+|v_2|-|v_1v_2|}} \biggl| \left( 1- \frac{(|v_1|-|v_1v_2|-x_1+d)(|v_2|-|v_1v_2|-x_2+d)}{(x_1+1-d)(x_2+1-d)} \right) {|v_1| - |v_1v_2| \choose x_1 - d} {|v_2| - |v_1v_2| \choose x_2 - d} \biggr|, } \end{align}

How to estimate $f(v_1,v_2)$? Thank you very much.

Improve this question
$\endgroup$
7
  • $\begingroup$ Have you any further information on the behaviour of $|v_{1} v_{2}|$ ? As it stands it could be anything in $\left [ 0, \min(|v_{1}|,|v_{2}|) \right]$. Maybe $|v_{1} v_{2}|= O(\min(|v_{1}|, |v_{2}|) )$ ? $\endgroup$
    – Johannes Trost
    Commented Aug 5, 2018 at 12:42
  • $\begingroup$ @Johannes Trost, thank you very much. The vectors $v_1, v_2$ are given. So $v_1 v_2$ is known and $|v_1 v_2|$ is known. $\endgroup$
    – Jianrong Li
    Commented Aug 5, 2018 at 13:06
  • $\begingroup$ So you are not looking for an asymptotic expansion, but rather an efficient (approximate) algorithm for large $|v_{1}|$, $|v_{2}|$ ? $\endgroup$
    – Johannes Trost
    Commented Aug 5, 2018 at 13:30
  • $\begingroup$ @JohannesTrost, I am looking for something like ${2n \choose n} \sim \frac{4^{n}}{\sqrt{n \pi}}$ ($n \to \infty$). $\endgroup$
    – Jianrong Li
    Commented Aug 5, 2018 at 13:40
  • $\begingroup$ The asymptotics will be very different depending on the size of $|v_{1} v_{2}|$. If the vectors have a small overlap, $|v_{1} v_{2}|\ll \min(v_{1}, v_{2})$, then one might neglect $|v_{1} v_{2}|$. If the vectors have large overlap, then $|v_{1} v_{2}| = O(\min(v_{1}, v_{2}))$ and should not be neglected. Or let it be $|v_{1} v_{2}|= O(\min(v_{1}, v_{2})^\nu)$ with some real exponent $\nu$, presumably smaller than one. And these are only some examples. The results could be very different in all these cases. Before I start working, it would be helpful, if many possibilities could be excluded. $\endgroup$
    – Johannes Trost
    Commented Aug 5, 2018 at 14:20

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .