what is the probability that a sequence is increasing?

Question

I am preparing for my exams in algorithms & probabilty. For the exam preparation, we have been given this exercise. I couldn't solve this, even with the master solution given to us.

In a casino in Monte Carlo, you play at a very peculiar machine. The machine has $n$ wheels, each with $k$ possible values (not necessarily distinct). The wheels may be different from each other, that is it does not necessarily hold that every wheel has the same $k$ values on it.

When you activate the machine, each wheels lands in one of its $k$ possible values chosen uniformly at random and independently of all other wheels. You win a jackpot if the $n$ chosen values form an increasing sequence $x_1 \leq x_2 \leq \dots \leq x_n$ (the sequence does not need to be strictly increasing). You want to compute your chances of winning a jackpot.

---

My idea would have been to define the events: $A_i = ``x_{i-1} \leq x_i"$. So I have to calculate $P[A_2 \& \dots \&A_N]$. I'm not sure but $P[A_i]$ must be: $P[A_i] = (k-z)/k * (1/k)$ ($z$ is the number that has been taken in $x_{i-1}$). But how do I calculate this probability? Does any one also have an idea how to implement it in Java? The master solution uses recursion, but I didn't get that part.

We have been given numbers to solve this problem: For example: we have two wheels and the number of different values each wheel has is 3.

Wheel 1 has the values: 1, 2, 3 Wheel 2 has the values: 1, 2, 3

The probability of an increasing sequence is 2/3

Another Example would be: we have two wheels, $k = 2$ wheel 1 = 1, 2 wheel 2 = 2, 2

probability is 1 :)

Thank you!!

Answer 1

This is really more of a programming question than a math question, because the math is simple, and the programming is more challenging. Anyway, since all sequences are equally like (provided we count sequences when different instances of a repeated number come as distinct), the probability is just the number of increasing sequences divided by the number of possible sequences. We know the latter is $k^n,$ so the problem is to count the increasing sequences, and that requires a computer program.

Suppose we have three wheels with the numbers ${1,4,6},{2,8, 14},{4, 12, 27}$ Look at the last wheel. If it comes up $4$, then the second wheel must have come up $2$, so we need to know the number of increasing sequences on the first $2$ wheels end in $2$. If the last wheel comes up $12,$ then the second wheel has to come up $2$ or $8$ so we need to know how many $2-$wheel sequences end in $2$ and how many end in $8$. If the last wheel comes up $14$ the second wheel can come up any number, so that we need to know the number of all two-wheel sequences.

This is the idea of the recursion. We can solve the problem for $n$ wheels by reducing it to the problem with $n-1$ wheels. Recursion is a nice way to think about it, or to write down pseudocode, but it's not a good way to solve this particular problem. If you go through my, example, you see that we need to compute the number of two-wheel sequences that end in $2$ three times. As $n$ and $k$ get bigger, this will explode.

Let's assume that the data are given in an $n\times k$ array called say wheel so that wheel[w][j] is the $j$th number on wheel $w$. Then you want to compute another array $n\times k$ array called increasing so that increasing[w][j] is the number of $w+1-$wheel sequences that end in wheel[w][j]. It will be convenient if the rows of the array are sorted.

The simplest way to do the calculations, and the one I recommend, is to fill out the increasing array column-by-column. We know that increasing[w][0]=1 for every w. Now calculate the second column (the values of increasing[w][1] and so on. Now the number of increasing sequences is just the sum of column $n-1$ of increasing.

Answer 2

This looks like a job for dynamic programming.

Compute for each relevant $(n,x)$ the number of outcomes of the first $n$ wheels that is non-decreasing and ends with $x$.

Then divide by $k^n$.