Category Archives: Functional programming

The birthday problem and tail recursion

The birthday problem or probability paradox concerns the probability that a group of n people all have different birthdays, see for instance p. 15 of the book “Statistical modelling and computation” by Dirk Kroese and Joshua Chan. The purpose of this blog post is to exemplify how tail recursion can be used to avoid mutability in the context of a simple statistical computation, thus switching from the imperative to the functional programming paradigm.


Short recap on the solution to the birthday problem

As a succinct recap of the solution to the birthday problem, let A_k denote the event that the k first people have different birthdays for k=1,2,\dots, n. Notice that A_{k}\subseteq A_{k-1}, whence A_n=\underset{k=1}{\overset{n}{\bigcap}}A_k. The probability that all n people have different birthdays is then \mbox{P}(A_n)=\mbox{P}(\underset{k=1}{\overset{n}{\bigcap}}A_k). By application of the product rule of probability,

\mbox{P}(A_n)=\mbox{P}(A_1)\displaystyle\prod_{k=2}^{n}\mbox{P}(A_k|A_{k-1}).

Given that the first k-1 people have different birthdays, the first k people have different birthdays if and only if the birthday of the k-th person is chosen from the remaining 365-(k-1) birthdays. So,

\mbox{P}(A_k|A_{k-1})=\displaystyle\frac{365-k+1}{365}.

Obviously, \mbox{P}(A_1)=1, which leads to

\mbox{P}(A_n)=\displaystyle\frac{1}{365^{n-1}} \prod_{k=2}^{n}(365-k+1).


Computing the probability of different birthdays via an iterative function

To compute the probability \mbox{P}(A_n) that all n people have distinct birthdays as a function of n, consider the following iterative function in R:

UniqueBirthdayProb <- function(n) {
  p <- 1
  for (k in 1:n) {
    p <- p * (365 - k + 1) / 365
  }
  return(p)
}

The function call

UniqueBirthdayProb(23)

gives a probability of 0.4927028, which means that the probability of n=23 people not exhibiting a duplicate birthday is less than 50\%.

The following snippet computes and plots \mbox{P}(A_n) for n=1,2,\dots,70:

nseq <- 1:70
pseq <- sapply(nseq, UniqueBirthdayProb)

plot(
  nseq, pseq,
  type="o", pch="*", ylim=c(0, 1),
  xlab="n", ylab=expression('P(A'[n]*')'),
  main="Probability of distinct birthdays"
)

The resulting plot is shown below:birthday_problem_solution


Computing the probability of different birthdays via a recursive function

The following R function computes \mbox{P}(A_n) recursively:

RecUniqueBirthdayProb <- function(n) {
  if (n == 1) {
    return(1)
  } else {
    return(RecUniqueBirthdayProb(n - 1) * (365 - n + 1) / 365)
  }
}

Mutability has been avoided in that the state of the local variable p in the body of UniqueBirthdayProb(n) is not altered. The function RecUniqueBirthdayProb(n) calls itself recursively, and therefore avoids the need for a local variable. A downside of the recursive function calls in RecUniqueBirthdayProb(n) is that the stack frame is filled for increasing values of the input argument n.


Computing the probability of different birthdays via a tail-recursive function

Tail recursion reduces the number of recursive calls. This is how to define a tail-recursive function in R to compute \mbox{P}(A_n):

TailRecUniqueBirthdayProb <- function(n) {
  loop <- function(acc, n) {
    if (n == 1) {
      return(acc)
    } else {
      return(loop(acc * (365 - n + 1) / 365, n - 1))
    }
  }
  loop(1, n)
}

A closure loop(acc, n) is defined inside the tail-recursive function TailRecUniqueBirthdayProb(n). The number of recursive calls is reduced via the accumulator acc, which is the first input argument to loop(acc, n).


A comparison of stack frames between the three functions

To compare the iterative, recursive and tail-recursive functions in terms of their stack demands, the trace() R function is called upon each of the three functions, yielding the following output:

> trace(UniqueBirthdayProb)
> UniqueBirthdayProb(10)
trace: UniqueBirthdayProb(10)
[1] 0.8830518
> untrace(UniqueBirthdayProb)
>
> trace(RecUniqueBirthdayProb)
> RecUniqueBirthdayProb(10)
trace: RecUniqueBirthdayProb(10)
trace: RecUniqueBirthdayProb
trace: RecUniqueBirthdayProb
trace: RecUniqueBirthdayProb
trace: RecUniqueBirthdayProb
trace: RecUniqueBirthdayProb
trace: RecUniqueBirthdayProb
trace: RecUniqueBirthdayProb
trace: RecUniqueBirthdayProb
trace: RecUniqueBirthdayProb
[1] 0.8830518
> untrace(RecUniqueBirthdayProb)
>
> trace(TailRecUniqueBirthdayProb)
> TailRecUniqueBirthdayProb(10)
trace: TailRecUniqueBirthdayProb(10)
[1] 0.8830518
> untrace(TailRecUniqueBirthdayProb)

It is clear from the output that RecUniqueBirthdayProb(n) requires more recursive function calls than TailRecUniqueBirthdayProb(n). Strictly speaking, and despite the reduction in the number of recursive function calls, R does not support tail elimination. The focus of this post is on the concept of tail recursion and how it can be applied in a simple statistical problem, not on the specifics of tail elimination in R. The choice of programming language in this post has been made on pedagogical and not on performance grounds.