Puzzle: probability problem

Here is an interesting probability problem who recently generated long discussions in our team:

Say that you have an array of N boolean values, with all values initially set to FALSE. At each iteration step, you arbitrary pick an element in the array and set it to TRUE. What is the average number of elements set to TRUE after K iteration steps?

By the way, as an anecdotic fact, this problem came from analyzing paged pool memory consumption when you randomly access a large volume over time. I will not go in more details, but I just wanted to mention this problem as a particular application of theoretical statistics in the design of operating system components...

Comments

• Anonymous
  December 28, 2005
  Well, I'd try and attack a problem like this with a recurrence relation.
  
  Fix N.
  
  Then, define a function f(k,x) that is the probability that after k steps, x of the N elements are true.
  
  f(0,x)=1 if x=0 and 0 otherwise is a boundary condition.
  
  f(k,0)=1 if k=0 and 0 otherwise is another boundary condition.
  
  f(k,x)=f(k-1,x)x/N+f(k-1,x-1)(N-x+1)/N is the recurrence.
  
  The average number of true elements after K steps is then
  
  A(K)=sum from x=0 to N of xf(K,x).
  
  Plugging the recurrence into the average and iterating a few times, it looks like A(K)=N(1-(1-1/N)^K).

• Anonymous
  December 28, 2005
  Interesting (both the recurrence and the final formula are indeed correct). So what formula did you find for f(k,x)?
  
  Thanks, Adi

• Anonymous
  December 28, 2005
  The different approaches to this problem in our group were interesting. Adi approached it with the recurrence that Nicholas Allen used. I used an inclusion-exclusion argument to show that f(k,x) is defined as follow:
  
  f(k,x) = 1/n^k (n choose x)sum from j = 0 to x-1 (-1)^j(x choose j)(i-j)^k
  
  This gives you the formula for the probability, but it's a pain to simplify it down to n*(1-(1-1/n)^k).
  
  The simplest solution that another member of our group came up with is to consider the expected number of elements set for each element of the array (sounds weird). This is equal to the probability that a single element is 1, i.e. 1 - (1-1/n)^k. The expected number of elements set in the whole array is the sum of the expectations, i.e. n(1-(1/n)^k)
  

• Anonymous
  December 28, 2005
  The comment has been removed

• Anonymous
  April 03, 2008
  PingBack from http://drinksandbirthdaysblog.info/antimail-puzzle-probability-problem/

• Anonymous
  April 04, 2008
  PingBack from http://drinksairportsblog.info/antimail-puzzle-probability-problem/