random alternation

[radosr]

Pick random numbers x_1, x_2, x_3, ... between 0 and 1 (uniformly at random), as long as they keep alternating in size (x_1 < x_2 > x_3 < x_4 > ... or x_1 > x_2 < x_3 > x_4 < ...). What is the expected number of numbers you pick?

 

[AlexandreH]

is it 4?

 

[Tsotne]

What is the expected number of numbers you pick?

Is this question asking for the expected number of success? success = x_1 < x_2 > x_3 < x_4 > ... is forced. I am simulating it but not sure what I'm exactly searching for.

 

[AlexandreH]

Is this question asking for the expected number of success? success = x_1 < x_2 > x_3 < x_4 > ... is forced. I am simulating it but not sure what I'm exactly searching for.

No, It's looking for the expected numbers of picks until the game ends. It will end when the "alternating" rule is broken.
At least that's what I understood.
@Tsotne, what are you using for simulations?

 

[Tsotne]

@Tsotne, what are you using for simulations?

Aha thanks Alexandre now I got it. I created a vector holding the random numbers. Intuition tells that array of max-20 is enough and even more since the probability that 20 sequence will not violate the sequence rule is 0. Then simulate the vector by changing the values of random elements and see how many times the sequence has been broken. To get a good precision i will simulate it for big n (say 50000 if it shows this minimizes the error) times and get the average value of breakdowns such that the difference between the previous iteration and the current one is minimal, say 10e-14. Ill finish it and post here in a few minutes.

 

[AlexandreH]

Aha thanks Alexandre now I got it. I created a vector holding the random numbers. Intuition tells that array of max-20 is enough and even more since the probability that 20 sequence will not violate the sequence rule is 0. Then simulate the vector by changing the values of random elements and see how many times the sequence has been broken. To get a good precision i will simulate it for big n (say 50000 if it shows this minimizes the error) times and get the average value of breakdowns such that the difference between the previous iteration and the current one is minimal, say 10e-14. Ill finish it and post here in a few minutes.

I actually think it is much simpler than this. I will try it on C++ and post the code. I got "4" using probability theory and not a simulation but I m not sure about my logic.

 

[pruse]

Why is it that people always attack these problems with simulations? Anyone can write a quick program that will give a fairly accurate answer -- that's easy. But it defeats the whole purpose of the question. When you're asked something like this on an interview, you're being tested on your knowledge of how probabilities and expectations work, and maybe your creative skills. That being said, the answer is more complicated than just '4'. What if I told you it involved trig functions?

 

[Tsotne]

I actually think it is much simpler than this. I will try it on C++ and post the code. I got "4" using probability theory and not a simulation but I m not sure about my logic.

I did it and gives me the answer = 2.33. I did it in C#. Here's the initial code. I'll streamline it as well as possible later because it makes many calls which can be avoided. I extracted the methods just for the sake of clear illustration.
How did you do it?

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace RandomSequence
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] countsVector = new int[10000000];

            for (int i = 0; i < countsVector.Length; i++)
            {
                countsVector[i] = BreakOrder(RandomizeVector());

            }

            int sum = 0;
            for (int i = 0; i < countsVector.Length; i++)
            {
                sum += countsVector[i];
            }

            double average = (double)sum / countsVector.Length;

            Console.WriteLine(average);

            Console.ReadLine();
        }

        static double[] RandomizeVector()
        {
            Random r = new Random();
            double[] outputVector = new double[20];

            for (int i = 0; i < outputVector.Length; i++)
            {
                outputVector[i] = r.NextDouble();
            }
            return outputVector;
        }

        static int BreakOrder(double[] vector)
        {
            int count = 1;

            for (int i = 0; i < vector.Length - 2; i+=2)
            {
                if (vector[i] < vector[i + 1])
                {
                    count++;
                    if (vector[i + 1] < vector[i + 2])
                        count++;
                }
                else
                    break;
            }
            return count;
        }
    }
}

 

[Tsotne]

Why is it that people always attack these problems with simulations? Anyone can write a quick program that will give a fairly accurate answer -- that's easy. But it defeats the whole purpose of the question. When you're asked something like this on an interview, you're being tested on your knowledge of how probabilities and expectations work, and maybe your creative skills. That being said, the answer is more complicated than just '4'. What if I told you it involved trig functions?

You are right but we just got interested in programming algorithm of doing so. I think it is really interesting. I especially wonder how people come up with checking logic there. As a whole, you are right, I'm doing it analytically now. At least we should have a correct answer to compare, so simulation is not a first weapon to "attack". Just a good start

 

[bob]

Why is it that people always attack these problems with simulations? Anyone can write a quick program that will give a fairly accurate answer -- that's easy. But it defeats the whole purpose of the question. When you're asked something like this on an interview, you're being tested on your knowledge of how probabilities and expectations work, and maybe your creative skills. That being said, the answer is more complicated than just '4'. What if I told you it involved trig functions?

