Gambler’s Ruin (Random Walk) Probleminin R ile Çözümü

Herkese Selam,

Gambler’s Ruin Problemi, yöneylem alanının araştırma konusundan biridir. Problemin hikayesi şöyledir;

Bir kumar oyuncusunun p olasılıkla 1 dolar kazandığı 1-p olasılıkla da 1 dolar kaybettiği bir oyun düşünelim. Oyuncu elinde X dolar ile bu oyunu oynamaya başlasın. Oyuncunun elindeki para N (N>X) dolara çıkarana kadar veya elinde hiç para kalmadığı duruma kadar bu oyunu oynayacaktır. Oyuncunun kazanmayı amaçladığı N değerine ulaşana kadar oyunu bırakmayacağını bildiğimize göre , oyuncunun arzu ettiği paraya (N) ulaşma ihtimali nedir?

Yukarıda hikayesini anlattığım problem, literatürde “Gambler’s Ruin” veya “Random Walk ” olarak bilinir. Bu yazıda bu problemi farklı ayarlar ile R programlama dili ile simüle edip, oyun sonuçlarının farklı ayarlar ile nasıl değiştiğini inceleyeceğim.

Bu simülasyonu yaparken kullanacağım parametreler;

  • Oyuncunun, oyuna girerken elinde bulundurduğu para.
  • Oyunun biteceği alt para limiti.
  • Oyunun biteceği üst para limiti.
  • Oyuncunun 1 dolar kazandığı durumun olasılığı. (p)
  • Yukarıda belirttiğimiz parametreler ile deneyi tekrarlama sayımız (n).

Şimdi tanımladığımız parametrelerden bir kaç senaryo üretelim ve simülasyonu bu senaryolar ile gerçekleştirelim.

Senaryo 1 :  

  • Oyuncunun, oyuna girerken elinde bulundurduğu para : $6
  • Oyunun biteceği alt para limiti: $2
  • Oyunun biteceği üst para limiti: $10
  • Oyuncunun 1 dolar kazandığı durumun olasılığı:  (p: 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9) (Her olasılık değeri için oyunu ayrı ayrı oynayacağız)
  • Deneyi tekrarlama sayımız n: 100

Senaryo 2 :  

  • Oyuncunun, oyuna girerken elinde bulundurduğu para : $7
  • Oyunun biteceği alt para limiti: $1
  • Oyunun biteceği üst para limiti: $10
  • Oyuncunun 1 dolar kazandığı durumun olasılığı:  (p: 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9) (Her olasılık değeri için oyunu ayrı ayrı oynayacağız)
  • Deneyi tekrarlama sayımız n: 100

Senaryo 3 :  

  • Oyuncunun, oyuna girerken elinde bulundurduğu para : $10
  • Oyunun biteceği alt para limiti: $3
  • Oyunun biteceği üst para limiti: $20
  • Oyuncunun 1 dolar kazandığı durumun olasılığı:  (p: 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9) (Her olasılık değeri için oyunu ayrı ayrı oynayacağız)
  • Deneyi tekrarlama sayımız: n: 100

Yukarıda tariflediğimiz 3 temel senaryomuz var. Ancak farklı olasılık değerleri için (9) aynı senaryoyu tekrar tekrar çalıştıracağımız için, her bir senaryo toplamda 9 kez çalışacak.  Gün sonunda 9X3 = 27 farklı senaryo çalıştıracağız.

Şimdi simülasyonu yapacak R koduna geçelim. Bu simülasyonun tamamını gerçeklemek için toplam 5 fonksiyon yazacağım. Bunlar;

ReadInstances: Bu fonksiyon ile oyuncunun elindeki para miktarını ve oyunun hangi üst ve alt limitte biteceğini .csv dosyaları aracılığı ile okuma işlemini yapacağım.

Örnek dosya formatı (,Lower Limit,Upper Limit):  6,2,10

GamblerRuin: Oyunu, verilen parametreler ile 1 kez oynayan ve sonucu döndüren fonksiyon (win/loss).

Simulator: GamblerRuin fonksiyonunu tüm olası senaryoların sayısı kadar çalıştıran ve sonuçları kayıt edecek fonksiyon.

ExportResults: Simulasyon sonuçlarını dosyaya yazan fonksiyon.

