perplexus.info :: Algorithms : Select an Item

Select an Item (Posted on 2004-10-22)

Your job is to pick one ball from a collection of balls in such a way that every ball has an equal probability of being selected. The twist is that you do not know how many balls are in the collection. Each ball will be handed to you, one at a time. As each ball is handed to you you must decide (by some random process) whether to keep or discard the ball.

You must always be holding one and only one ball so that when a new ball is given to you, you must either discard it or keep it by discarding the previously held ball.

Submitted by Brian Smith

Rating: 3.2500 (8 votes)

Solution: (Hide)

Pick the 1st ball (with probability 1)
Replace the ball in hand with the 2nd with probability 1/2
Replace the ball in hand with the 3rd with probability 1/3
...
Replace the ball in hand with the Nth with probability 1/N
first round:
1: 1/2
2: 1/2

second round:
11: 1/2 * 2/3 = 2/6 total ending in 1 = 1/3
13: 1/2 * 1/3 = 1/6
22: 1/2 * 2/3 = 2/6 total ending in 2 = 1/3
23: 1/2 * 1/3 = 1/6 total ending in 3 = 1/3

third round:
111: 1/2 * 2/3 * 3/4 = 6/24 total ending in 1 = 1/4
114: 1/2 * 2/3 * 1/4 = 2/24
133: 1/2 * 1/3 * 3/4 = 3/24
134: 1/2 * 1/3 * 1/4 = 1/24
222: 1/2 * 2/3 * 3/4 = 6/24 total ending in 2 = 1/4
224: 1/2 * 2/3 * 1/4 = 2/24
233: 1/2 * 1/3 * 3/4 = 3/24 total ending in 3 = 1/4
234: 1/2 * 1/3 * 1/4 = 1/24 total ending in 4 = 1/4
Starting with round 1 (r = 1), replace the object you are holding with the new object with a probability of 1/r. Then increment r and repeat for the next round.
Charlie offers a similar explanation here.

Comments: ( You must be logged in to post comments.)

Subject	Author	Date
re: Random	Akhil	2006-06-16 18:30:34
re(3): No Subject	bob909	2004-10-26 07:56:41
Agree with Charlie	owl	2004-10-23 23:27:42
re(2): No Subject	Federico Kereki	2004-10-23 12:09:52
re: No Subject	bob909	2004-10-23 07:37:12
No Subject	bob909	2004-10-23 05:54:01
re(4): Very Simple	Charlie	2004-10-22 19:09:22
re(3): Very Simple	RandyOrton	2004-10-22 18:19:43
re(2): Very Simple	Charlie	2004-10-22 17:38:27
re: Very Simple	RandyOrton	2004-10-22 16:37:58
Very Simple	Old Original Oskar!	2004-10-22 16:01:20
I am dumb	RandyOrton	2004-10-22 15:48:36
Random	RandyOrton	2004-10-22 15:46:23

Please log in:

Login:
Password:
Remember me:

Sign up! \| Forgot password

Search:

Search body:

Forums (1)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (6)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:


perplexus dot info