calculate the probability

[bona3]

if you have this code

int a[];
int max =0;

for ( int i=0; i<a.lenght;i++)
if (a[i]>max)
max=a[i]

can someone help me to find the probability of number of times if statment will be true if (a[i]>max)


thanks in advance

[rudhi]

each place can be true or false: so probability for true is 0.5
each place is an independent option
so all positions are to be multiplied
0.5 * 0.5 * 0.5 * ... a.length times ...

take care ...rudhi

[bona3]

thankyou , I thought at firest it is like waht you said

but when I ask the prof to give me ahint she said

p(x)=p(A intersection x)+P(Ac intersection x)

P(A intersection x)=P(A)*P(xgive n A)

x is the number of times if statment is true

A is event

Ac is Acomplement

[jkmyoung]

Throwing out some ideas:
Are you calculating the values for each probability, or just the expected probability? Eg if X = # of times int[i]> max, then calculate P(X) for all X?

First of all, assuming that the compiler you're using doesn't initialize the values to 0, otherwise it will always be 0. P(0) = 1

Are you allowed to assume that none of the values are equal to each other?
Also, you will have some weird condition involving INT_MAX and INT_MIN, since INT_MAX + INT_MIN is usually -1, and not 0.

32 bit:
INT_MAX = 2,147,483,647
INT_MIN = -2,147,483,648

For position 0:
strict odds are 2,147,483,647 / 4,294,967,296 which is just less than 1/2

n = 2
If a[0] > 0, then the P(a[1] > max) < 1/2. However if a[0] <=0 then P(a[1] > max) ~= 1/2
Taking the average of possibilities, you get about,
P(0) = 1/4
P(2) = 1/2 * ( (1/2)+0)/2) = 1/2 * 1/4 = 1/8
P(1) = 1 - 1/4 - 1/8 = 5/8
E(X) = 11/16

n=3
P(0) = 1/8
P(1) = 1/4 *1/2 + 5/8*3/4 = 1/8 + 15/32 = 19/32
P(3) = 1/8*1/6 = 1/48
P(2) = 1 - 1/8 - 1/48 - 19/32 = 25/96
E(X) = 1 17/96

This question would be a lot easier if you were to initialize max to INT_MIN instead of 0. I would ask your teacher about that.

[Glenton]

If the elements are all positive, then the question is what's the number of times we find the largest element of the set so far. That's 1+1/2+1/3+1/4+...