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

Analyzing Randomly Descending Sequences

Get link

Facebook

Twitter

Pinterest

Email

Other Apps

Finals week just ended for me so I'm hoping to post some new cool math problems in the next few days. In this blog post, I present a math problem that is very easy to understand what it is asking, but not so easy to solve. Regardless, I will present my solution, which yielded a very interesting result.

You construct a sequence \( k_1, k_2, ..., k_m \) by randomly picking an integer from the set \( 0 \leq k_1 < n \). After picking \( k_1 \), you repeat the process by picking \( k_2 \) randomly from \( 0 \leq k_2 < k_1 \) and repeat the process until you can no longer pick any numbers (when \( k_m = 0 \)). Find a function for \( f(n) \), where \( f(n) \) is the expected value of the length of this sequence.

If \( n = 3 \), then the possible sequences are \( \{ [0], [1,0], [2,0], [2,1,0] \} \), but these don't all occur with equal probability: \( P([0]) = \frac{1}{3}, P([1,0]) = \frac{1}{3}, P([2,0]) = \frac{1}{6}, P([2,1,0]) = \frac{1}{6} \). Using these probabilities, we can easily compute \( f(3) \):
$$
f(3) = \frac{1}{3} \cdot 1 + \Big(\frac{1}{3} + \frac{1}{6}\Big) \cdot 2 + \frac{1}{6} \cdot 3 = \frac{11}{6}
$$ By similar analysis, we can see \( f(0) = 0, f(1) = 1, \) and \( f(2) = \frac{3}{2} \). Do you recognize a pattern? I didn't see it right away, but let's keep going and see what we can come up with.

This problem is inherently recursive, and we can write a recurrence relation for \( f(n) \). The possible values for \( k_1 \) are \( k_1 \in \{ 0, 1, ..., n-1 \} \). In each case the problem reduces to \( f(k_1) \), but we must average the results over all the possibilities. Here is a recurrence relation for \( f(n) \):
$$
f(n) = 1 + \frac{1}{n} \sum_{k=0}^{n-1} f(k)
$$ In this equation, the \( +1 \) represents the cost of reducing the problem in size (when we choose \( k_1 \), that adds 1 item to our sequence). The summation is the average of the expected values all the possible sub problems that can arise from the current position. Let's rearrange the recurrence relation and try to make some simplifications.
$$
n (f(n) - 1) = \sum_{k=0}^{n-1} f(k) = f(n-1) + \sum_{k=0}^{n-2} f(k)
$$ Notice that we can also write \( f(n-1) \) in a similar manner.
$$
(n-1) (f(n-1) - 1) = \sum_{k=0}^{n-2} f(k)
$$ We can replace the summation in the top formula with the summation in the bottom formula to get a nice
recurrence relation for \( f(n) \) in terms of \( f(n-1) \).
$$
n (f(n) - 1) = f(n-1) + (n-1) (f(n-1) - 1)
$$ After some algebraic manipulation, we can see that
$$
f(n) = f(n-1) + \frac{1}{n}
$$ Additionally, we have the initial condition that \( f(0) = 0 \), so we have
$$
f(n) = \sum_{i=1}^n \frac{1}{i} = H_n
$$ This is the exact construction for the harmonic numbers! Although I was unable to answer the original question and find a function for \( f(n) \) in closed form, this is an equally exciting result.

In this post, I will discuss my findings in terms of an optimal strategy for Farkle , which is a dice game of chance. If you are unfamiliar with the game, I encourage you to skim the linked article so that you can better understand this blog post. All of my findings are based on sound mathematical methods and a computer program was used to determine the optimal strategy. Before I begin, let me first state the value of different dice rolls I assumed while developing the strategy. Each 1: 100 points Each 5: 50 points 3 1's: 1000 points 3 2's: 200 points ... 3 6's: 600 points 4 1's: 2000 points ... 4 6's 1200 points 5 1's 3000 points ... 5 6's 1800 points Straight 1-6 1500 points 3 Pairs (e.g., 22 33 44): 750 points Everything else is considered to be a Farkle (0 points). There are many variants to Farkle, but I like to play by this set of rules. The "game state" of Farkle roll can roughly be characterized by 2 values: the curre

A few weeks ago, I was using a Markov Chain as a model for a Project Euler problem, and I learned about how to use the transition matrix to find the expected number of steps to reach a certain state. In this post, I will derive the linear system that will help answer that question, and will work out specific an example using a 1-dimensional random walk as the model. Terminology Before I begin the derivation, let me define some terms. The transition matrix is an \( n \) by \( n \) matrix that describes how you can move from one state to the next. The rows of the transition matrix must always sum to 1. States can either be transient or absorbing . An absorbing state is one that cannot be left once reached (it transitions to itself with probability 1). A transient state is a state that is not an absorbing state. In many problems, it is of general interest to compute the expected number of steps to reach an absorbing state (from some start state). Derivation Let \( p_

In a lot of the recreational math and computer science problems I solve, I try to derive a recurrence relation that describes the situation. These recurrence relations pop up pretty often in counting problems (how many ways can you tile a 2xn grid with 2x1 tiles?) In some cases, I am unable to derive a recurrence relation directly from the problem statement, but still suspect that there exists some recurrence relation. In these cases, I end up solving the problem usin g brute force methods for small input sizes and analyzing/extrapolating the pattern. However, when the relation is obscure, it becomes hard to find. In order to make this process easier in the future, I created a program that can automatically find recurrence relations for arbitrary integer sequences. To use it, simply type in the first few terms of a sequence you are interested in, and it will try to find a recurrence relation for that sequence. There are some constraints on the allowable inputs/outputs which I di

## Comments

## Post a Comment