Expected Value

How can I calculate the expected number of hash collisions hits ? - n objects, m hash locations/buckets?

Lets say k-th object is  to be hashed. 

What is the probability that it gets a selected location without miss

probability of selecting m-1 location from  = (m-1)/m

And doing so for k objects = r = [(m-1)/m]^k

Expected number of miss in (n-1) trails = 1 + r + r^2 + r^3 + r^4 .... r^(n-1)

=  (1 - r^n)/(1 - r)

1 - r =  1/m

 (1 - r^n)/(1 - r) = m(1 - r^n)

So how many times, I will not miss.

Expected number of hits =  n - m(1 - r^n)

------------------------------------------------------------------------------------------------------

A dice can be rolled n times max and rolling can be stopped at any point 1....n. The score is the last value on dice. What is the expected value of dice ?

E[1 roll] =  {1, 2, 3, 4, 5, 6} with equal probability = 21/6 = 3.5

Let xi = outcome of dice in i-th roll

IF 

E[2 roll] = p(x2 > E[1]) * E[x2 | x2 > E[1]] + p(x2 <= E[1]) * E[1]

               = (0.5 * 5) + (0.5 * 3.5)

               = 2.5 +  1.75

               = 4.25

E[3 roll] = p(x3 > E[2]) * E[x3 | x3 > E[2]] + p(x3 <= E[2]) * E[2]

               = 0.3333 * 5.5  +  0.6666 * 4.25

               =  4.66

E[n roll] = p(xn > E[n-1 roll]) * E[xn | xn > E[n-1 roll]] + p(x3 <= E[n-1 roll]) * E[n-1]

------------------------------------------------------------------------------------------------------

Expected value that last flip is Head and not before. First success at k-th trial. Where success probability = p

E[k] = p*1 + (1-p)*p*2 + (1-p)*(1-p)*p*3 .......

 = Σ [(1-p)^(r-1) ]* p * r


E[k] = p + (1-p)[E[k] + 1]

p* E[k] = 1

E[k] =  1/p

------------------------------------------------------------------------------------------------------

Bobo the amoeba has a 25%, 25%, and 50% chance of producing 0, 1, or 2 offspring, respectively. Each of Bobo’s descendants also have the same probabilities. What is the probability that Bobo’s lineage dies out?

Let unknown Probability that Bobo extincts = P

Bobo - 0 = 0.25

Bobo - 1 = 0.25 * P

Bobo - 2 = 0.5*P*P

P = 0.25 + 0.25 * P + 0.5*P^2

4P = 1 + P + 2*P^2

2*P^2 - 3*P + 1 = 0

(P-1)(2P -1) = 0

------------------------------------------------------------------------------------------------------

What’s the expected number of coin flips until you get two heads in a row? 

HH --> 0.25
HT --> 0.25 ; Expected number from here is same as in start
TT --> 0.25 ; Expected number from here is same as in start
TH --> 0.25 ;

E = 0.25*2 + 0.25*(E + 2) + 0.25(E +2) + 0.25*0.5*(1+2) + 0.25*0.5*(E+1+2)

= 0.5 + (0.5 + 0.25*E) + (0.25*E + 0.5) + ( 0.375)  + (0.375 + 0.125*E)

E = 0.625*E + 2.25

E = 2.25/0.375 = 6

------------------------------------------------------------------------------------------------------

Given

P(Truth|A) = P(Truth|B) = P(Truth|C) = 2/3

Find P(Rain = 1 | A,B,C= Rain) 

P (A,B,C = Rain | Rain = 1)  = 8/27

P (A,B,C = Rain | Rain = 0)  = 1/27
P(Rain = 1)  = 
p(A, B, C = Rain) = 8/27 + 1/27 = 9/27


P(Rain = 0 | A,B,C= Rain)  =
P(Rain = 0)  = 1 - P(Rain = 1)

{

p(Rain = 1, A, B, C= Rain)  = p(Rain = 1 | A, B, C= Rain) * p(A, B, C = Rain)

p(Rain = 1, A, B, C= Rain)  = p(A,B,C=Rain | Rain=1) * p(Rain=1)

}

p(A,B,C=Rain | Rain=1) * p(Rain=1) = p(Rain = 1 | A, B, C= Rain) * p(A, B, C = Rain)

p(Rain = 1 | A, B, C= Rain)  = p(A,B,C=Rain | Rain=1) * p(Rain=1) / p(A, B, C = Rain)

=  p(Rain=1)*(8/9)