it is... but a small mistake in the code again...
def get_random_obj( objstream ):
count = 1
obj = objstream.get()
while not objstream.end():
* count += 1*
r = rand(0, count)
if r == 0:
obj = objstream.get()
else:
objstream.get() #discard
return obj
note that you cannot make sense of equal probability if there are infinite
number of objects. Hence assume that there are N objects streaming.
*Loop invariant*: probability of choosing any of the previously streamed
objects at the end of iteration n is
P[k, n] = probability that kth object is chosen at iteration n
*Base*: at the end of first iteration, P[1,1] = P[random(0,2)=0] = 1/2
*Induction*:
Assume the invariant to be true at all iterations < n
P[n, n] = P[random(0, n) = 0] = 1/n
P[k, n] = P[k, n-1]*(1-P[n,n]) = (1/(n-1))*(1 - (1/n)) = 1/n
therefore at the end of N iterations, the probability of choosing any object
is 1/N
Anil
On Sun, Jun 27, 2010 at 9:19 AM, sharad kumar <[email protected]>wrote:
> @above
> probabilty for all numbers in d stream must be *same*.....whether first or
> last....
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to [email protected].
> To unsubscribe from this group, send email to
> [email protected]<algogeeks%[email protected]>
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
