Probability shortlist

[•Cosmin]

http://www.infoarena.ro/blog/probability-shortlist

[•dutzul]

what do you mean by "fair" 0 and 1 result??

[•Cosmin]

0 or 1 each appear with 1/2 probability

[•dutzul]

Im not used to this type of problems so if my solution look bad im sorry lol ))

2. If we substract 1 from the function result we can get a random number betwen 0 and 4 , if we use the function 6 times ,and we get a and we look at the results as a  6 digits number in Base 5 we get a random number betwen  0 and (5^6-1) .  The number (5^6-1) is divisible by 7 so if we take the remainder of the result dividing by number 7 we get a random number betwen 0 and 6 . If we add 1 here is our answer.

3. Generate a random real number between 0 and 2pi , then generate the a random number betwen 0 and R.(the angle and the distance from the point x,y) from here you can find the point using some math formulas wich i dont know .

4.
Lets substract 1 from every element of the permutation for simplicy we will add 1 at the final result to get our answer.

Generate a random number betwen 0 and (n!-1).  Lets call it X.

There are exactly n! permutations and exactly n! X's so for each number X we can map only one permutation.

One way of finding the first element of the permutation is
  A.1= X/(n-1) ! (integer part of it )

once we found the first elemenent we then substract A.1*(n-1)! from X and we repeat the above step till we find all digits.

[•dutzul]

1) If we toss the coin 1/p times we will get a head. If we toss the coin (1/p)/2 we get 50% chance of getting a head so if we toss it 1/(p*2) times and we dont get a head we consider it a 0 otherwise 1.

Also i dont understand 5) what do you mean by stream of integers ? it means that you dont know how many integers you got and you keep reading them?
like a while (f>>X) ?

and also i dont get what problem 6 ) wants . the expected time?

and at problem 7 . I need to come up with a formula or an algorithm ?

My english is no very good so im sorry if this questions look stupid

[•auRSTAR]

6) Let's consider p(i) be the probability to draw a new card if I have already i cards.
p(i) = 1 - i / n = ( n - i ) / n, for 0 <= i < n
Let's Ti be a random variable, where Ti(j) represents the probability to pick a new card from j draws if I already have i cards.
Ti(j) = p(i) * ( (1 - p(i)) ^ (j - 1) ) ( geometric distribution )
From the fact that Ti is geometric distributed , the mean ( E(Ti) ) is 1/p.
The expected times you need to draw before having each card at least once is sum( E(Ti) ), for 0<=i<n
sum( E(Ti) ) = n + n/2 + n/3 + .. + 1 = n * (1 + 1/2 + .. + 1/n ) = n * Hn, where Hn is the n-th harmonic number.

[•gogu]

Some of these are pretty classic (I think 4 should be toughened a bit to require an O(N) algorithm), so I'll skip some I know and some I actually have to think about more to be sure.

2) Create a function rand25() from two rand5() calls: rand25() = rand5()*5 + rand5().
While rand25() returns a number greater than the biggest multiple of 7 in your range (21), ignore it.
In the end, return this number mod 7.
This works because you now generate a uniform distribution of length longer than 7, and you just ignore the extremities to get a multiple of 7 number of options.

3) I think Bondariuc Dan's solution is almost right: you need to generate the distance from the center proportional to the "amount" of points at that distance. I know you have infinite points at a certain distance, but the probability of picking a point at distance d should be equal to the circumference of the circle with radius d (there's a "bigger" infinity at distance d, to put it intuitively).
So, the solution would be:
- generate u uniformly in [0, 2*pi)
- generate rs uniformly in [0, r*r], and take d = sqrt(rs)
The point you want should be at (x + d*sin(u), y + d * cos(u))

[•auRSTAR]

8 ) s(n, m) = number of permutations of length n that execute the 4th line exactly m times.
To compute s(n, m) we can consider the s(n-1, m-1) case and put the new element on the first position or the s(n-1,m) case and add the new element on other position.
So s(n, m) = s(n-1, m-1) + (n-1)*s(n-1, m) ( Unsigned Stirling numbers of the first kind)
The expected value is sum ( m * s(n,m) ) / n!, for 1<= m<= n.

