Friday, July 26, 2013

Probability of a 7 game win streak in DOTA2

Everyone has experienced win or loss streaks in DOTA2 that seem to go on forever. Is this luck, or skill, or just business as usual?

If you're feeling lucky, this is the hero for you 
(Valve Ogre Magi release art)


Probability Theory

Modelling the probability of a single streak is trivial. Most people seem to have a win / loss streak of about 7, and if each game was "well balanced" they'd have a 50% chance of winning - the chance of 7 wins in a row is 0.5^7 = 0.8%. Wow, so nearly everyone has experienced a 0.8% probability event on their account, that seems pretty unlikely.

Or is it?

Modelling the probability of a streak of length K occurring within a sample of N attempts is a lot harder. The chance of, say, a 4 win streak (probability 0.5^4=6.3%) in 20 games isn't simply 6.3% x 5... it's not even 1-(1-6.3%)^4. It's complicated because while each event is independent, what's being evaluated is not - we're evaluating each flip and checking if it's a successful streak, and this evaluation is dependent on the previous attempts. We need to delve into Markov Chains for this.

Fortunately, there is a simple formula that covers this, which involves K-Step Fibonacci Sequences. The regular Fibonacci Sequence we all learned about in school has K=2 where each successive integer is the sum of the two before it. For higher values of K, say 3, each integer is the sum of the 3 values before it, and so on.

The formula for determining the probability of a streak of length K occurring with a sample of N attempts is 1- (K Step Fibonacci Sequence of N+2) / (2^N). We can demonstrate this works on some trivial examples which we can hand calculate, for example, the probability of a 2 win streak occurring in 4 games. (skip this portion if you're not interested in the math and head on to the next...)

The denominator (2^N) is the number of total outcomes. (say A is win, B is lose)

4 Wins - AAAA
3 Wins - AAAB AABA ABAA BAAA
2 Wins - AABB ABBA BBAA ABAB BABA BAAB
1 Wins - ABBB BABB BBAB BBBA
0 Wins - BBBB

The 2 step Fibonacci Sequence is 1 1 2 3 5 8 13 21

I've bolded the ones above which have a 2 win streak (8 outcomes), total outcomes are 16, so the chance of a 2 win streak in 4 games is 50%. According the formula, the result of the Fibonacci Sequence for (N+2) is 8 as seen above, the value of 2^4 is 16, so the answer is 1-(8)/(16) = 50% which agrees with our result.

We can test this formula for a more complicated question, what's the probability of a 3 win streak in 5 games? 

5 wins - AAAAA
4 wins - AAAAB AAABA AABAA ABAAA BAAAA
3 wins - BBBBB AABBA ABBAAA BBAAA AABAB ABABA BABAA ABAAB BAABA BAAAB
2 wins - AABBB BAABB BBAAB BBBAA ABABB BABAB BBABA ABBAB BABBA ABBBA
1 wins - ABBBB BABBB BBABB BBBAB BBBBA
0 wins - BBBBB

The 3 step Fibonacci Sequence is 1 1 2 4 7 13 24 44

I've bolded the ones above which have a 3 win streak (8 outcomes), total outcomes are 32, so the chance of a 3 win streak in 5 games is 25%. According to the formula, the result of the Fibonacci Sequence for (N+2) is 24 as seen above, the value of 2^5 is 32, so the answer is 1-(8)/(32) = 25% which agrees with our result.


So about this 7 win streak...

Say the average player has 400 matches under his belt, and is wondering if his 7 win / loss streak is unusual. This means K=7 and N=400.

7 Step Fibonacci Sequence = 1 1 2 4 8 16 32 64 127 253 504 104 2000 3984 ...

Woah, we need to write this out until N+2 = 402 integers. Luckily computers can do it for us. Excel gives me a value of 5.2668E+119 for the 402th number in the sequence - that's a huge number, it is 119 digits long. I don't even know if we've invented a name for it. 12 digits long is "Trillion". 18 digits long is "Quintillion".

The denominator is 2^400. This is 2.5822E+120.

Finishing up the formula, 1-(5.2668E+119)/(2.5822E+120) = 79%.

This means that after 400 games, where the average win rate is 50%, there's 79% chance you will encounter at least one 7 game win streak. This means that out of a sample of 5 players, each of them with 400 games, 4 of them on average will have a 7 game win streak.

What this means is that a 7 game win (or loss) streak is not luck, or skill - it's just business as usual.

If you get up to 800 games played, there's a 79% chance you'll have an 8 game streak.

I couldn't calculate the equivalent 9 game streak chance for higher number of games because Excel apparently can't do numbers larger than 308 digits long (who knew).

If you have Excel or an equivalent (Google Spreadsheets, Open Office, etc) you can set up a K-Step Fibonacci sequence quite easily and calculate the various scenarios yourself.

No! It was not luck, but skill!
(The Celestial Starlight skin, created by Oni and Zaphk)