random alternation

[radosr]

The answer does involve trig functions (this I am sure about).
The asnwer I got is (1 + sin 1)/cos 1, which is around 3.41 (between 3 and 4 ). I could be wrong.
I am not going to give away my reasoning just yet.
The "random alternation" question was asked in an interview for a QR position recently.
It is a "variant" on the following (more classical) question that has been asked more than once.
Question: "You pick random numbers between 0 and 1 (uniformly at random) x_1, x_2, x_3, ..., as long as they keep decreasing x_1 > x_2 > x_3 > ... What is the expected number of numbers you pick?"
Solution: Let E(x) be the expected number of numbers you have yet to select, given that you have just selected the number x. Then
E(x) = (1-x) + integral from 0 to x of (E(y) + 1)dy ;
so E(x) = 1 + integral from 0 to x of E(y)dy.
Differentiate --> E'(x)=E(x), so E(x) = e^x (using the initial condition E(0) = 1).
Now, the expected number of numbers selected (in this decreasing fashion) is E(1) = e (since your first pick is less than 1).
Let's just say that similar ideas can be carried over to the random alternation variant, but it does get "hairy".
Best regards!

 

[Tsotne]

The answer does involve trig functions (this I am sure about).
The asnwer I got is (1 + sin 1)/cos 1, which is around 3.41 (between 3 and 4 ). I could be wrong.
I am not going to give away my reasoning just yet.
The "random alternation" question was asked in an interview for a QR position recently.
It is a "variant" on the following (more classical) question that has been asked more than once.
Question: "You pick random numbers between 0 and 1 (uniformly at random) x_1, x_2, x_3, ..., as long as they keep decreasing x_1 > x_2 > x_3 > ... What is the expected number of numbers you pick?"
Solution: Let E(x) be the expected number of numbers you have yet to select, given that you have just selected the number x. Then
E(x) = (1-x) + integral from 0 to x of (E(y) + 1)dy ;
so E(x) = 1 + integral from 0 to x of E(y)dy.
Differentiate --> E'(x)=E(x), so E(x) = e^x (using the initial condition E(0) = 1).
Now, the expected number of numbers selected (in this decreasing fashion) is E(1) = e (since your first pick is less than 1).
Let's just say that similar ideas can be carried over to the random alternation variant, but it does get "hairy".
Best regards!

Is your 3.41th number a violating number or the last fitting number? If this is the violating number then our simulation is correct. We got the same result.

 

[cgorac]

@cgorac: I wouldn't use random() for simulation.

I wouldn't, either - according to man page, the period of random() is approximately 16 * ((2^31) - 1). But it's readily available in C standard library, so it makes code short and does its job well here.

On the other side, Mersenne Twister is not be-all end-all for simulations - oftentimes people pick it just because everyone else is using it, while there are other generators, faster than Mersenne Twister and with adequate period for specific types of simulation.

 

[AlexandreH]

I wouldn't, either - according to man page, the period of random() is approximately 16 * ((2^31) - 1). But it's readily available in C standard library, so it makes code short and does its job well here.

On the other side, Mersenne Twister is not be-all end-all for simulations - oftentimes people pick it just because everyone else is using it, while there are other generators, faster than Mersenne Twister and with adequate period for specific types of simulation.

I agree.

 

[pruse]

The answer does involve trig functions (this I am sure about).
The asnwer I got is (1 + sin 1)/cos 1, which is around 3.41 (between 3 and 4 ). I could be wrong.
I am not going to give away my reasoning just yet.
The "random alternation" question was asked in an interview for a QR position recently.
It is a "variant" on the following (more classical) question that has been asked more than once.
Question: "You pick random numbers between 0 and 1 (uniformly at random) x_1, x_2, x_3, ..., as long as they keep decreasing x_1 > x_2 > x_3 > ... What is the expected number of numbers you pick?"
Solution: Let E(x) be the expected number of numbers you have yet to select, given that you have just selected the number x. Then
E(x) = (1-x) + integral from 0 to x of (E(y) + 1)dy ;
so E(x) = 1 + integral from 0 to x of E(y)dy.
Differentiate --> E'(x)=E(x), so E(x) = e^x (using the initial condition E(0) = 1).
Now, the expected number of numbers selected (in this decreasing fashion) is E(1) = e (since your first pick is less than 1).
Let's just say that similar ideas can be carried over to the random alternation variant, but it does get "hairy".
Best regards!

