Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM or The Math Forum.


JohnF
Posts:
219
Registered:
5/27/08


Re: Prob of flipping coin n times, at no time with #h > #t?
Posted:
Feb 14, 2013 2:25 AM


James Waldby <not@valid.invalid> wrote: > On 06 Feb 2013 14:16:33 +0000, Robin Chapman wrote: >> On 06/02/2013 13:42, JohnF wrote: >>> What's P_n, the prob of flipping a coin n times, >>> and at no time ever having more heads than tails? >>> There are 2^n possible ht... sequences of n flips, >>> comprising a binomial tree (or pascal's triangle), >>> with 5050 prob of going left/right at each node. >>> So, equivalently, how many of those 2^n paths never >>> cross the "center line" (#h = #t okay after even number >>> of flips)? >> >> See the ballot theorem: >> http://en.wikipedia.org/wiki/Ballot_theorem > > Bertrand's ballot theorem addresses the problem "In an > election where candidate A receives p votes and candidate > B receives q votes with p > q, what is the probability > that A will be strictly ahead of B throughout the count?" > and gives answer (pq)/(p+q). In the current problem, > A must be equal to B or ahead of B throughout the count, > so Bertrand's theorem doesn't quite apply and gives wrong > answers. > > Anyhow, correct answers for the stated question are given by > 1/(2^n) times "central binomial coefficients: C(n,floor(n/2)" > (see <http://oeis.org/A001405>). > > As noted at that link, central binomial coefficients count > "the maximal number of subsets of an nset such that no one > contains another" (ie max sizes of Sperner families) > <http://en.wikipedia.org/wiki/Sperner_family#Sperner.27s_theorem> > which probably can be equated to the current problem with a > little work. > > Central binomial coefficients also count the "number of left > factors of Dyck paths, consisting of n steps", where a Dyck > path is a "staircase walk from (0,0) to (n,n) that lies strictly > below (but may touch) the diagonal y=x" which has an obvious > parallel to the current problem. > <http://mathworld.wolfram.com/DyckPath.html>
Thanks for the additional info, Jim. Note that the "comments" in your A001405 link indicate ceil(.), rather than floor(.) stated at the top, in agreement (i.e., ceil in agreement) with other posts in this thread.  John Forkosh ( mailto: j@f.com where j=john and f=forkosh )



