# Let's discuss Mathematics

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

1. ### ParadigmShifterRandom 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. ### IdiotsOppositeBoom, headshot.

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

3. ### ParadigmShifterRandom Nonsense Generator

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

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

5. ### ParadigmShifterRandom 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. ### ParadigmShifterRandom 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. ### SpoonwoodGrand 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

8. ### ParadigmShifterRandom 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. ### sanabasPsycho BunnyHall 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. ### ParadigmShifterRandom 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. ### sanabasPsycho BunnyHall 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. ### SouronThe 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. ### sanabasPsycho BunnyHall 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. ### ParadigmShifterRandom 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. ### Miseisle 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...

16. ### ParadigmShifterRandom 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. ### AtticusDeityRetired 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. ### ParadigmShifterRandom 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. ### Miseisle 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. ### ParadigmShifterRandom 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