I get stuck here, so I tried another approach:

Let's consider Y(i) = max(X(j)), 1<= j<= i, X is the permutation and Z is a random variable where Z(i) = 1 / (number of occurences of Y(i) in Y). sum( Z ) = number of times line 4 is executed for X.
The expected value, E(Z) = sum ( E(Z(i)) ). E(Z(i)) = sum(1/k * P(Z(i) == 1/k) ), for 1<= k<= n. So E( Z(i) ) = 1/n * (1/1 + 1/2 + 1/3 + .. + 1/n) ) = 1/n * Hn.
E( Z ) = n * (1/n * Hn) = Hn.

[•Cosmin]

Cool, plenty of comments. I'll go through them one by one.

@ Dan-Alexandru
2. 5^6 % 7 = 1 so one of the 7 results is sightly more frequent than the others.

3. using this method a point has 1/2 probability of being in the 1/2 r radius circle. this circle has 1/4th of the area of the entire circle. so the points are not evenly distributed.

4. this works! one caveat is that as n grows you start needing big number operations and the algorithm starts being somewhat slow.

@ vali_MIT
7. good job. this works.

@ Dan-Alexandru
1. you don't know p.

5. yes

6. average time

7. formula. you can see vali's solution.

@ Aurelian
6. Yes. This works.

I would do it slightly different:  the probability of seeing a new after already having i toys is (n - i) / n. The expected number of steps for an event that happens with probability p to happen is 1/p. So the expected number of steps for seeing a new toy after already seeing i toys is n/(n-i). Thus the total number of steps is
n / n + n / (n - 1) + ... + n/(n-i) + ... + n / 1 = n Hn

8. This works as well. How I would solve it:
the probability of line 4 being executed at step i is 1/i (the probability of the maximum number in a sequence of i numbers being in the last position of the sequence is 1/i).
so the expected number of times step 4 is executed is 1/1 + 1/2 + ... + 1/n = Hn.

@ Mihai Ciucu
2. good job. the key insight is that you have to ignore a few numbers to get uniform results. (now the algorithm is non deterministic but has a short expected execution time)

3. yup. using a random number between 0 and r*r then doing sqrt gives us a good distribution.


To sum up we don't have a good solution for 1. We don't have an efficient solution for 4. We don't have any solution for 5.

[•auRSTAR]

I have an idea for first problem, it's an adaptation of Mihai's solution for second problem.
Let's 0 be Tail-Head and 1 be Head-Tail. The probabilities for 0 and 1 are equal, p * (1 - p). We roll the dice twice until we see Tail-Head or Head-Tail. So we ignore Head-Head and Tail-Tail.

[•Cosmin]

It works. John von Neumann came up with the same solution.

[•auRSTAR]

For problem 4:
When I read the statement, first thing that came in my mind was the Petr's problem from Google Code Jam Round 1A.
 
Let's consider X be the identity permutation of length N, initially.
For every positive integer i, i<= N, we generate a random number j from [i+1, N] and swap X[ i ] with X[j]. Pr(X[ i ] == k) = 1/n, for every i,k positive integers, i,k<= N.

[•Cosmin]

Yes this works, the algorithm is called Fisher–Yates shuffle or Knuth shuffle.

[•dutzul]

5)  Assign to each element a random key , keep a heap with the biggest K pair<key,value> as we iterate trough the elements.

[•Cosmin]

5) This works, it takes O(n log k) time and O(k) space. There's another solution in O(n) time and O(k) space. (you can also improve this one to take O(n) time and O(k) space)

[•dariusdarius]

5) Let me suggest another solution for this problem.

Let's consider that we already have a solution: k random numbers from the first n - 1 numbers in the stream. Each number in the first n - 1 had a k/(n - 1) chance of remaining in the sample, and now all n numbers must have a k/n chance of remaining. Let's consider we can use a uniform random function that can generate random numbers in the range (1..n); use this function to get a random x. We now have 2 possible situations:

