# Random Point on Infinite Line Paradox

I've invented a paradox, or at least I think I have. Here is how it goes:

On an infinite line, a point is placed at random. You start at point 0 on the line, and your job is to find the point, but you can only recognize that you have found it by standing on it. You can only move left or right along the line.

Logically, you would want to go the greatest distance possible in either direction before turning around, as that would prevent backtracking the best. But you do intend to eventually find the point given infinite time, which would be impossible if you only go in one direction for infinity- turning around is a necessity. So you have guaranteed inefficiency, that is, you want to go as far as you possibly can before turning around but you can not go as far as you can, as that would strip you of the assurance of finding the point, cutting the odds down to 50%.

So the question is: have I really invented this paradox. More specifically, is this a paradox and has it been thought of before?

-
Is the line discrete or continuous (i.e. is it $\mathbb Z$ or $\mathbb R$)? –  Asaf Karagila Jan 31 '13 at 0:40
Why would you want to prevent backtracking? Do you get paid more if you find the point faster? If so, what is the payoff as a function of the time you take? –  Trevor Wilson Jan 31 '13 at 0:42
On an infinite line, a point is placed at random... End of the road. –  Did Jan 31 '13 at 0:44
Even with the very naive formulation, what exactly is the paradox??? –  Ittay Weiss Jan 31 '13 at 0:53
If the distribution is unspecified, part of the problem does have a meaning: "An arbitrary point on the real line is chosen. Is there a strategy that is guaranteed to find the point?" But then you want to ask the question, "Which is the most efficient strategy?", for which you have to define efficiency, perhaps in terms of the expected time to find the point. And that has no meaning unless the distribution is specified. –  Rahul Jan 31 '13 at 1:00

As Trevor pointed out in a comment, "paradox" need not mean a contradiction in mathematics. It could mean a contradiction between a mathematical result and our intuition (e.g., the Banach-Tarski paradox), in which case it suggests either refining our intuition to incorporate the surprising mathematical knowledge or modifying the mathematical model to match our intuition more closely. In the case at hand, the situation is complicated by the presence of (at least) two ingredients in the OP's intuition that contradict the mathematical theory. The first such ingredient is the idea that it makes sense to talk about placing a point "at random" on an infinite line without specifying a probability distribution. The second is the assumption that there should be an optimal strategy for finding such a point. Even if one removes the first problem by specifying a probability distribution, and if one then uses that distribution to define the efficiency of a strategy in terms of the expectation of the time needed to find the point, there is no guarantee that this expectation is finite (for any strategy), and, even if it is finite for some strategies, there is no guarantee that there is a strategy minimizing this expectation.

Mathematicians like me will regard these problems as indicating that the OP's intuition is simply wrong and needs to be corrected in the light of the mathematics. An alternative possibility is that the OP might be able to develop a mathematical theory that incorporates the problematic intuitions and allows a precise formulation of the "paradox". I expect this alternative possibility to be very unlikely, but I won't say it's absolutely impossible.

Though it's tangential to the question, let me mention a related problem that I heard many years ago from Ingo Wegener. Fix some probability distribution on the interval $[-1,1]$, for example the one whose density function is the tent-shaped $p(x)$ given by $x+1$ for $x\leq0$ and $1-x$ for $x\geq0$. Suppose a point is chosen at random in $[-1,1]$ with respect to your fixed distribution. You are standing at $0$, you don't know where the point is, and you want to reach the point as quickly as possible by walking back and forth at unit speed. You can certainly succeed in time at most $3$ by walking all the way to one end of the interval and then, if necessary, back to the other end. So the expected time is finite for this strategy. But, for typical probability distributions, there are other strategies that do better (i.e., succeed after lower expected time). The problem is to find the optimal strategy for a given distribution and its expected time. (It's not obvious to me at the moment that the optimum must be achieved, so maybe the problem was to find the infimum, over all strategies, of the expected times and to find a sequence of strategies approaching the infimum.) At the time, Ingo told me that the problem is open even for the "tent" distribution; I don't know whether it has been solved since then.

-

Let's consider the discrete version, because it is less complicated. It is only a paradox if you consider the following two assumptions to be intuitively correct:

(1) The distribution of the point's placement is uniform over all of $\mathbb{Z}$.

(2) Given a strategy (e.g. "always move left" or "always move right",) if for every finite time interval, that strategy maximizes the chance of finding the point within that time interval, then that strategy maximizes the chance of finding the point eventually.

Assume without loss of generality that you start at the origin, and begin by moving one step to the right. If you haven't found the point at time $n$, all you know is that it is somewhere outside the bounded interval that you've explored. If the distribution were uniform, you'd conclude that it was equally likely to be to the left or to the right. You'd rather find it sooner than later, so for any given $N$ to maximize your chance of finding it before time $N$ the best strategy is to keep moving to the right. By (2) this strategy would maximize your chance of finding the point eventually, but it doesn't because it makes the chance equal to 1/2 whereas the "zig-zag" strategy makes the chance equal to 1.

Therefore at least one of (1) and (2) must fail. In the usual formulation of "chance" as probability, (2) holds but (1) fails. One could imagine some other formulation of "chance" that allows (1), but then (2) or some unstated assumption would have to fail. Whether this is a paradox depends on your intuition regarding (1) and (2) and the other unstated assumptions.

I'm sure that people have considered problems like this before (I have) but I'm not sure whether anyone has thought of them as paradoxes.

-
(1) is wrong right off the bat because there is no uniform distribution over $\mathbb Z$. –  Rahul Jan 31 '13 at 1:04
Correct. That doesn't address the question of whether it is a paradox. –  Trevor Wilson Jan 31 '13 at 1:05
For example, the Banach--Tarski paradox is a paradox because many people start with the intuition that equi-decomposability preserves Lebesgue measure. This turns out to be false. But instead of just saying "Theorem: equi-decomposability does not preserve Lebesgue measure" we call it a paradox. –  Trevor Wilson Jan 31 '13 at 1:06

Your point is uniformly distributed throughout the entire real line, from $-\infty$ to $\infty$. No, you will never find your point, ever. It is trivial to show that this is absurd, but imagine the probability of finding the your spot at any point is $P$. Now try to calculate the probability of finding your point within a distance $d$ of $x=0$. Since your probability is defined as $\frac{\text{probability of event happening}}{\text{sum of all probabilities}}$, we calculate the probability as $$\frac{\int_{-d}^dPdx}{\int_{-\infty}^{\infty}P dx} = \frac{2d}{\infty} = 0.$$

Therefore, given that you have traveled any distance $d$, there is $0$ probability that you will find your point.

-