Drexel dragonThe Math ForumDonate to the Math Forum



Search All of the Math Forum:

Views expressed in these public forums are not endorsed by Drexel University or The Math Forum.


Math Forum » Discussions » sci.math.* » sci.math.independent

Topic: Prob of flipping coin n times, at no time with #h > #t?
Replies: 10   Last Post: Feb 14, 2013 2:25 AM

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
JohnF

Posts: 151
Registered: 5/27/08
Re: Prob of flipping coin n times, at no time with #h > #t?
Posted: Feb 14, 2013 2:25 AM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

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 h-t-... sequences of n flips,
>>> comprising a binomial tree (or pascal's triangle),
>>> with 50-50 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 (p-q)/(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 n-set 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 )



Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© Drexel University 1994-2014. All Rights Reserved.
The Math Forum is a research and educational enterprise of the Drexel University School of Education.