Let's say I have a sequence $\{x_1,...x_n\}\in\mathbb{R}^+$, where $x_i Is it possible to form a new sequence $z_m$ by inserting values $y_k$ in between the $x_n$ as necessary (for e.g., ${x_1,y_1,y_2,x_2,y_3,...y_k,x_n}$) such that $z_{i+1}-z_i=c$, a constant? Are there cases where this can/cannot be done? How does one prove if it is/is not possible? Lastly, I really don't know what tags to assign, so hope someone helps me out here.
Equally spaced sequence from a randomly spaced sequence
-
1This is possible iff $(x_{i+1}-x_i)/(x_1 - x_0)$ is rational for all $i$. – 2011-03-30
3 Answers
In general this is impossible for nearly-trivial reasons; if it were possible to 'equispace' the sequence then it would imply that all the differences $x_{i+1}-x_i$ are multiples of some common difference, but 'generically' a finite set of real numbers are mutually algebraically independent and so certainly linearly independent. If $x_1=1$, $x_2=2$, and $x_3=\pi$, for instance, there certainly can't be any such $z$ sequence.
You can do it if only if all the $x_{i+1}-x_i$ are whole multiples of some number. If they are, you just put enough $y$'s in between each pair of $x$'s to make the gaps match. If they are not, you can't. Think about $\{1,\sqrt{2},5\sqrt{2}-4\}$, where you can put three $y$'s in the second gap and get there, then think about $\{1,\sqrt{2},2\}$ where it cannot be done.
There is probability 0 of being able to do this for $x_1$,$x_2$ and $x_3$, as you need $x_3 -x_2$ to be a rational multiple of $x_2-x_1$ and it almost always will be an irrational multiple. It just gets worse with more $x_i$.
-
0Without knowing the distribution, you can't say the probability is $0$. – 2011-03-30
-
0Fair enough, though I took the distribution be random too in some sense. – 2011-03-30