2
$\begingroup$

Suppose we have the following random process. We start with two vectors $a_1=(0)$ and $b_1=(0)$. In going from $i$ to $i+1$, we will a perturbation to $a_i$ and $b_i$. With probability $p$, we perform Case 1, otherwise perform Case 2.

  • Case 1: We pick an element of $a_i$, say at coordinate $x$ (chosen uniformly at random from all coordinates $1,2,\ldots,|a_i|$, where $|a_i|$ is the length of $a_i$), and append it to the end of $a_i$ to form $a_{i+1}$. Similarly, to form $b_{i+1}$ append the element at coordinate $x$ from $b_i$ to the end of $b_i$. The remainder of $a_{i+1}$ and $b_{i+1}$ is the same as $a_i$ and $b_i$, respectively. [The copied element is at coordinate $x$ in both $a_i$ and $b_i$.]

  • Case 2: Choose $x$ and $y$ to be two coordinates chosen uniformly at random from $1,2,\ldots,|a_i|$. If $x \neq y$ then set $a_{i+1}[x]=a_i[x]+1$ and $b_{i+1}[y]=b_i[y]+1$ (if $x=y$ then don't do anything [it's not clear at this point whether or not I want to enforce $x \neq y$]). Again, the remainder of $a_{i+1}$ and $b_{i+1}$ is the same as $a_i$ and $b_i$, respectively.

Question: What is the expected dot product of $a_i$ and $b_i$? That is, what is $\mathrm{E}(\sum_x a_i[x] \cdot b_i[x])$?

So here's an example of what these vectors could look like:

i a_i b_i
1 (0) (0)
2 (0,0) (0,0) [case 1 x=1]
3 (0,0,0) (0,0,0) [case 1 x=1]
4 (1,0,0) (0,1,0) [case 2 x=1 y=2]
5 (1,0,0,1) (0,1,0,0) [case 1 x=1]
6 (1,0,0,1) (0,1,0,0) [case 2 x=4 y=4]
7 (1,0,0,2) (0,1,1,0) [case 2 x=4 y=3]

I'm looking at a related problem studying evolving random graphs. In the random graph problem, the two vectors represent the in-degrees and out-degrees of an evolving network over time. In the graph, we can duplicate vertices or add or delete an edge (which is related to cases 1 and 2 above). In this case, the dot product therefore counts the number of directed paths of length 3.

However, the above problem differs from the one I'm considering since (a) it's not necessarily the case that $\sum_x a_i[x]=\sum_x b_i[x]$ and (b) there's nothing to stop parallel edges arising here. Although, I'm hoping that this simplified question will be more answerable and the techniques can be re-used.

$\endgroup$
  • $\begingroup$ This is one of those rare cases where a little more formality would be welcome. Probability statements can be notoriously ambiguous and this one invites ambiguity on many levels. Perhaps a small example would clarify. Also, please reread your question: some words are obviously missing. $\endgroup$ – whuber Mar 8 '11 at 2:35
  • $\begingroup$ Is there any motivation behind why the process is the way is is? $\endgroup$ – rm999 Mar 8 '11 at 2:55
  • $\begingroup$ @whuber and rm999: I edited a response into the question. $\endgroup$ – Douglas S. Stones Mar 8 '11 at 3:57
3
$\begingroup$

EDIT 2: We have to simplify the problem by removing the restriction that $x \ne y$ always in case two. Otherwise correlation issues vastly complicate the answer.

Let $|v|$, the 1-norm, denote the sum of the coordinates of the vector. Let $v * w$ denote the coordinate-wise product of the vectors $v$ and $w$. (So the dot-product of $v$ and $w$ is $|v * w|$.

Note that $|a_i| = |b_i|$ always.

In case one: $$E[|a_{i+1}|] = E[|a_{i}| + a_{i+1}] = E[|a_{i}|] + E[a_{i+1}]$$ $$= E[|a_{i+1}|] + \frac{1}{i}E[|a_{i+1}|]= \frac{i+1}{i} E[|a_i|],$$ $$E[|a_{i+1}|^2] = E[(|a_{i}| + a_{i+1})^2] = E[|a_i|^2 + 2|a_i|a_{i+1} + a_{i+1}^2]$$ $$= E[|a_i|^2] + 2E[|a_i|a_{i+1}] + E[a_{i+1}^2]$$ $$= E[|a_i|^2] + 2E[E[|a_i|a_{i+1}]:|a_i|=k] + E[a_{i+1}^2]$$ $$= E[|a_i|^2] + 2E[kE[a_{i+1}]:|a_i|=k] + E[a_{i+1}^2]$$ $$= E[|a_i|^2] + 2E[k\frac{1}{i} k:|a_i|=k] + E[a_{i+1}^2]$$ $$= E[|a_i|^2] + \frac{2}{i}E[|a_i|^2] + E[a_{i+1}^2]$$ $$= E[|a_i|^2] + \frac{2}{i}E[|a_i|^2] + E[E[a_{i+1}^2] : |a_i| = k]$$ $$= E[|a_i|^2] + \frac{2}{i}E[|a_i|^2] + E[E[\frac{k}{i}^2] : |a_i| = k]$$ $$= E[|a_i|^2] + \frac{2}{i}E[|a_i|^2] + E[\frac{1}{i^2}|a_i|^2]$$ $$= \frac{(i+1)^2}{i^2} E[|a_i|^2],$$ $$E[|a_{i+1}*b_{i+1}|] = \frac{i+1}{i} E[|a_i * b_i|].$$

In case two, $$E[|a_{i+1}|] = \frac{i+1}{i} E[|a_i|] + 1,$$ $$E[|a_{i+1}|^2] = \frac{(i+1)^2}{i^2} E[|a_i|^2] + 2E[|a_i|] + 1,$$ $$E[|a_{i+1}*b_{i+1}|]= E|a_i * b_i| + E[a_{i+1} b_{i+1}]$$ $$=E|a_i * b_i| + E[kE(a_{i+1}): b_{i+1} = k]$$ $$=E|a_i * b_i| + E[k(\frac{1}{i}|a_i| + 1): b_{i+1} = k]$$ $$=E|a_i * b_i| + E[(\frac{1}{i}k|a_i| + k): b_{i+1} = k]$$ $$=E|a_i * b_i| + \frac{1}{i} E[(\frac{1}{i}|b_i|+1)|a_i|] + E[b_{i+1}]$$ $$=E|a_i * b_i| + \frac{1}{i^2} E[|a_i||b_i|]+ \frac{1}{i} E[|a_i|] + \frac{1}{i}E[|b_i|] + 1$$ $$=E|a_i * b_i| + \frac{1}{i^2} E[|a_i|^2]+ \frac{2}{i} E[|a_i|] + 1.$$ [The last equation would be much more complicated if we require $x \ne y$ in case 2.]

So overall,

$$E[|a_{i+1}|] = \frac{i+1}{i} E[|a_i|] + (1-p),$$ $$E[|b_{i+1}|] = \frac{i+1}{i} E[|b_i|] + (1-p),$$ $$E[|a_{i+1}|^2|]= \frac{(i+1)^2}{i^2} E[|a_i|^2] + (1-p) [E[|a_i|^2] + 2E[|a_i|] + 1]$$ $$E[|a_{i+1}*b_{i+1}|] = \frac{p+i}{i} E[|a_i * b_i|] + (1-p)[\frac{1}{i^2} E[|a_i|^2]+ \frac{1}{i} [2E[|a_i|] + 1].$$

Which allows us to efficiently tabulate the answer for $i = 1, 2, 3, ...$

DISCLAIMER: I have yet to numerically verify this answer.

$\endgroup$

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.