Proving Equal Set Sizes in Sequential Point Selection on a Real Interval with Variable-Length Intervals

Question

I'm here as an engineer working on a point sampling algorithm and I've noticed that when I perform the algorithm on an ordered set of points in one direction it selects the exact same number of points as when I perform this algorithm in the opposite direction. It's not obvious from the algorithm that this should always be the case, but I've ran a simulation in python where I tested this property on 10 millions sets of 100 points with random intervals, and it seems to always hold true. I'd like to prove this.

I did my best to formulate it in a mathematical way:

Problem Formulation:

Let $L$ be a line segment representing a range $[a, b]$, where $a < b$ and $a, b \in \mathbb{R}$. On $L$, there is a set of points $P = \{p_1, p_2, \ldots, p_n\}$ such that $a = p_1 < p_2 < \ldots < p_n = b$.

Define an interval length $m$ where $m$ is greater than or equal to the largest interval between consecutive points in $P$. Use the following selection process:

1. Start with the first point $p_1 = a$ and define an interval $[p_1, p_1 + m]$.
2. Identify the last point $p_k \in P$ within this interval such that $p_k \leq p_1 + m$, and add $p_k$ to a set $S$.
3. Repeat this process from $p_k$, defining each new interval starting from the last selected point and continuing until reaching $p_n = b$, adding selected points to $S$.
4. Similarly, start from $p_n = b$ and move leftward, defining intervals $[p_n - m, p_n]$ and adding selected points to a set $S'$.

Claim: The sizes of the sets $S$ and $S'$ are equal for any distribution of points in $P$.

In summary: the algorithm picks samples by going over an ordered set of points in sequence, and every time the distance to the last sample gets bigger than some maximum interval $m$, it selects the last point that was still within the interval, thereby guaranteeing that samples are never further apart than $m$. When executed backwards the algorithm often selects different points, yet the number of selected samples seems to always be the same. I have a hard time proving this and would appreciate any help.

Answer 1

As Emil mentioned in the comments this forum is for math research questions and this question would have been better suited for math.stackexchange.com. My apologies for this oversight.

Nevertheless, even with Emil's comments I was still not convinced the algorithm guaranteed the same number of hops in both directions. I've chosen not to go to math.stackexchange yet and first give it a couple more tries myself. I think I've solved it and want to put the answer here for completeness:

Let:

• $L$ be a line segment representing a range $[a, b]$, where $a < b$ and $a, b \in \mathbb{R}$.
• $P = {p_1, p_2, \ldots, p_n}$ be a set of points along $L$ such that $a = p_1 < p_2 < \ldots < p_n = b$.
• $S = {s_1, s_2, \ldots, s_k}$ be the set of sampled points generated by starting at $p_1$ and moving rightward with a maximum interval length $m$, where $m$ is greater than or equal to the largest interval between consecutive points in $P$.
• $S' = {t_1, t_2, \ldots, t_l}$ be the set of sampled points generated by starting at $p_n$ and moving leftward, using the same interval length $m$.

Our goal is to prove that: $$ |S| = |S'| $$

For each sample $s_i$ in $S$, the next sample $s_{i+1}$ is the farthest point $p_u$ such that: $$ p_u - s_i \leq m $$

For each sample $t_j$ in $S'$, the next sample $t_{j+1}$ is the farthest point $p_v$ before $t_j$ such that: $$ t_j - p_v \leq m $$

Constraint on the second sample in the backward direction:

• By definition, $t_1 = s_k$
• For $t_2$ (the next sample in the backward direction after $t_1$), we find that:
  • Upper bound: $t_2$ must be at least as small as $s_{k-1}$, because $s_{k-1}$ could reach $s_k$ within the distance constraint $m$.
  • Lower bound: $t_2$ cannot be equal to or smaller than $s_{k-2}$, because if $t_2 \leq s_{k-2}$, then the step from $s_{k-2}$ to $s_k$ would have been feasible within the distance constraint $m$, meaning $s_{k-1}$ would not have been present in $S$.
• Therefore, $t_{2}$ is constrained in the range $(s_{k-2}, s_{k-1}]$.

Inductive Step for Subsequent Samples in $S'$:

• If $t_j$ lies in the range $(s_{i-1}, s_i]$, then by the sampling rule:
  • Upper bound: $t_{j+1}$ cannot be larger than $s_{i-1}$, as $s_{i-1}$ could reach $s_i$, so $t_j$ must be able to reach at least $s_{i-1}$.
  • Lower bound: $t_{j+1}$ cannot be equal to or smaller than $s_{i-2}$, because $t_j > s_{i-1}$ by assumption. If $t_{j+1} \leq s_{i-2}$, then the distance from $s_{i-2}$ to $s_{i-1}$ would not have been maximized, meaning $s_{i-1}$ would not have been present in $S$.
• Thus, we confirm that: $$ t_{j+1} \in (s_{i-2}, s_{i-1}] $$
• This reasoning applies inductively, ensuring that each subsequent point in $S'$ is constrained to lie within a range determined by prior points in $S$, preserving the symmetry of sampling.

Conclusion:

• Each $t_j$ in $S'$ aligns with an interval constrained by points in $S$, making it impossible to add or skip points relative to $S$.
• This guarantees that the number of sampled points is identical in both directions, so: $$ |S| = |S'| $$