Analyzer:  Dosyaya yazılan simülasyon sonuçlarını okuyup, bir tahmin ve bu tahmine bağlı hata hesaplayan fonksiyon.

Error = |Pactual-Pestimated|/Pactual

Şimdi R’da kod yazma kısmına geçebiliriz.

İlk etapta değişkenlerimiz initialize ediyoruz.

#Initializing Parameters
instancesFolder = "ProblemInstances"
options(warn = -1)
options(max.print = 100000000)
probabilities = c(0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9)
n = c(100)

Şimdi fonksiyonların yazımımına başlayabiliriz.

ReadInstances

# Function ReadInstances(input FilesFolderPaths)
# Return: DataFrame, each record in seperate files
ReadInstances <- function(instancesFolder) {
  mydata = data.frame()
  files <- as.list(list.files(path = instancesFolder))
  for (i in 1:length(files))
  {
     line <-
          read.csv(
                   paste("ProblemInstances", .Platform$file.sep, files[i], sep = ""),
                   header = F,
                   sep = ",",
                   quote = ""
                  )
        line$UL > line$currentState && line$UL > line$LL)
    {
      mydata = rbind(mydata, line)
    }
  }
  colnames(mydata) = c('currentState', 'LL', 'UL', 'fileName')
  return(as.data.frame(mydata))
}

GamblerRuin: Bu fonksiyonda oyunu bir bernoulli trial olarak gerçekleştiriyoruz. Bu olayı gerçeklemek için rbinom fonksiyonundan faydalanıyoruz.

# Function GamblerRuin(inputs currentState, UL, LL, p)
# Return: string, game result win or lose
GamblerRuin <- function(currentState, UL, LL, p) { while (currentState > LL && currentState < UL)
  {
    coin = rbinom(1, 1, p)
    
    if (coin == 1)
    {
      currentState = currentState + 1
    }
    else
    {
      currentState = currentState - 1
    }
  }
  
  if (currentState == UL)
  {
    return("win")
  }
  else  
  {
    return("lose")
  }
}

Simulator

# Function Simulator(inputs problemInstances, probabilities, n)
# Saving Scenarios and SimulationResults to Files
# Return: data frame, results of all possible scenarios (resultTable)
Simulator <- function(problemInstances, probabilities, n) {
 set.seed(0)
 resultTable = data.frame()
 scenarioID = 0
 scenarioTable = data.frame()
 
 for (instance in 1:nrow(problemInstances)) {
 for (prob in 1:as.integer(length(probabilities)))
 {
 for (j in 1:as.integer(length(n)))
 {
 scenarioID = scenarioID + 1
 scenrow = data.frame(problemInstances[instance,]$fileName,
 scenarioID,
 probabilities[prob],
 n[j])
 scenarioTable = rbind(scenarioTable, scenrow)
 
 for (k in 1:n[j])
 {
 gameResult = GamblerRuin(
 problemInstances[instance, ]$currentState,
 problemInstances[instance, ]$UL,
 problemInstances[instance, ]$LL,
 probabilities[prob]
 )
 row = data.frame(problemInstances[instance, ]$fileName,
 scenarioID,
 probabilities[prob],
 n[j],
 k,
 gameResult)
 resultTable = rbind(resultTable, row)
 }
 }
 }
 scenarioID = 0
 }
 
 
 colnames(scenarioTable) = c('instanceFileName', 'ScenarioID', 'p', 'n')
 #Save Scenario to File
 ExportResults(scenarioTable, "ScenarioFormatted.txt", 2)
 ExportResults(scenarioTable, "Scenario.txt", 1)
 
 colnames(resultTable) = c('instanceFileName',
 'ScenarioID',
 'p',
 'n',
 'ReplicationID',
 'Result')
 
 
 SimulationResults <-
 subset(resultTable,
 select = c(instanceFileName, ScenarioID, ReplicationID, Result))
 #Save SimulationResults to File
 ExportResults(SimulationResults, "SimulationResultsFormatted.txt", 2)
 ExportResults(SimulationResults, "SimulationResults.txt", 1)
 
 
 return(resultTable)
}

ExportResults

