1. We have added a Gift Upgrades feature that allows you to gift an account upgrade to another member, just in time for the holiday season. You can see the gift option when going to the Account Upgrades screen, or on any user profile screen.
    Dismiss Notice

Let's discuss Mathematics

Discussion in 'Science & Technology' started by ParadigmShifter, Mar 16, 2009.

  1. ParadigmShifter

    ParadigmShifter Random Nonsense Generator

    Joined:
    Apr 4, 2007
    Messages:
    21,810
    Location:
    Liverpool, home of Everton FC
    We did a bit of knot theory first in topology - that was interesting, and doesn't use a metric.
     
  2. IdiotsOpposite

    IdiotsOpposite Boom, headshot.

    Joined:
    Mar 10, 2007
    Messages:
    2,718
    Location:
    America.
    Explain this "knot theory" to a poor college undergrad.
     
  3. ParadigmShifter

    ParadigmShifter Random Nonsense Generator

    Joined:
    Apr 4, 2007
    Messages:
    21,810
    Location:
    Liverpool, home of Everton FC
  4. IdiotsOpposite

    IdiotsOpposite Boom, headshot.

    Joined:
    Mar 10, 2007
    Messages:
    2,718
    Location:
    America.
    A knot can always be untied. Just use the Gordian knot method.
     
  5. ParadigmShifter

    ParadigmShifter Random Nonsense Generator

    Joined:
    Apr 4, 2007
    Messages:
    21,810
    Location:
    Liverpool, home of Everton FC
    No cutting is allowed.

    Some knots are not the same as the others. The Jones polynomial says which knots definitely aren't equivalent.
     
  6. ParadigmShifter

    ParadigmShifter Random Nonsense Generator

    Joined:
    Apr 4, 2007
    Messages:
    21,810
    Location:
    Liverpool, home of Everton FC
    Well there was an interesting question raised in the Civ4 GD forum.

    What is the distribution of the number of runs of consecutive heads/tails in a coin toss experiment? How many tosses would you need to perform to have a probability of > 0.5 to have a run of 10 consecutive heads or tails?

    I think the continuous case may be the F-distribution, but don't quote me on that.
     
  7. Spoonwood

    Spoonwood Grand Philosopher

    Joined:
    Apr 30, 2008
    Messages:
    4,887
    Location:
    Ohio
    Well, you just need a run of 10 consecutive heads or tails, and with that each coin has a probability of heads or tails respectively of 1. Oh, you mean before you see the results of the coin flip :lol:
     
  8. ParadigmShifter

    ParadigmShifter Random Nonsense Generator

    Joined:
    Apr 4, 2007
    Messages:
    21,810
    Location:
    Liverpool, home of Everton FC
    My intuition says it should be related to log2 of the number of trials.
     
  9. sanabas

    sanabas Psycho Bunny Hall of Fame Staff

    Joined:
    Nov 24, 2004
    Messages:
    4,269
    Location:
    Canberra, Australia
    Maybe look at each tail as a separate event?

    i.e. T is length 1, p = 0.5

    HT is length 2, p=0.25

    HHT is length 3, p=0.125

    HHHHHHHHHT is length 10, p = 0.000977

    HHHHHHHHHH is length 10, p = 0.000977

    Then all you want is how long before 10 heads comes up.

    It's once in 1024 trials, which should mean that on average it comes up in the 1024th trial (not 100% sure, can't be bothered checking.)

    1024 trials will have an average length of 512 x 1 + 256 x 2 + 128 x 3 + ... + 1 x 10 + 1 x 10 = 2046 coin tosses.

    Easy enough to redo it for p different to 0.5, it's still p = 1/1024 for the individual event, and the average event is just under 2 tosses long.
     
  10. ParadigmShifter

    ParadigmShifter Random Nonsense Generator

    Joined:
    Apr 4, 2007
    Messages:
    21,810
    Location:
    Liverpool, home of Everton FC
    With 100 tosses you get more than one chance to get a run of 10.
     
  11. sanabas

    sanabas Psycho Bunny Hall of Fame Staff

    Joined:
    Nov 24, 2004
    Messages:
    4,269
    Location:
    Canberra, Australia
    Yep, you get approximately 45 chances.

    I can't tell if that was a response to my post, and if it was, what it was refuting.

    Every time a tail comes up, you get a new chance to have a run of 10 heads. Every time a head comes up, you're still in the same chance to get 10 heads. So every time a tail appears, there's a 1/1024 chance that that's your tail before the run of 10 heads.
     
  12. Souron

    Souron The Dark Lord

    Joined:
    Mar 9, 2003
    Messages:
    5,947
    Location:
    (GMT-5)
    May be you can do something like this:
    [Chance to get a run of 10 in 10 flips]*90-sum(i=11,20,[Chance to get a run of i in i flips]*(100-i))-2*sum(i=21,30,[Chance to get a run of i in i flips]*(100-i))-3*sum(i=31,40,[Chance to get a run of i in i flips]*(100-i))-4*sum(i=41,50,[Chance to get a run of i in i flips]*(100-i))

    That is, the number of chances to get a run of 10, times that probability, minus all the ways a run can be double counted.

    EDIT2:
    2^(1-10)*90-(sum(i=11 to 20) 2^(1-i)*(100-i)) -(2*sum(i=21 to 30)2^(1-i)*(100-i))-(3*sum(i=31 to 40) 2^(1-i)*(100-i))-(4*sum(i=41 to 50) 2^(1-i)*(100-i))

    Wolfram yeilds:
    0.00375735
     
  13. sanabas

    sanabas Psycho Bunny Hall of Fame Staff

    Joined:
    Nov 24, 2004
    Messages:
    4,269
    Location:
    Canberra, Australia
    My back of the envelope calculation says roughly 4.3% chance of getting a run of 10 heads in 100 coin flips.

    It also says 52.3% chance of a run of 6 heads, and 0.064% chance of a run of 16 heads.

    Who wants to do 1 million tests of 100 virtual coin flips and see how many have a run of 10 heads? I'm not, because my programming skills are non-existent.
     
  14. ParadigmShifter

    ParadigmShifter Random Nonsense Generator

    Joined:
    Apr 4, 2007
    Messages:
    21,810
    Location:
    Liverpool, home of Everton FC
    I'd do a proper histogram of the results not just record whether we got 10+ in a row or not.

    It's very easy in C++ using a std::map for the histogram and a std::vector for the coin toss results.

    I can't be bothered downloading Visual C++ express again (I used to have it but I had to reinstall windows).

    EDIT: Looks like it has to do with Fibonacci numbers http://mathworld.wolfram.com/CoinTossing.html
     
  15. Mise

    Mise isle of lucy

    Joined:
    Apr 13, 2004
    Messages:
    28,622
    Location:
    London, UK
    Maybe look at it from a different way, e.g. what's the probability that a 100 digit number will contain a string of 10 even digits in a row.

    (Or if your brain naturally thinks in binary, a 100 bit number containing 10 "1"s in a row.)

    I haven't quite woken up yet, so bear with me... :p
     
  16. ParadigmShifter

    ParadigmShifter Random Nonsense Generator

    Joined:
    Apr 4, 2007
    Messages:
    21,810
    Location:
    Liverpool, home of Everton FC
    It's a lot easier in binary ;)

    You could enumerate all 2^100 possibilities to get the exact distribution... I suppose. I'm guessing that would take a while.

    EDIT: And it doesn't generalise for arbitrary number of tosses.
     
  17. Atticus

    Atticus Deity Retired Moderator

    Joined:
    Aug 20, 2006
    Messages:
    3,666
    Location:
    Helsinki, Finland
    I don't know how to do it, but I do know that this is nontrivial subject.

    Here's some preliminary thoughts:
    In order to succeed you need at least 10+k tosses, k=0,1,2,...
    For k=0 the probability is 1/2^10 = 1/1024
    Let's assume that you get HHHHHHHHHH first time after the 10+k:th toss and k>0. Then the k:th toss must be T. Also it is required that you haven't succeeded during the first k-1 tosses.
    Therefore the probability to succeed after n=10+k tosses is
    p_n =1/1024 * 1/2 *q_{n-11},
    where we have respectively the probability for success in the last 10 tosses, the tails on the k:th toss and failure during the first k-1 tosses, q_{k-1}=q_{n-11}.
     
  18. ParadigmShifter

    ParadigmShifter Random Nonsense Generator

    Joined:
    Apr 4, 2007
    Messages:
    21,810
    Location:
    Liverpool, home of Everton FC
    It's 1/512 to start: it doesn't have to be a run of heads, tails are OK too.
     
  19. Mise

    Mise isle of lucy

    Joined:
    Apr 13, 2004
    Messages:
    28,622
    Location:
    London, UK
    I'm pretty sure nobody will ever need an exact solution. Can it be estimated? Also I'm not going to worry about the requirement not to have won in the previous k-1 tosses. To me, the utility is just in a rough stab at how many units you'll need to throw at a stack of 10 units if both sides have equal strength. Useful in other games too of course.
     
  20. ParadigmShifter

    ParadigmShifter Random Nonsense Generator

    Joined:
    Apr 4, 2007
    Messages:
    21,810
    Location:
    Liverpool, home of Everton FC
    It's easy to estimate via simulation. You are the excel whizz Mise ;) As I said I haven't got a C++ compiler at the moment.

    I wonder if there is an exact distribution for this though, or a continuous version (like the normal for estimating binomial).

    EDIT: I have got a ZX Spectrum emulator ;) I'm not going to use that though :lol:
     

Share This Page