Ερώτηση

Κάθε φορά που επισκέπτεστε ένα εστιατόριο επιλέγετε ένα από τα \(N\) πιάτα του μενού τυχαία. Ποια είναι η μέση τιμή του χρόνου που θα σας πάρει να δοκιμάσετε όλα τα πιάτα;

Απάντηση

Το πλήθος των διαφορετικών πιάτων που έχουμε δοκιμάσει μετά από \(n\) επισκέψεις είναι μια μαρκοβιανή αλυσίδα με πιθανότητες μετάβασης

\[p_{k,k+1}=\frac{N-k}{N}\] και \[p_{k,k} = \frac{k}{N}\] για \(k=0,1,2,\dots,N.\)

Αυτό συμβαίνει γιατί αν έχουμε ήδη δοκιμάσει \(k\) πιάτα η πιθανότητα να επιλέξουμε ένα από αυτά στην παραγγελία μας είναι: \(\frac{k}{N}.\)

Αν \(Τ= \inf\{k \geq 0:X_{k}=N \}\) και \(g(x=\mathbb{E}[T])\) η \(g(x)\) λύνει το πρόβλημα:

\[\left\{\begin{array}{lr} g(N)=0\\ g(k)=1 + \frac{k}{N}g(k)+\frac{N-k}{N}g(k+1)\\ \end{array}\right\}\]

Η τελευταία εξίσωση γράφεται και ως:

\[ \begin{align*} g(k)&=1 + \frac{k}{N}g(k)+\frac{N-k}{N}g(k+1) \\ g(k)- \frac{k}{N}g(k)&=1 +\frac{N-k}{N}g(k+1) \\ g(k)(1- \frac{k}{N})&=1 +\frac{N-k}{N}g(k+1) \\ g(k) &= \frac{1}{1-\frac{k}{N}} + \frac{\frac{N-k}{N} g(k+1) }{1-\frac{k}{N}}\\ g(k) &= \frac{\frac{1}{1}}{\frac{N}{N} -\frac{k}{N}} + \frac{\frac{N-k}{N} g(k+1) }{\frac{N}{N}-\frac{k}{N}}\\ g(k) &= \frac{\frac{1}{1}}{\frac{N-k}{N}} + \frac{\frac{N-k}{N} g(k+1) }{\frac{N-k}{N}}\\ g(k) &= \frac{N}{N-k} + \frac{N(N-k)g(k+1)}{N(N-k)}\\ g(k) &= \frac{N}{N-k} + g(k+1)\\ g(k) - g(k+1) &= \frac{N}{N-k} \\ \end{align*} \]

Αθροίζοντας τις παραπάνω σχέσεις για \(k=0,1,2,\dots,N-1\) λαμβάνουμε:

\[g(0)-g(N)=N\sum_{k=0}^{N-1}\frac{1}{N-k} \Rightarrow g(0)=N\sum_{k=1}^{N}\frac{1}{k}\] Τώρα αν απομονώσουμε τον όρο :

\(\sum_{k=1}^{N}\frac{1}{k}\) βλέπουμε οτι ειναι μια αρμονική σειρά όπου χρησιμοποιώντας το integral τεστ έχουμε :

\[\int_{1}^{x} \frac{1}{k} dk = \ln(k)-\ln(1)=\ln(k)\] Χρησιμοποιόντας ομως την ασυμπτωτική των αρμονικών σειρων λαμβάνουμε οτι \[{\displaystyle \operatorname {E} (T)=n\log n+\gamma n+{\frac {1}{2}}+O(1/n),}\] όπου \(\gamma \approx 0.5772156649\) η σταθερά των Euler–Mascheroni.

Ας υποθέσουμε τωρα πως ενα εστιατόριο έχει ένα μενού με 20 πιάτα.Ο αριθμός των ημερών που πρεπεί να περάσουν μέχρι να γευτούμε όλα τα πίατα ειναι περίπου 72 μέρες.

N =20 
gamma  = 0.5772156649
N * log(N) + gamma * N + 0.5
## [1] 71.95896

Θέλοντας να προσόμοιώσουμε την παραπανω αλυσίδα Markov έχουμε πολυ κοντινά αποτελέσματα.

nits <- 1000 #simulate the problem 1000 times
results = integer(length = nits)
N = 20 # number of dishes 
for (i in 1:nits){
  dishes = 1:N
  tasted = rep(0, N) 
  count = 0
  while(sum(tasted) < N){
    tasted[sample(dishes, size = 1)] = 1
    count = count + 1
  } 
  results[i] = count
}
#results
mean(results)
## [1] 72.894