# Probability that there is sub-sequence of exact length

Can you help me to solve the following:

Find probability that in sequence of N random uniformly distributed numbers there is increasing sub-sequence of exact length L.

• Is this a homework problem? What have you tried? Dec 18 '14 at 19:22
• What do you mean by "random uniformly distributed numbers"? Also, are the random variables independent? Dec 18 '14 at 19:51
• Random numbers that are drawn from uniform distribution. I don't know if they are independent, it's not said. :/
– gov
Dec 18 '14 at 19:55
• I'm sick of these "bounties"... Dec 23 '14 at 18:01
• There is a lot of literature on this subject. The asymptotic distribution is known. I don't believe exact formulas for the case of finite $N$ are available. Dec 24 '14 at 21:29

Since it's an infinitely large range of numbers, when you have one number X1, and the chance of X2 > X1 would be 50%. Similarly, X3 > X2 would also be roughly 50% (infinitely close to 50%). Thus for length L, the chances are very close to 0.5 ^ (L-1).

===---=== Details on why X2 > X1 and X3 > X2 is 50%

Imagine if the range is only (1 - 10).

When X1 = 1, X2 > X1 = 9/10. Similarly, when X1 = 9, X2 > X1 = 1/10. Average those two extremes and you get 5/10. Do the same with X1 = 2 and X1 = 8... Basically all the extreme pairs average out to exactly 50%. The only problem is when X1 = 10 (the maximum range).

So with an infinitely large set of numbers, this is becomes an infinitely small deviation from the perfect 50% probability.

Similarly, with all the X2/X1 combos that fit the original pattern, you will have X2 = 2,3,4,5,6,7,8,9,10. The chance of X3 > X2 is roughly 50% as well using the previous logic.

So when the number range is infinitely large, the probability of getting an increasing sequence of L numbers would be P = 0.5 ^ (L-1). Please keep in mind that this is just an estimate, a very close one at infinite range (or very large range). The bigger the number range and the smaller the L, the closer the estimate.

Now considering how long the original sequence is (let's call that S), you will need to multiply the P of getting one sub-sequence L by the number of existing sub-sequence in S. that's S+1-L.

So the final equation is:

(0.5)^(L-1) * (S+1-L)

===

For people not clear on why the chance of getting a number to be larger than a previous one is about 50% as the range of numbers becomes infinite...

For any number X0 in range R, there's n numbers where n < X and (R-n) > X. Since the probability of getting any number is the same, X0 can above or below the middle point of the range, m.

If n < m and d = m - n then ratio of getting P(X1 > X0) is (R - m + d) / R

Similarly, if n > m, and d = n - m then the ratio of getting P(X1 > X0) is (m - d) / R

If you notice, those two add up to one (R/R), and since m is the MIDDLE point, there are equal numbers of d. Thus all pairs of number equal distance away from the middle point will add up to one (and average to 0.5).

===---===

Above is a very very wordy answer to a very simply intuitive mathematical solution. Math isn't supposed to be equations but intuitive understanding and logic.

If you take the smallest point as X0, that gives you the entire range as possibility to be X1 > X0, (R/R); however, if you take the largest point as X0, then none of the range will be X1 > X0, (0/R).

If you take X0 as the smallest number + 1, then that gives you (R-1)/R probabilities of X1 > X0, similarly, if you take X0 as the largest number - 1, then that gives you 1/R as the probability.

• Can you explain why the probability that one number is larger than another one is 50% if they are drawn from uniform distribution?
– gov
Dec 25 '14 at 18:49
• That's pretty intuitive... And I already described it in my answer... I will clarify. Dec 26 '14 at 14:47
• I don't understand this sentence: "For any number X_0 in range R, there's n numbers where n < X and (R-n) > X." What do you mean with "range"? As I know, range is difference between largest and smallest value. So, for example, if smallest value is 0 and largest is 1, range is R=1-0=1. Now, following your words, having n>1, that sentence sounds pretty impossible. I understand that you know math and I think I am smart enough to understand the solution, but I'd like you to be more friendly and more at the Earth. And I still don't understand your answer.
– gov
Dec 26 '14 at 21:19
• I mean, for example, if you take finite range (1-10), for any number X0 in that range (1 - 10), there are n numbers where n is smaller than X0 and R-n) is larger than X0. If X0 is 5, there are 4 numbers that are smaller than X0, and (R-4) numbers that are bigger than X0. So if X0 = 5, the chance of X1 > X0 is (R-n)/R = (9-4)/9. Similarly, if X0 = 6, the chance of X1 > X0 is (R-n)/R = (9-5)/9. Those two adds up to 9/9 = 1, so the average is 0.5 (50%). Then you have P(4) + P(7), P(3) + P(8), P(2) + P(9), P(1) + P(10), all of these pairs add up to 1 and thus average to 50%. Dec 28 '14 at 18:20
• I understand what you're saying, but why are you adding probabilities to each other? Isn't it, for example, for increasing sub-sequence, "X1<X2<X3<X4<..." so it is "X1 is smaller than X2 AND X2 is smaller than X3 AND X3 is smaller than X4 AND..." so it is AND, not OR, and shouldn't we multiply probabilities, not add them? Why don't you use probability for uniform distribution?
– gov
Dec 29 '14 at 18:45

I've tried something like this:

${x_1,x_2,...,x_N}$ is sequence of length N and $x_i$ are uniformly distributed random numbers from interval (a,b) . Let's say that increasing sub-sequence of length L appears at the beginning, i.e. it's a sub-sequence ${x_1,x_2,...,x_L}$.

Probability that we will draw a number $x_1$ is 1. Actually, I was thinking about this element. As we have to take the first number and its value is not important, I think that the probability of drawing it is 1. Since the sub-sequence is increasing, it means that $x_2>x_1$ and probability of this is $P\{X>x_1\}=1-P\{X<x_1\}=1-\int_a^{x_1} \frac{1}{b-a}dx=1-\frac{x_1-a}{b-a}$

Next element, $x_3$ is greater than $x_2$ and probability for that is $P\{X>x_2\}=1-\frac{x_2-a}{b-a}$ and so on to $x_L$.

Element after $x_L$ is smaller than $x_L$, i.e. $x_{L+1}<x_L$ and the probability of that is $P\{X<x_L\}=\frac{x_{L+1}-a}{b-a}$. Elements after this one may be in any order, increasing or decreasing, and depending on that I just have to find probabilities for each element and to make a product of all these probabilities. But I don't know how to do that since I don't know their order.

At least, am I on the right way?