Edit: Since the geometric approach did not work, I try now another approach: phrasing the problem as a quadratic programme.

Probabilistic version. Let $x=(x_1,x_2, \ldots) $ be an ergodic random sequence of bits. Let $k $ be a positive integer, and $i$ a random integer uniformly distributed in $\{1,\ldots, k\} $ independently of $x $. Is it alway the case that $Cov (x_1,x_i) \geq 0$?

Specifically, does the above hold when $x $ is a random rotation of a fixed periodic binary sequence?

Quadratic programming version. For integers $n\geq k>0$, let $f$ be the following quadratic form: $$f(x_1,\ldots,x_n)=\sum_{i=1}^n\sum_{j=0}^{k-1}x_ix_{i+j\bmod n}.$$ Is it true that the minimum of $f$ over the unit simplex is attained at $(1/n,\ldots,1/n)$? Where the unit simplex is the set $\{x\in\mathbb R^n:x_i\geq 0\forall i,\ \sum x_i=1\}$.

Geometric version. Let $v_1,\ldots,v_k$ be vectors in a euclidian space. Suppose that the inner products satisfy $v_i\cdot v_j=f(|i-j|)$ for some function $f\colon\{0,\ldots,k-1\}\to\mathbb R$. Is it necessarily the case that $f(0)+\cdots +f(k-1)\geq 0$?


Edit: Please note that this answer does not solve the problem. It only shows that the attempt to reduce the problem to a geometric problem fails.

I think a have a counterexample to the geometric version with $k=3$. Let $$ v_1=(\sin a,\cos a,0) ,$$ $$ v_2=(0,\sin b,\cos b) ,$$ $$ v_3=(-\sin a,\cos a,0). $$ Then, $v_1\cdot \sum v_i = (\cos a)(\sin b+2\cos a) $, which can be made negative by choosing $a $ and $b $ adequately.


The answer is "no". Here's a counterexample to the probabilistic version which translates to counterexamples to the other version. Consider the periodic binary sequence $a=(11000)^\omega $. Now, let $x $ be a random rotation of $a $. The expectation of $x_i$ is $2/5$, which is greater than $E [x_i|x_1=1]=3/8$.


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.