Does anyone have any idea how to find a closed form or a good closed form approximation to $$\min\arg_j\left[i = \sum_{k=1}^{j} b_k\right]$$
where $b \in Z_2^n$?
For example, $b = [1,1,0,1,0,0,0,1]$, $i \in [1,4]$, $j \in [1, 8]$.
$i = 1,2,3,4$ gives $j = 1,2,4,8$.
Very simply, we are recovering the index $j$ for the $i$th $1$.
The sum accumulates the $1$'s, and the $\min\arg$ finds the minimum argument $j$ that produces that value(the minimum index into $b$).
If $cb$ is the cumulative sum of $b$ then $cb = [1,2,2,3,3,3,3,4]$ and now we are just finding the index of the first occurrence of $i$ in $cb$
One could look at this as a probability density problem, and we want to find out when the probability distribution passes the threshold $i$.
This ultimately occurs in an exponent of a problem I'm working on, and I can't evaluate it in any reasonable way. Any approximations end up being too bad to give convergent results(the convergences end up depending on some features of $b$). e.g., a simple linear approximation can result in invalid results because the problem critically depends on the distribution of $b$ and is too tight to use naive approximations(e.g., $b = 1$).