# what is the probability that a sequence is increasing?

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!!

• If the wheels can have different numbers, and you don't know what the numbers are that are on the wheels, I don;t see how you could figure this out ... or at least not how you could compute a concrete value ... or even a closed formula ... for example, what if there are 2 wheels and wheel 1 only has the number 1, and wheel 2 only the number 2 .. then the probability is 1 ... but if wheel 1 only has a 2 and wheel 2 only a 1, then the probability is 0 Jul 31, 2018 at 19:25
• I totally forgot to mention that. We have been given numbers for that, it's programming task :). For example the num of wheels = 2. The number of different values each wheel has = 3. The first wheel has the values: 1, 2, 3 and the second wheel has the values 1, 2, 3. Then the probability of an increasing sequence is 2/3 Jul 31, 2018 at 19:32
• So you better put those numbers in the question. What about the cases with more wheels/numbers? What else do you know? You need to provide the whole data or the problem will be unsolvable (or solved in a too complicated way) Jul 31, 2018 at 19:36
• @RolazaroAzeveires: If it's a programming task, he hasn't been given the numbers yet -- he's expected to write a program that will be given the numbers. Jul 31, 2018 at 19:40

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.

• just a passing question: Is the array notation applicable to any programming language or it restricts to a certain domain of languages? Jul 31, 2018 at 21:31
• Well, C used this notation, and C has had a great influence. So languages derived from C all use this. Not all languages use this, I'm certain. LISP doesn't, so far as I know, for example. Jul 31, 2018 at 21:36
• Thank you very much! It now makes sense to me :) Aug 3, 2018 at 18:10
• It was my pleasure. Aug 3, 2018 at 18:11

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$.

• Hi Hening Makholm :) I don't understand what you really mean. Could you please explain it to me. Thank you! :) Jul 31, 2018 at 19:44
• For each relevant relation, you should compute the # of outcomes of the first n wheels being non decreasing and then ending with x. You should then divide by k to the n. I believe the idea is "outcomes with the desired property divided by all possible outcomes" so as to obtain the probability. Jul 31, 2018 at 21:28