Optimal Talmudic Zigzag

Question

I have a finite sequence of positive real numbers $p_1,\dots, p_n$ and I am looking for a monotonically ascending sequence of indices $z_1,\dots, z_k$ that starts with $z_1 = 1$ and ends with $z_k = n$ in order to maximize the following product over all $k,z_1,\dots, z_k$: $$ \prod_{i = 1}^{k - 1} \frac{p_{z_i} + p_{z_{i + 1}}}{2 \sqrt{p_{z_i} p_{z_{i + 1}}}}. $$ How do I approach this optimization problem? Ideally, I am looking for an efficient algorithm that can find the optimal sequence $(z_i)$ given any input sequence $(p_i)$, typically containing millions of elements.

Answer 1

This is a special case of finding the longest path in a directed acyclic graph. Namely, the vertices of our graph are $1$, $2$, ..., $n$, there is an edge $i \to j$ for each $i<j$ and the length of that edge is $\log \tfrac{p_i + p_j}{2 \sqrt{p_i p_j}}$. We want the longest path from $1$ to $n$.

There are a number of standard efficient algorithms for this; see for example Section 4.7 in Dasgupta, Papadimitriou and Vazirani's Algorithms.

An observation: If we chose to include $z_i$, then we must have $$\frac{p_{z_{i-1}} + p_{z_i}}{2 \sqrt{p_{z_{i-1}} p_{z_i}}}\ \frac{p_{z_{i}} + p_{z_{i+1}}}{2 \sqrt{p_{z_{i}} p_{z_{i+1}}}} \geq \frac{p_{z_{i-1}} + p_{z_{i+1}}}{2 \sqrt{p_{z_{i-1}} p_{z_{i+1}}}}$$ and multiplying this out and rearranging gives $$\left( \frac{p_{z_{i+1}}}{p_{z_i}} - \frac{p_{z_{i}}}{p_{z_{i+1}}}\right) \left( \frac{p_{z_{i}}}{p_{z_{i-1}}} - \frac{p_{z_{i-1}}}{p_{z_{i}}}\right) < 0$$ so either $p_{z_{i-1}} < p_{z_i} > p_{z_{i+1}}$ or $p_{z_{i-1}} > p_{z_i} < p_{z_{i+1}}$. In other words, the sequence $p_{z_1}$, $p_{z_2}$, ..., $p_{z_k}$ is alternating. Finding the longest alternating subsequence of a sequence is a well studied problem, and good algorithms for that might be good heurisitics for this.

Another thought (and I'm going to drop out of this conversation soon): Running times for longest path algorithms depends on the number of edges in the graph. If the optimal solution uses the edge $j \to \ell$, then we must have $p_k$ between $p_j$ and $p_{\ell}$ for all $j < k < \ell$. (Otherwise, inserting $p_k$ would be an improvement.) Let's call $(j, \ell)$ a good pair if this condition holds.

Let's insert a preprocessing step which finds all good pairs $(j, \ell)$ and restrict the graph algorithm to them. Here is how that preprocessing step works. For each $j$, do the following. Suppose $p_{j+1} > p_j$ (if $p_{j+1} < p_j$, reverse all inequalities that follow.) Let $k_j$ be the smallest index $k_j>j$ for which $p_{k_j}<p_j$. If the $p_i$ are independently identically distributed, then $k_j-j=r$ with probability $1/2^{r-1}$ for $r \geq 2$. The good pairs are $(j,\ell)$ with $j < \ell < k_j$ where $p_{\ell}$ is the maximum of $(p_{j+1}, p_{j+2}, \dots, p_{\ell})$. So the expected search time to find $k_j$ is $\sum_{r \geq 2} r/2^{r-1} =3$ and the expected number of such $\ell$ is $\sum_{r \geq 2} 2^{-(r-1)} (1+1/2+\cdots+1/(r-1)) = 2 \log 2 \approx 1.39$.

Thus, if your $p_i$ are independently identically distributed, then in $O(n)$ time you can find the good pairs, and there are only about $1.39 n$ of them. Djisktra's algorithm on a graph with $O(n)$ edges, implemented with a binary heap, runs in time $O(n \log n)$.

Answer 2

It is easy to see that the optimal subsequence needs to be a zigzag. Then, assuming the $(p_i)$ sequence is replaced with its longest zigzag subsequence, one can define cuts as intervals that do not increase the product that needs to be maximized: $$ \operatorname{Cut}(a, b) \Leftrightarrow \prod_{i = a}^{b - 1} \frac{p_i + p_{i + 1}}{2 \sqrt{p_i p_{i + 1}}} \le \frac{p_a + p_b}{2 \sqrt{p_a p_b}}. $$ Also, let an interval be called solid when it does not include any shorter cuts: $$ \operatorname{Solid}(a, b) \Leftrightarrow \nexists i,j \in [a, b]: \operatorname{Cut}(i, j) \wedge j - i < b - a. $$ Finally, it will be particularly useful to distinguish solid cuts: $$ \operatorname{SolidCut}(a, b) \Leftrightarrow \operatorname{Solid}(a, b) \wedge \operatorname{Cut}(a, b). $$ Due to the properties discussed in this paper, any solid cut needs to have an odd length: $$ \operatorname{SolidCut}(a, b) \Rightarrow b - a = 2k + 1 \wedge k \ge 1, $$ and any chain of overlapping solid cuts is also a cut. Thus the optimal subsequence cannot include any elements that are within solid cuts. However, after removing all elements that are within solid cuts, the resulting sequence can have some new solid cuts, so the process needs to be repeated until no cuts remain, reaching the optimal subsequence.