A place where share my thoughts and ideas with the world.

An Interesting Game

Get link

Facebook

Twitter

Pinterest

Email

Other Apps

Today I'm going to talk about an interesting game that I thought of, and in particular I'll show the probability that each player will win. While the rules of the game are not fair, the skill levels of each player are not necessarily the same either, so I formally define what I mean and find the conditions under which these factors balance out. Without further ado, here is the problem statement:

Alice and Bob play a game consisting of an indeterminate number of rounds. In each round, Alice and Bob compete to win the round, and thus score a point. Alice is more skilled at this game and so she wins each round with probability $ p > 0.5 $ (independent of the score and other context), meaning Bob wins each round with probability $ 1 - p $. The score starts at $ 0 - 0 $ and Bob wins if he ever has more points than Alice, and Alice wins otherwise. What is the probability that Bob wins this game? For what value of $ p $ is this game fair?

While the game never ends unless Bob wins, we can still reason about the game in a theoretical setting. The rest of this blog post is devoted to answering this question, so if you'd like to see a solution or know the answer, click the button below.

A natural place to start is to think about the probability of Bob winning when the current score is (a,b), then connect the probabilities between adjacent scores by defining some kind of recurrence relation. The first key observation to make is that the probability that Bob wins only depends on the score differential, or $ a - b $: the number of points Alice has minus the number of points Bob has. This allows us to define a recurrence relation with respect to one parameter, $ d = a - b $ rather than two, and these are much easier to reason about analytically.

If $ d = a - b = -1 $, then Bob has won by definition. Letting $ f(d) $ denote the function mapping score differentials to probabilities of Bob winning, we have $ f(-1) = 1 $. This is our base case, and now we can define a more general formula for $ f(d) $ as follows:
$$ f(d) = (1-p) \cdot f(d-1) + p \cdot f(d+1) $$
If you are familiar with recurrence relations, this formula should be pretty intuitive to you. If not, I encourage you to think carefully about how $ f $ is defined in English, then convince yourself that the mathematical definition is consistent with it. This formula holds because Bob scores the next point with probability $ 1-p $ and the score differential goes down by one. Similarly, Alice scores the next point with probability $p$ and the score differential goes up by one. We are interested in $ f(0) $ - the probability that Bob wins when the score differential is $ 0 $, because that's the score differential when the game first starts.

Now that we have a recurrence relation for $ f(d) $, we'd like to find a closed form expression for it in terms of $ p $ and $ d $ so we can just plug in $ d = 0 $ to get our answer. However, using another clever insight we can get around the need for doing that (although as I'll show, it's easy to recover $f(d)$ from $ f(0) $ anyway). Using the recurrence relation defined above, we know:
$$ f(0) = (1-p) \cdot f(-1) + p \cdot f(1) = (1-p) + p \cdot f(1) $$
The second key insight is that $ f(1) = f(0)^2$. Again I encourage you to think about this carefully to convince yourself that it is true. It basically holds because $p$ doesn't change based on the score differential. We can think of $ f(1) $ in two different ways: (1) by definition, it is the probability that Bob wins when the current score differential is $ 1 $ and (2) it is the probability that Bob wins two games in a row with score differential $0$. (2) holds because winning one game brings the score differential down from $ 1 $ to $ 0 $, and winning the second game brings it down from $ 0 $ to $ -1 $. Plugging in this newly derived knowledge to the formula above, we find:
$$ f(0) = (1-p) + p \cdot f(0)^2 $$
This is just a quadratic equation that we need to solve. To make it more clear that this is the case, we will let $ f(0) = x $, so we want to find the value of $ x $ such that
$$ x = (1-p) + p x^2 $$ $$-p x^2 + x + (p-1) = 0 $$
Using the quadratic formula, we find that $ x = \frac{p-1}{p} $ or $ x = 1 $. Of course $ x = 1 $ is the solution when $ p \leq 0.5 $, but $ \frac{p-1}{p} $ is the solution when $ p > 0.5 $. Thus the answer to the first question is $ f(0) = \frac{p-1}{p} $ and we can find the answer to the second question by setting $ f(0) = \frac{1}{2} $. This shows that when $ p = \frac{2}{3} $ the game is fair for both players.

I hope you enjoyed this problem, and if you have other solutions, feel free to post them in the comments section below!

Silahkan di kunjungi ya kawan-kawan 100% Memuaskan > Hoki anda ada di sini < Bandar Q Online Terpercaya dan Teraman di GUNUNGPOKER Link daftar : http://bandaraduq.com/Register.aspx?lang=id BBM : 56978317

SEMUA GAME HANYA PAKAI 1 USER ID : Poker, Domino QQ, Capsa Susun, Adu Q, Bandar Poker,