Hi Rados,

First off, nice problem! And damn difficult

I am not entirely sure how to do it yet, but I do know the answer involves trig functions because the first few probabilities (of getting a sequence of n alternating values) that I get -- 1, 1, 2/3, 5/12, 4/15, 61/360 -- are twice the coefficients of the Taylor expansion of sec x + tan x.

But adding these first 6 probabilities I am getting 3.519, which would mean the expectation is larger than this. Maybe you can tell me where my error is.

Based on that Taylor expansion and my interpretation of the problem, I am getting that it should be (2(\sec 1 + \tan 1 - 2)+1 = 2(\sec 1 + \tan 1) - 3 \approx 3.816)

 

[radosr]

Let's say we continue picking as long as x_1 > x_2 < x_3 > x_4 < ...
Let R(x) be the expected number of numbers we have yet to pick for x = x_1, x_3, ...
and let S(x) be the expected number of numbers we have yet to pick for x = x_2, x_4, ...
Using the same reasoning as in my post above, we get:
R(x) = (1-x) + (integral from 0 to x of (S(y) + 1) dy) and
S(x) = x + (integral from x to 1 of ((R(y) +1) dy).
Differentiating, we get R'(x) = S(x) and S'(x) = -R(x). Now, substitution and initial conditions R(0) = 1, S(1) = 1,
give that, for example, S(x) = A*cos(x) - B*sin(x), where A = (1 + sin(1))/cos(1) and B = 1.
Now, we want S(0), which is (1+ sin(1))/cos(1).

This said (aside from the computational mistakes I may have made), Peter's post confused me. I may be wrong,
since I do remember (from my algebraic combinatorics days and books by Stanley) that the generating function for alternating permutations is indeed sec x + tan x. (see e.g. http://mathworld.wolfram.com/AlternatingPermutation.html) Now what?

 

[pruse]

Let's say we continue picking as long as x_1 > x_2 < x_3 > x_4 < ...
Let R(x) be the expected number of numbers we have yet to pick for x = x_1, x_3, ...
and let S(x) be the expected number of numbers we have yet to pick for x = x_2, x_4, ...
Using the same reasoning as in my post above, we get:
R(x) = (1-x) + (integral from 0 to x of (S(y) + 1) dy) and
S(x) = x + (integral from x to 1 of ((R(y) +1) dy).
Differentiating, we get R'(x) = S(x) and S'(x) = -R(x). Now, substitution and initial conditions R(0) = 1, S(1) = 1,
give that, for example, S(x) = A*cos(x) - B*sin(x), where A = (1 + sin(1))/cos(1) and B = 1.
Now, we want S(0), which is (1+ sin(1))/cos(1).

This said (aside from the computational mistakes I may have made), Peter's post confused me. I may be wrong,
since I do remember (from my algebraic combinatorics days and books by Stanley) that the generating function for alternating permutations is indeed sec x + tan x. (see e.g. http://mathworld.wolfram.com/AlternatingPermutation.html) Now what?

well your answer can be written as sec(1) + tan(1)... are you maybe only considering alternating sequences that start on an "up"? from your original problem statement, starting on a "down" should be allowed too.

 

[radosr]

How silly of me! Great point! (1 + sin(1))/cos(1) is indeed sec(1) + tan(1) and it is the answer if one only considers alternating sequences starting with an "up". Peter's answer from several posts above is then the correct answer for the original problem.

By the way, I noticed something interesting:
If one keeps picking random numbers from 0 to 1, uniformly at random, as long as they are decreasing in size, the expected number of numbers picked is e. Curiously, number of permutations of 1 to n, decreasing in size, is clearly just 1. The exponential generating function for these permutations is sum of 1*x^n/n! over all n, which is e^x. The answer to the random selection procedure question is then obtained by plugging x=1 into e^x.

If one keeps picking random numbers from 0 to 1, uniformly at random, as long as they are alternating in size, starting with an "up", the expected number of numbers picked is sec(1) + tan(1). Curiously, number of permutations of 1 to n, alternating in size, starting with an up, has an exponential generating function sec(x) + tan(x) (see the link i provided above, for example). The answer to the random selection procedure question is then obtained by plugging x = 1 into sec x + tan x. (!!!)

So, to make my point clear: Suppose the number of permutations, that follow or avoid a certain pattern (e.g. see http://en.wikipedia.org/wiki/Permutation_pattern) has a known exponential generating function f(x). There is a whole discipline in enumerative combinatorics dealing with counting pattern-avoiding permutations. Now, let's consider our random selection procedure, where we stop as soon as a forbidden pattern is reached. Is it true that the expected number of numbers selected is f(1)?!

 

[pruse]

How silly of me! Great point! (1 + sin(1))/cos(1) is indeed sec(1) + tan(1) and it is the answer if one only considers alternating sequences starting with an "up". Peter's answer from several posts above is then the correct answer for the original problem.

By the way, I noticed something interesting:
If one keeps picking random numbers from 0 to 1, uniformly at random, as long as they are decreasing in size, the expected number of numbers picked is e. Curiously, number of permutations of 1 to n, decreasing in size, is clearly just 1. The exponential generating function for these permutations is sum of 1*x^n/n! over all n, which is e^x. The answer to the random selection procedure question is then obtained by plugging x=1 into e^x.

If one keeps picking random numbers from 0 to 1, uniformly at random, as long as they are alternating in size, starting with an "up", the expected number of numbers picked is sec(1) + tan(1). Curiously, number of permutations of 1 to n, alternating in size, starting with an up, has an exponential generating function sec(x) + tan(x) (see the link i provided above, for example). The answer to the random selection procedure question is then obtained by plugging x = 1 into sec x + tan x. (!!!)

So, to make my point clear: Suppose the number of permutations, that follow or avoid a certain pattern (e.g. see http://en.wikipedia.org/wiki/Permutation_pattern) has a known exponential generating function f(x). There is a whole discipline in enumerative combinatorics dealing with counting pattern-avoiding permutations. Now, let's consider our random selection procedure, where we stop as soon as a forbidden pattern is reached. Is it true that the expected number of numbers selected is f(1)?!

This makes sense, since the expectation is a sum over all N of the probability of the condition being satisfied up to step N... plugging 1 into the probability generating function finds the sum of those probabilities...

Here's another classic interview question whose answer is also (e): What is the expected number of (U[0,1]) numbers you will pick as long as their sum is (\leq 1)?

And now I see the connection between this problem and your problem: picking (U[0,1]) numbers so that their sum is less than 1 is equivalent to picking increasing (U[0,1]) (these increasing numbers representing your running sum), which of course is equivalent to picking decreasing (U[0,1]) numbers.

 

[cgorac]

Corrected simulation code from above:

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

#define N 100000000

int
main(void)
{
    double          sum = 0;
    for (int i = 0; i < N; ++i) {
        double          curr = (double) random() / RAND_MAX;
        double          next;
        while ((next = (double) random() / RAND_MAX) == curr)
            ;
        int             j = 2;
        bool            flag = curr < next;
        while (1) {
            curr = next;
            while ((next = (double) random() / RAND_MAX) == curr)
                ;
            if (flag) {
                if (curr <= next)
                    break;
            } else {
                if (curr >= next)
                    break;
            }
            ++j;
            flag = !flag;
        }
        sum += j;
    }
    printf("%g\n", sum / N);

    return 0;
}

Two corrections are made:

• violating number is calculated in, as obviously that would be correct interpretation of OP's problem (with this correction, previous version of the code is producing correct result for alternating sequences starting with "up" only)
• alternating sequence starting with "down" are counted too (don't know how I missed that from the problem statement, but in any case the code above will print 3.81636, which seems to be correct result)

 

[AlexandreH]

Corrected simulation code from above:

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

#define N 100000000

int
main(void)
{
    double          sum = 0;
    for (int i = 0; i < N; ++i) {
        double          curr = (double) random() / RAND_MAX;
        double          next;
        while ((next = (double) random() / RAND_MAX) == curr)
            ;
        int             j = 2;
        bool            flag = curr < next;
        while (1) {
            curr = next;
            while ((next = (double) random() / RAND_MAX) == curr)
                ;
            if (flag) {
                if (curr <= next)
                    break;
            } else {
                if (curr >= next)
                    break;
            }
            ++j;
            flag = !flag;
        }
        sum += j;
    }
    printf("%g\n", sum / N);

    return 0;
}

Two corrections are made:

• violating number is calculated in, as obviously that would be correct interpretation of OP's problem (with this correction, previous version of the code is producing correct result for alternating sequences starting with "up" only)
• alternating sequence starting with "down" are counted too (don't know how I missed that from the problem statement, but in any case the code above will print 3.81636, which seems to be correct result)

Nice catch . I wonder why I keep getting 3.436. Maybe the RNG I am using is not giving me a good approximation of a uniform distribution. I will have to run some tests to see.

 

[yongge]

The solution is quite amazing. I like it very much. The differential equations are such a beautiful tool. I tried a similar approach to
peterruse, but I can only get numerical solution by using iterations and got stuck with the series, not able to connect the series with the function sec(x)+tan(x).

I just wanted to point out a small mistake other than only the "up" sequence is considered.

For the "up" sequence x_1 > x_2 < x_3 > x_4 <...

Just want to clarify, if the sequence is x_1 > x_2 < x_3 > x_4>x_5, the number of draws is 5 rather than 4.
this definition is crucial in building the two equations of adosr.

These two equations are only true for the second random number (x_2) or thereafter.
R(x) = (1-x) + (integral from 0 to x of (S(y) + 1) dy)
S(x) = x + (integral from x to 1 of ((R(y) +1) dy).

The sequence continues always for x_2 regardless what value of x_1. So the initial value of S(1)=1 is incorrect for
x_1.

Therefore, the computation of the expectation number of length for the "up" sequence should be
L_up= 1+ integral from 0 to 1 of R(y)+1 dy = S(0)+1 = sec(1)+tan(1)+1

If we combine both together, we have
(L_up-3)*2+2 = 2*(sec(1)+tan(1)) - 2 =4.816.

I believe peter didn't include the last draw which violates the rule when computing the expectation of N.
The expectation should be N+1, which will agree with the answer above.

peterruse said
"well the probability of the first N draws alternating is 1 for N=1,2, and then 2/3, 5/12, 4/15, 61/360 (computed via multiple integrals) for N=3, 4, 5, 6, so the expectation is at least 1+1+2/3+5/12+4/15+61/360=3.5194..."

Let's say we continue picking as long as x_1 > x_2 < x_3 > x_4 < ...
Let R(x) be the expected number of numbers we have yet to pick for x = x_1, x_3, ...
and let S(x) be the expected number of numbers we have yet to pick for x = x_2, x_4, ...
Using the same reasoning as in my post above, we get:
R(x) = (1-x) + (integral from 0 to x of (S(y) + 1) dy) and
S(x) = x + (integral from x to 1 of ((R(y) +1) dy).
Differentiating, we get R'(x) = S(x) and S'(x) = -R(x). Now, substitution and initial conditions R(0) = 1, S(1) = 1,
give that, for example, S(x) = A*cos(x) - B*sin(x), where A = (1 + sin(1))/cos(1) and B = 1.
Now, we want S(0), which is (1+ sin(1))/cos(1).

This said (aside from the computational mistakes I may have made), Peter's post confused me. I may be wrong,
since I do remember (from my algebraic combinatorics days and books by Stanley) that the generating function for alternating permutations is indeed sec x + tan x. (see e.g. http://mathworld.wolfram.com/AlternatingPermutation.html) Now what?

 

[pruse]

yongge: read the original problem statement..."as long as they keep alternating in size" -- which implies that we shouldn't count the one that breaks the pattern.

if it had said "until the pattern is broken," I'd have agreed with you

 

[yongge]

I guess we can define whatever N we want do decide as long as it's clear, we just need to add or subtract 1. That is minor issue. That's why I clarify the definition of N in my post.

However, to establish radosr's two equations, we need to count the last draw that breaks the pattern. I do not know there is another way around.

yongge: read the original problem statement..."as long as they keep alternating in size" -- which implies that we shouldn't count the one that breaks the pattern.

if it had said "until the pattern is broken," I'd have agreed with you