- x <= k : we replace the X-th number in our sample with A[n].
- x > k : we do nothing.

It is obvious that the nth number has a k/n chance of entering the sample. All of the previous numbers have a chance of 1/n of being eliminated from the sample by A[n]. Therefore their chance of remaining is (n - 1)/n after this step, so the final chance is k/(n - 1) * (n - 1)/n = k/n. The algorithm is correct, and it takes O(1) for each number coming in, so the total time complexity is linear in the number of integers in the stream. Also, only O(k) memory is required for the implementation.

[•dariusdarius]

4) I believe I have a correct O(N * log N) time and O(N) memory solution:

For simplicity, let's define a uniform random function for the interval 1..N as rand(N).

Call rand(N) to get the first number in the permutation. Then, to get the k-th element, consider x = rand(N - k + 1). We want element k of the permutation to be the x-th of the remaining ones (for example, if n = 7 and k = 4 and so far we have P = 5, 2, 4 the remaining ones are 1, 3, 6, 7 so x = 3 would actually mean that P[4] = 6). We can find this using a Fenwick Tree or a Segment Tree, both requiring a total of O(N * log N) time and O(N) memory.

[•Cosmin]

@Darius
4) Good job. This is called the "Reservoir Sampling" algorithm.

There's a interesting weighted version of the problem where the algorithm gets more complex.

5) I think this is ok, but the Knuth shuffle algorithm mentioned above is O(n).

To shuffle an array a of n elements (indices 0..n-1):
  for i from n − 1 downto 1 do
       j ← random integer with 0 ≤ j ≤ i
       exchange a[j] and a[ i]

[•Cosmin]

Good job guys! I think we went through all the problems.

[•catalincraciun]

2.  rand7()=rand5()+rand5()%3 Is this a correct answer? 

[•Cosmin]

Good question. Probability is pretty tricky to get right. The algorithm you mention doesn't work.
Try running it 1000 times and see how frequent are the 7 results.

I've implemented the algorithm you mention and the algorithm described in the previous comments in python. Here's how they compare:

Cod:

import random

def rand5():
    return random.randint(1, 5)

def badfunction():
  f = [0] * 8
  for i in xrange(0, 1000):
      f[rand5() + rand5() % 3] += 1
  print 'badfunction'
  print f


def rand0_24():
    return (rand5() - 1) * 5 + rand5() - 1

def rand7():
    r = rand0_24()
    while r >= 21:
        r = rand0_24()
    return r % 7 + 1

def goodfunction():
  f = [0] * 8
  for i in xrange(0, 1000):
      f[rand7()] += 1
  print 'goodfunction'
  print f

badfunction()
goodfunction()

the results are
badfunction
[0, 46, 108, 199, 195, 206, 165, 81]
goodfunction
[0, 144, 162, 142, 140, 131, 149, 132]

So you can see the function you mentioned returns 1 much less frequently than it returns 3.

Having a good random generator is important. Here's an example where not caring about the random function went wrong http://www.cigital.com/papers/download/developer_gambling.php

[•szili]

Problem number 3 can be done by using polar coordinates. Generate a value for r in the range [0, R] and generate another value theta in the range (0, 360). After obtaining these one can get the euclidean coordinates using some trigonomoetric functions. Check out Wikipedia for the details. e.g. for the first quadrant: x = sin(theta) * r; y = cos(theta) * r

[•Cosmin]

no, this doesn't yield a uniform random point. read the previous comments to see why.

[•szili]

Yes, I see, you are right. The radius should be generated proportionally to the number of points at that radius. Actually there is another solution to this problem as well but it is less efficient. It can be solved in a Monte Carlo simulation manner. Just generate x between 0 and R, generate y between 0 and R and if it is within a distance smaller than R with respect to the center of the circle return it. It rejects the points outside the circle but I think it does work.