Segera daftarkan userid anda di GUNUNGPOKER Promo Terbaru dari GUNUNGPOKER - Minimal DEPOSIT & WITHDRAW Rp 20.000,- - Tersedia 7 game dalam 1 USER ID - BONUS Turnover 0.5% - BONUS Referral 20%

UNTUK INFORMASI SELANJUTNYA BISA HUB KAMI DI : LIVECHAT GUNUNGPOKER 24 JAM ONLINE Fanspage FB : @agengunungpoker Pin BB : 56978317 WA : +62812-7287-4416 LINE : gunungpokercsr1 WECHAT : gunungpokercsr1 YM : gunungpokercsr1@yahoo.com Agen domino BandarQ Domino 99 Domino QQ Agen Poker Bandar Poker Agen Judi QQ Judi Online Forum Judi Online hubungi kami di : Line : gunungpokercsr1 Bbm : 56978317 Wa : +6281272874416

Processors speeds are no longer growing at the rate we've grown accustomed to. Moore's law states that computers double in speed every 18 months. Moore's law is still alive and well, but we just need to find alternate ways to speed up computers. That's where multi-core programming comes into play. The idea behind it is that 2 heads are better than one and in the right situation 2 processors can work on the same problem to solve it twice as fast. Parallel programming is becoming increasingly important these days and there are many different flavors of it including distributed computing, shared memory computing, and GPU computing. Today I am going to focus on shared memory computing, or using multi-core computers rather than many single core computers. This blog post is intended to serve as a beginners guide to parallel programming with Java. It is recommended that the reader have some java experience and is familiar with some of the features of Java 8 (namely lambda exp…

If you have taken an introductory computer science course, you've probably seen the binary search algorithm - an algorithm to efficiently find the index of an item in a sorted array, if it exists. You might not have heard of interpolation search, however. Interpolation search is an alternative to binary search that utilizes information about the underlying distribution of data to be searched. By using this additional information, interpolation search can be as fast as $O(log(log(n)))$, where $n$ is the size of the array. In this post I am going to talk about two implementations of interpolation search. First, I will discuss the algorithm as described on Wikepedia, then I will describe my own version of the algorithm that has a better worst case time complexity than the first and performs better in practice than the traditional binary search and interpolation search algorithms.
The Basic Idea
Interpolation search models how humans search a dictionary better than a binary search, be…

Suppose you have a 2d numpy array and you want to remove duplicate rows (or columns). In this blog post, I'll show you a trick you can use to do this more efficiently than using np.unique(A, axis=0). This algorithm has time complexity $ O(\max(n \log{n}, n m)) $ for an $ n \times m $ matrix, and works almost surely. By "almost surely" I mean that it is a randomized algorithm that works correctly with probability $1$. To find the unique rows of a matrix $A$, the algorithm works by generating a random vector $x$ of real numbers, computing the dot product $ y = A x $, then analyzing the unique elements of $y$. The indices of unique elements in $y$ is the same as the unique row indices in $A$ with probability $1$. Below is an example to demonstrate how it works:

Free Game

ReplyDeleteSteam Keys

Free Steam Keys

Game Giveaway

Game Steam Giveaway

Free Steam Game Giveaway

Superb Article, visit mine at

ReplyDeleteAgen DominoAgen PokerAgen ReferralPoker Live

ReplyDeleteSilahkan di kunjungi ya kawan-kawan 100% Memuaskan

> Hoki anda ada di sini <

Bandar Q Online Terpercaya dan Teraman di GUNUNGPOKER

Link daftar : http://bandaraduq.com/Register.aspx?lang=id

BBM : 56978317

SEMUA GAME HANYA PAKAI 1 USER ID : Poker, Domino QQ, Capsa Susun, Adu Q, Bandar Poker,

Segera daftarkan userid anda di GUNUNGPOKER

Promo Terbaru dari GUNUNGPOKER

- Minimal DEPOSIT & WITHDRAW Rp 20.000,-

- Tersedia 7 game dalam 1 USER ID

- BONUS Turnover 0.5%

- BONUS Referral 20%

UNTUK INFORMASI SELANJUTNYA BISA HUB KAMI DI :

LIVECHAT GUNUNGPOKER 24 JAM ONLINE

Fanspage FB : @agengunungpoker

Pin BB : 56978317

WA : +62812-7287-4416

LINE : gunungpokercsr1

WECHAT : gunungpokercsr1

YM : gunungpokercsr1@yahoo.com

Agen domino

BandarQ

Domino 99

Domino QQ

Agen Poker

Bandar Poker

Agen Judi QQ

Judi Online

Forum Judi Online

hubungi kami di :

Line : gunungpokercsr1

Bbm : 56978317

Wa : +6281272874416