My Math Forum  

Go Back   My Math Forum > High School Math Forum > Algebra

Algebra Pre-Algebra and Basic Algebra Math Forum


Reply
 
LinkBack Thread Tools Display Modes
May 14th, 2008, 07:06 AM   #1
Newbie
 
Joined: May 2008

Posts: 3
Thanks: 0

Odds of seeing all possible values

Is there a way to compute the odds of seeing all possible values in a set of values?

For example, on average, how many times would you have to throw a 6 sided dice to see all 6 possible numbers?

Or, if you have a 1000 items in a database and you are shown one randomly, on average, how many times would you be shown items before you have seen each item at least once?

For the dice problem, I simulated it in Excel and after 5000 runs I had an average of 15 rolls before you have seen all 6 possibilities. I'm just looking for the mathematics to verify this answer.
WayneC is offline  
 
May 14th, 2008, 08:51 AM   #2
Global Moderator
 
CRGreathouse's Avatar
 
Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 938

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
I find an average (expected number of flips before all sides show up) of 14.7, exactly, for a six-sided die. Other averages: 3 for a fair coin, 25/3 for a three-sided die, and 761/35 for an eight-sided die.

I'll see if I can explain my method.
CRGreathouse is offline  
May 14th, 2008, 11:57 AM   #3
Newbie
 
Joined: May 2008

Posts: 3
Thanks: 0

This is what I came up with:

For the dice example N = 6

1 + 1/((N-1)/N) + 1/((N-2)/N) + 1/((N-3)/N) ... + 1/((N-5)/N)

I just don't know how to express this or solve it more concisely. Using the above I would still have to do 1000 calculations if N = 1000.
WayneC is offline  
May 19th, 2008, 06:15 AM   #4
Newbie
 
Joined: May 2008

Posts: 3
Thanks: 0

For anyone else that may happen upon this... This problem is more famously known as the "Coupon Collector Problem". Just do a search for that and you will find lots of information. An approximation for the solution is: N*ln(N).
WayneC is offline  
Reply

  My Math Forum > High School Math Forum > Algebra

Tags
odds, values



Thread Tools
Display Modes


Similar Threads
Thread Thread Starter Forum Replies Last Post
What are the odds? Ebed Advanced Statistics 3 January 23rd, 2014 07:48 PM
What are the odds? Sixteen08 Advanced Statistics 1 April 25th, 2013 02:01 PM
What Are The Odds Of This?? travelin4fun Advanced Statistics 4 July 26th, 2012 06:05 AM
find values of ? that correspond to the ? values? space55 Calculus 0 October 10th, 2010 03:23 PM
What are my odds mbodenheimer Number Theory 3 December 31st, 1969 04:00 PM





Copyright © 2019 My Math Forum. All rights reserved.