What is the expected number of numbers you pick?
No, It's looking for the expected numbers of picks until the game ends. It will end when the "alternating" rule is broken.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.
@Tsotne, what are you using for simulations?
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.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.
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;
}
}
}
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?
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?
I did it in C#. Here's the initial 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;
}
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.
One question... Are you accounting for the violating number???
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...
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.
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.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?
Using simulation, I get 3.436. So, I don't know.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...