# Function ExportResults(inputs dataFrame, fileName, type)
# Saving to file (data and filename are parameters)
#type1: standart csv output, type2: formatted output
ExportResults <- function(dataFrame, fileName, type)
{
  #type1: standart csv output
  if (type == 1)
  {
    write.table(
      dataFrame,
      file = fileName,
      append = FALSE,
      quote = TRUE,
      sep = ",",
      eol = "\n",
      na = "NA",
      dec = ".",
      row.names = FALSE,
      col.names = TRUE,
      qmethod = c("escape", "double"),
      fileEncoding = ""
    )
    
  }
  else
    #type2: formatted output
  {
    capture.output(print(dataFrame, print.gap = 3, row.names = FALSE), file =
                     fileName)
  }
}

ReadFilesFromCsv <- function(fileName)
{
  myData = read.csv(fileName,
                    header = T,
                    sep = ",",
                    quote = "")
  return(myData)
}

Analyzer

# Function Analyzer()
# Read recorded files and Analysis Estimation Errors
# Saving and Plotting Result of Analysis
Analyzer <- function() {
  #Read Simulation Result
  simulationResults = ReadFilesFromCsv("SimulationResults.txt")
  
  #converting formatted data frame
  simResults = (data.frame(
    table(
      simulationResults$X.instanceFileName,
      simulationResults$X.ScenarioID,
      simulationResults$X.Result
    )
  ))
  colnames(simResults) = c('instanceFileName', 'ScenarioID', 'Result', 'Count')
  
  #Seprating "win" and "lose" records to calculating p value.(using external libarary dplyr)
  library(dplyr)
  simResults_win  =  filter(simResults, Result == as.character('"win"'))
  simResults_lose =  filter(simResults, Result == as.character('"lose"'))
  
  #Join 2 data frame and calculate p_estimated value (using sqldf external libarary)
  library(sqldf)
  simResultsWithPestimated <-
    sqldf(
      "SELECT instanceFileName,ScenarioID,
      round((cast(simResults_win.Count as real)/(simResults_lose.Count+simResults_win.Count)),3) p_estimated
      FROM simResults_win
      JOIN simResults_lose USING(instanceFileName,ScenarioID)"
    )
  
  
  #Read Scenario Result
  scenarios = ReadFilesFromCsv("Scenario.txt")
  
  #changing column name
  colnames(scenarios) = c('instanceFileName', 'ScenarioID', 'p', 'n')
  
  
  #Caclulation Percentage Error using sqldf external libarary
  library(sqldf)
  estimationErrors = sqldf(
    "SELECT instanceFileName,ScenarioID,sc.p p_actual, sim.p_estimated p_estimated,
    round(abs(cast(sc.p - sim.p_estimated as real)/ sc.p),3) PercentageError
    FROM scenarios sc
    JOIN simResultsWithPestimated sim USING(instanceFileName,ScenarioID)"
  )
  
  #dump out staging and final data frames
  ExportResults(simResultsWithPestimated,
                "SimulationResultWithPestimated.txt",
                2)
  ExportResults(estimationErrors, "estimationErrors.txt", 2)
  
  #plotting estimationErrors vector
  countOfPercentageError <- table(estimationErrors$PercentageError)
  barplot(
    countOfPercentageError,
    main = "Percentage Distribution",
    xlab = "ErrorRates",
    ylab = "Number of Counts"
  )
  
}

Tüm fonksiyonlarımızın yazımını tamamladık. Şimdi simülasyonu çalıştıracak kod parçasını yazalım ve sonuçları inceleyelim.

instances = ReadInstances(instancesFolder)
resultTable = Simulator(instances, probabilities, n)
Analyzer()
ExportResults(resultTable, 'ResultTable.txt', 2)

Kodumuz çalıştıktan sonra ürettiğimiz çıktılardan biri hangi senaryoların çalıştığı.

Üretilen bir diğer çıktı, oynanan oyunların sonuçları(sadece örnek bir küme listelenmiştir.)

Ürettilen son çıktı ise her bir senaryo için hesaplanan tahmin değerleri.

 

Aşağıdaki grafikte ise hesaplanan hatanın dağılımını görmekteyiz.

Advertisements

About ... from Emrah METE

Bilgisayar Mühendisi
This entry was posted in Root, Uncategorized and tagged , , , , , , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.