For something like this where a simulation is quick to code and run, it's useful to have a result in hand so you can know whether the analytic result you work out is right. So it's not a bad first step, really.

But, you're absolutely right, the numerical answer is not really the point in a case like this, where the occasion of the question lets you know there is some nice formulation available. On the other hand, with an arbitrary problem it is often the case that no nice formulation exists to be found, and if the numerical answer is needed for some purpose, then it's far better to produce one and put it to use without being too concerned about what the "real" answer is.

 

[Tsotne]

uumm Seems I missed the real value. I forgot to increase the count variable by 1 since the breaking number should be taken into account. Current code ignores it. So simply I should have added 1 before return count; So the answer it gives me is 3.33 or --- on average the expectation of the number causing a sequence rule to break down is 3 approx.

 

[cgorac]

I did it in C#. Here's the initial code.

Rather inefficient (why allocate array?)... Here is C code:

#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;
        int             j = 1;
        while (1) {
            double          next = (double) random() / RAND_MAX;
            if (j & 0x1) {
                if (curr <= next)
                    break;
            } else {
                if (curr >= next)
                    break;
            }
            curr = next;
            ++j;
        }
        sum += j;
    }
    printf("%g\n", sum / N);

    return 0;
}

It prints out 2.40839, in less than 7secs (please post timing of your C# code). Compiled with "gcc --std=c99 -O3", and run on Intel P8600 CPU at 2.40GHz.

 

[Tsotne]

Rather inefficient (why allocate array?)... Here is C code:

It prints out 2.40839, in less than 7secs (please post timing of your C# code). Compiled with "gcc --std=c99 -O3", and run on Intel P8600 CPU at 2.40GHz.

I had exactly the same version in mind but rather decided to allocate arrays which certainly increases the compilation time. Also I have defined 2 helper functions which themselves do the same. I'm doing it again in one function and make it much faster. One question... Are you accounting for the violating number??? I got the same result at first but I had ignored the violating number. The question asks for the number of times you make an experiment. That is, how many times you should choose every following number till you break the sequence. So if the violating number is 3, we are getting 2 while the correct answer is 2. Both are correct, depends on the condition actually.

 

[cgorac]

I had exactly the same version in mind but rather decided to allocate arrays which certainly increases the compilation time.

If array allocated, there is a limit (depending on the size of memory on your machine) on the number of simulations runs, while without arrays practically (the data type used in my code to hold counters and such should be changed for some very large runs) the number of runs is unlimited. Also, the code is slower with arrays, as it has to deal with reading/writing memory, while without array all of variables used should fit into registers.

One question... Are you accounting for the violating number???

No (and I saw your message above, before sending mine, about this) but I'd say the problem statement is slightly ambiguous in that regard. In any case, if violating number should be accounted for, then the final result obviously should be just incremented by 1.

 

[pruse]

I'll be the first to admit, many of these questions have no direct bearing on finance, and people wonder why they're asked. They're asked because at core many of them mimic the fundamental principles driving financial engineering.

Tsotne and others: If I'm not mistaken, the true answer is around 3.8...

 

[Tsotne]

I'll be the first to admit, many of these questions have no direct bearing on finance, and people wonder why they're asked. They're asked because at core many of them mimic the fundamental principles driving financial engineering.

Tsotne and others: If I'm not mistaken, the true answer is around 3.8...

How did you obtain it? That's approx 4 which seems very high. Logically I don't expect such sequence not to ruin till the 4th outcome.

No (and I saw your message above, before sending mine, about this) but I'd say the problem statement is slightly ambiguous in that regard. In any case, if violating number should be accounted for, then the final result obviously should be just incremented by 1.

Exactly. Let's agree - we are not accounting for the violating number and are just interesting to get the number till which (inclusive) correct sequence occurs.
e.g.
0.3478
0.5978
0.2789
0.0145
Here the correct answer is 3.

 

[AlexandreH]

Why is it that people always attack these problems with simulations? Anyone can write a quick program that will give a fairly accurate answer -- that's easy. But it defeats the whole purpose of the question. When you're asked something like this on an interview, you're being tested on your knowledge of how probabilities and expectations work, and maybe your creative skills. That being said, the answer is more complicated than just '4'. What if I told you it involved trig functions?

Peter, I tried to solve it using prob and expectation work. The answer "4" was the result. Obviously, because I doubted my analysis, I did not post the solution. I know the answer is more complicated.

 

[pruse]

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...

 

[AlexandreH]

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...

Using simulation, I get 3.436. So, I don't know.

 

[AlexandreH]

@cgorac: I wouldn't use random() for simulation. Is the period also 2^32 - 1 (like rand() )? If so, it is not good for simulations. I used the Mersenne Twister RNG.