Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Randomly uniformly select $n$ numbers from a set $\{1,2,...,U\}$ with/without replacement, $y_i$ is the $i$th number selected, and $x_i$ is the rank of $y_i$ in the $n$ numbers. The rank is the order of a number after the $n$ numbers are sorted in ascending order.

We can get $n$ data points $(x_1, y_1), (x_2, y_2), ..., (x_n, y_n)$, And a best fit line for these data points can be found by linear regression with the object function $L_{\infty}$ norm. I want to get the bound of its object function.

The object function is to minimize $F(\alpha,\beta)=\max\limits_{1\leq i\leq n} |y_i-\alpha-\beta x_i|$

By using linear regression we can find a $F_{\min}$ that is minimized.

I want a distribution for $F_{\min}$ with respect to different selection of the list, or $\Pr [|F_{\min}-k|>t]$ for some $k$ and $t$.

share|improve this question
    
What's the distribution of the $n$ numbers? –  joriki Sep 11 '11 at 9:14
    
@joriki uniform distribution, and there maybe two selection scheme, one is with replacement, another is without replacement. –  Fan Zhang Sep 11 '11 at 10:15
    
If you are selecting with replacement, and you pick the same number twice, how do you define the rank? Do you have two data points $(x,k)$ and $(x,k+1)$ or one data point $(x,k+1/2)$? –  Craig Sep 14 '11 at 15:30
    
@Craig I think it should be the case: two points $(x,k)$ and $(x,k+1)$ –  Fan Zhang Sep 14 '11 at 16:00
    
Sorry, should be $(k,y)$ and $(k+1,y)$. Got confused as to which was the rank and which the value. –  Craig Sep 15 '11 at 0:39
add comment

1 Answer

up vote 0 down vote accepted
+50

Okay, let's work backwards. Suppose we have $\alpha, \beta$ that minimizes $\max_i | y_i - \alpha x_i - \beta |$, and let us suppose that for this $\alpha, \beta$ the absolute error is maximized at $x_i = i$. We first point out that there must be some other $j \neq i$ such that $|y_j - \alpha x_j - \beta| = |y_i - \alpha x_i - \beta |$. Otherwise, we are free to change $\beta$ to reduce this error (and still have it be the max error). Furthermore, there must be a third index $k \neq i,j$ with the same absolute error, otherwise we could change $\alpha$ or $\beta$ to reduce both of the errors for $i,j$ simultaneously (change $\beta$ if both errors have the same sign, change $\alpha$ if the signs are different). Let $i<j<k$. If we assume that no other indices have the same absolute error, then the signs of the errors must be either $+,-,+$ or $-,+,-$. If there are other indices with the same absolute error, then there must be some subsequence of error signs of that type.

Let us assume the $+,-,+$ sequence of error signs for now. Then we have

$ y_i - \alpha * i - \beta = \beta + \alpha * j - y_j = y_k - \alpha * k - \beta $

or

$ \alpha = \frac{y_k - y_i}{k-i} $ and $\beta = \frac{y_i + y_j}{2} - \frac{\alpha (i+j)}{2} = \frac{y_k + y_j}{2} - \frac{\alpha (k+j)}{2} = \frac{(j+k)y_i + (k-i)y_j - (i+j)y_k}{2(k-i)}$

and the maximum error is $F_{\min} \equiv \frac{(k-j)y_i + (i-k)y_j + (j-i)y_k}{2(k-i)}$.

Since this is the maximum error, we also have

$ \beta + \alpha * m - F_{\min} \leq y_m \leq \beta + \alpha *m + F_{\min}$ for all $m$.

The same formulas hold for the $-,+,-$ sign choice. This represents $(j,y_j)$ lying either above or below the line between $(i,y_i)$ and $(k,y_k)$ and all other points lying in the region defined by that line and the parallel line through $(j,y_j)$.

Now, the probability distribution for $F_{\min}$ is not too difficult to solve in an asymptotic limit: $U\rightarrow \infty, n/U \rightarrow 0$ drawing with or without replacement.

In either of these cases, we replace $y_i,y_j,y_k$ by $Y_i,Y_j,Y_k = y_i/U, y_j/U, y_k/U$. $F_{\min} = U f(Y_i,Y_j,Y_k)$ occurs with weight $(2 f(Y_i,Y_j,Y_k))^{n-3} * P(Y_i $ is the $i$th smallest draw and $Y_j $ is the $j$th smallest draw and $Y_k $ is the $k$th smallest draw$)$. We then divide by the sum/integral of all of the weights. The CDF of $P()$ is something like $(Y_i)^i (1-Y_k)^{n-k} (Y_j - Y_i)^{j-i} (Y_k - Y_j)^{k-j}$. Not a pretty integral. Furthermore, this ratio is going to give you the joint probability density of $(i,j,k,Y_i,Y_j,Y_k)$, not actually the probability density of $F_{\min}$. To get that, you would need to do another integration over that set of $(i,j,k,Y_i,Y_j,Y_k)$ that gives you a fixed value of $F_{\min}$.

share|improve this answer
    
Okay. There's a mistake here. The probability that $y_m$ lies in the correct region is not independent of the probability that $y_{m'}$ lies in the correct region. Whoops! Well, this is a starting point at least. Maybe not a very good one though. –  Craig Sep 15 '11 at 1:43
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.