I'm working on an issue related to Hyperdimensional Computing. In short, I have a $d$-bit array $v$ sampled uniformly from the space of all $d$-bit binary arrays.
Consider the following process: at each step, I uniformly choose one of the $d$ positions of this vector $v$ and flip the bit. My question is: what is the expected number of steps until the vector obtained is orthogonal ($d/2$ distant) to the initial vector?
What I could think of so far is that this process can be expressed as a birth-death process where state $0$ is not absorbing but another state $d/2$ is. In this case the question would be: what is the expected number of transitions, starting from state $0$, to absorption in state $d/2$?
Thank you so much,
I guess these are $\{ -1,1 \}$ bits instead of $\{ 0,1 \}$ bits.
If so then yes, assuming $d$ is even, then you can model this as a symmetric random walk which is a priori on $0,1,\dots,d$ with reflecting boundaries, but can be restricted to $0,1,\dots,d/2$ by making $d/2$ into an absorbing boundary. This random walk describes the number of bits that are different than the original, so it starts at $0$.
So you have $p_{i,i+1}=(d-i)/d$ for $0 \leq i<d/2$, $p_{i,i-1}=i/d$ for $1 \leq i<d/2$ and $p_{d/2,d/2}=1$. Everything else is zero. Say $u(i)$ is the expected absorption time starting at $i$. By considering starting at each state and conditioning on each possible outcome, you get $u(0)=1+u(1),u(i)=1+\frac{(d-i) u(i+1)+i u(i-1)}{d}$ for $1 \leq i<d/2$ and $u(d/2)=0$. This is a linear system you can solve.