Jump to content


Welcome to BrainDen.com - Brain Teasers Forum

Welcome to BrainDen.com - Brain Teasers Forum. Like most online communities you must register to post in our community, but don't worry this is a simple free process. To be a part of BrainDen Forums you may create a new account or sign in if you already have an account.
As a member you could start new topics, reply to others, subscribe to topics/forums to get automatic updates, get your own profile and make new friends.

Of course, you can also enjoy our collection of amazing optical illusions and cool math games.

If you like our site, you may support us by simply clicking Google "+1" or Facebook "Like" buttons at the top.
If you have a website, we would appreciate a little link to BrainDen.

Thanks and enjoy the Den :-)
Guest Message by DevFuse
 

Photo
- - - - -

Colored balls in a bag


Best Answer plasmid, 11 May 2014 - 06:02 PM

Spoiler for atrocious but verified answer

 

Spoiler for this agrees with simulation - perl code
Go to the full post


  • Please log in to reply
10 replies to this topic

#1 BMAD

BMAD

    Senior Member

  • Members
  • PipPipPipPip
  • 1674 posts
  • Gender:Female

Posted 06 May 2014 - 02:12 PM

There are N balls in the bag. Each one has a distinct color. You draw one ball randomly from the bag, record its color and put it back. Calculate the probability that after T draws you've seen M distinct colors. 
 
(T > 0, M > 0, M <= min(T, N) )

  • 0

#2 m00li

m00li

    Junior Member

  • Members
  • PipPip
  • 71 posts

Posted 06 May 2014 - 03:51 PM

Spoiler for solution attempt

  • 0

#3 bonanova

bonanova

    bonanova

  • Moderator
  • PipPipPipPip
  • 5827 posts
  • Gender:Male
  • Location:New York

Posted 09 May 2014 - 09:13 AM

Spoiler for Looks like


  • 0
The greatest challenge to any thinker is stating the problem in a way that will allow a solution.
- Bertrand Russell

#4 bonanova

bonanova

    bonanova

  • Moderator
  • PipPipPipPip
  • 5827 posts
  • Gender:Male
  • Location:New York

Posted 10 May 2014 - 02:09 PM

M different colors means: exactly M different colors, not: at least M colors, right?


  • 0
The greatest challenge to any thinker is stating the problem in a way that will allow a solution.
- Bertrand Russell

#5 plasmid

plasmid

    Senior Lolcat

  • VIP
  • PipPipPipPip
  • 1430 posts
  • Gender:Male

Posted 10 May 2014 - 06:23 PM

Bonanova: using that formula with 3 balls being drawn 3 times...

probability of drawing 1 color
3! 13-1 / 33(3-1)! = 6*1 / 27*2 = 6/54

probability of drawing 2 colors
3! 23-2 / 33(3-2)! = 6*2 / 27*1 = 12/27

probability of drawing 3 colors
3! 33-3 / 33(3-3)! = 6*1 / 27*1 = 6/27

Sum of all three of those is less than 1.

I'm having trouble following m00li's logic. I got lost as soon as he started talking about selecting balls from an infinite choice of colors (which was pretty soon).
  • 0

#6 m00li

m00li

    Junior Member

  • Members
  • PipPip
  • 71 posts

Posted 11 May 2014 - 10:34 AM

Bonanova: using that formula with 3 balls being drawn 3 times...

probability of drawing 1 color
3! 13-1 / 33(3-1)! = 6*1 / 27*2 = 6/54

probability of drawing 2 colors
3! 23-2 / 33(3-2)! = 6*2 / 27*1 = 12/27

probability of drawing 3 colors
3! 33-3 / 33(3-3)! = 6*1 / 27*1 = 6/27

Sum of all three of those is less than 1.

I'm having trouble following m00li's logic. I got lost as soon as he started talking about selecting balls from an infinite choice of colors (which was pretty soon).

You are not alone Plasmid. I am having trouble too :) I must have been high on something that day
 My solution is for cases where a 'selection' is being made out of n different colors. I should have calculated permutations and not selections.


  • 0

