Mathematics desk
< April 10	<< Mar \| April \| May >>	April 12 >

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

April 11

Probability

If I have a large number of black and white balls in a container, in a known ratio, then the probability of drawing a (say) black ball is directly related to that ratio. My question is - given that ratio (and a pot of balls sufficiently large) how do I calculate the probability of ending up with at least one black ball after a given number of draws. Or putting it another way, how many draws do I have to make for there to be an 80%, 90%, or other probability of seeing a black ball? Apologies for what is probably either a very basic question, or incorrectly framed - I lack the terminology to search for the answer!

Question relates to the probability of capturing rare events on a digital storage oscilloscope given a timebase and a waveforms/second update rate.

Ic0nwiki (talk) 11:01, 11 April 2013 (UTC)[reply]

If your rare event will not influence future occurrences (equivalent to a very large number of black and white balls) then a simple Binomial distribution is appropriate. For calculations (to save lots of arithmetic), this is often approximated using a Normal distribution with mean np and variance np(1-p) where p is the proportion of black balls, or the probability that the event will occur, and n is the number of draws or trials. (Drawing balls from a limited container without replacement requires a hypergeometric distribution, but this doesn't seem appropriate here.) For your question, it will be easier to calculate the probability that the event will not occur, then subtract from one to get the probablility that it will occur. See Binomial_distribution#Normal_approximation for detail, or ask again here. Dbfirs 11:33, 11 April 2013 (UTC)[reply]

That's tantalisingly close - I've been looking at the binomial theorem page and doing some sums. I started with some simple n, p, k combos - n=some suitably large number, p=0.5, k=1. I couldn't work out where I was going wrong at first - it was giving me implausibly small numbers - until I tried n=1, n=2, ... - I realised that the formula is telling the probability of exactly one success (yes, obvious to you all!), whereas I don't care *how* many successes, so long as n>=1 (n=1, n=2... n=p). Does this make it easier or harder to do? Ic0nwiki (talk) 14:24, 11 April 2013 (UTC)[reply]

I think you missed the part of Dbfirs' answer that said "it will be easier to calculate the probability that the event will not occur, then subtract from one to get the probablility that it will occur." -- if you don't do it that way, then you have to add together a lot of probabilities, e.g. the chance of exactly one success, exactly two,... up to exactly n. So, instead use the formulae to compute the probability of no black balls, then P(at least one black)=1-P(no black). Does that make sense? SemanticMantis (talk) 15:28, 11 April 2013 (UTC)[reply]

I did miss it - or rather I didn't understand. Then as I discovered the problem and was mulling how one could add up all the probabilities I had a blinding insight that you could do it the other way round and... and then I realised that's what I'd been told in the first place. Story of my life - someone's already had my blinding insights.

Ic0nwiki (talk) 09:43, 12 April 2013 (UTC)[reply]

Ranking that best satisfies set of orderings

If I have a set of orderings of the form (for example) {a > b, c > b, b > d, ...}, what techniques could I use to determine a ranking of the elements involved that maximises the number of constraints satisfied? Are there any better objective functions I could seek to maximise other than number of constraints satisfied? Thanks in advance for any pointers, I'm finding this quite hard to search for because I'm not sure what terms to use. --81.101.105.36 (talk) 14:39, 11 April 2013 (UTC)[reply]

If you're not careful about how you pose such problems, it's easy to run afoul of Arrow's paradox. Sławomir Biały (talk) 19:20, 11 April 2013 (UTC)[reply]

Your first question is the maximum acyclic subgraph problem. -- BenRG 22:44, 11 April 2013 (UTC)

Thanks, I would never have found that. As it happens, I solved this with a soft-margin SVM by determining ratings for each item that minimise the error of unsatisfied constraints. --81.101.105.36 (talk) 01:22, 12 April 2013 (UTC)[reply]