#7 plasmid

plasmid

    Senior Lolcat

  • VIP
  • PipPipPipPip
  • 1430 posts
  • Gender:Male

Posted 11 May 2014 - 06:02 PM   Best Answer

Spoiler for atrocious but verified answer

 

Spoiler for this agrees with simulation - perl code

  • 0

#8 bonanova

bonanova

    bonanova

  • Moderator
  • PipPipPipPip
  • 5827 posts
  • Gender:Male
  • Location:New York

Posted 12 May 2014 - 09:37 AM

My formula made such sense to me (this is often the case until someone explains the logic that I overlook) that I posted it.  Then, embarrassingly, it did not agree with simulations.
 
The second part of the probability (after M colors appeared in M draws)
appeared to be incorrect by a factor of 2. I've been chasing that factor of 2
for several days, but only part time owing to preparations for a choral
performance this weekend. More, perhaps, to follow this week.
 
plasmid, your post #7 may have found it, since you have agreement with simulation.
I'll read it after I've given my approach another shot.
 
FWIW here is my simulation of 10000 cases for N = 10.
The 10 columns are for M = 1 ... 10.
The 20 rows are for T = 1 ... 20
The table entries are percent, rounded to nearest integer.

 

My equations agree for the major diagonal.

But they underestimate the probabilities elsewhere.

      10 MNTHIST 10000
100  0  0  0  0  0  0  0  0  0
 10 90  0  0  0  0  0  0  0  0
  1 27 72  0  0  0  0  0  0  0
  0  6 43 50  0  0  0  0  0  0
  0  1 18 51 30  0  0  0  0  0
  0  0  6 34 45 15  0  0  0  0
  0  0  2 18 43 31  6  0  0  0
  0  0  1  8 33 40 17  2  0  0
  0  0  0  4 21 41 28  6  0  0
  0  0  0  2 12 36 35 14  1  0
  0  0  0  1  7 28 38 22  4  0
  0  0  0  0  4 20 38 29  8  1
  0  0  0  0  2 15 34 35 13  1
  0  0  0  0  1 10 30 38 19  3
  0  0  0  0  1  6 24 39 25  5
  0  0  0  0  0  4 20 39 30  7
  0  0  0  0  0  3 16 37 35 10
  0  0  0  0  0  2 12 34 39 13
  0  0  0  0  0  1  9 32 42 17
  0  0  0  0  0  1  6 28 44 22


  • 0
The greatest challenge to any thinker is stating the problem in a way that will allow a solution.
- Bertrand Russell

#9 m00li

m00li

    Junior Member

  • Members
  • PipPip
  • 71 posts

Posted 25 May 2014 - 01:13 AM

More recursions:

 

Let f(t,m) denote the number of ways of arranging m colored balls in t slots, where t >= m and supply of each m coloured ball is infinite. Then final answer is nCmf(t,m) / nt

 

Here are the different recursions I have come up with for f(t,m)   (alas, no direct formula in m,n)

 

1) mtmC1f(t,1) - mC2f(t,2) - mC3f(t,3) .... - mCm-1f(t,m-1) 

 

2) tC1f(t-1,m-1) + tC2f(t-2,m-1) + tC3f(t-3,m-1) + ... + tCt-m+1f(m-1,m-1)

 

3) mf(t-1,m-1) + m2f(t-2,m-1) + m3f(t-3,m-1) + ... + mt-m+1f(m-1,m-1)

 

4) m( f(t-1,m) + f(t-1,m-1) )

 

where f(t,1) = 1, f(t,2) = 2t-2, and f(t,t) = t!


  • 0

#10 bonanova

bonanova

    bonanova

  • Moderator
  • PipPipPipPip
  • 5827 posts
  • Gender:Male
  • Location:New York

Posted 25 May 2014 - 01:14 AM

So, I wonder. Is there no closed form solution?


  • 0
The greatest challenge to any thinker is stating the problem in a way that will allow a solution.
- Bertrand Russell




0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users