0
$\begingroup$

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

$\endgroup$
4
  • 2
    $\begingroup$ 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 $\endgroup$
    – Bram28
    Jul 31, 2018 at 19:25
  • $\begingroup$ 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 $\endgroup$
    – scalpula
    Jul 31, 2018 at 19:32
  • $\begingroup$ 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) $\endgroup$ Jul 31, 2018 at 19:36
  • 1
    $\begingroup$ @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. $\endgroup$ Jul 31, 2018 at 19:40

2 Answers 2

0
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ just a passing question: Is the array notation applicable to any programming language or it restricts to a certain domain of languages? $\endgroup$ Jul 31, 2018 at 21:31
  • $\begingroup$ 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. $\endgroup$
    – saulspatz
    Jul 31, 2018 at 21:36
  • $\begingroup$ Thank you very much! It now makes sense to me :) $\endgroup$
    – scalpula
    Aug 3, 2018 at 18:10
  • $\begingroup$ It was my pleasure. $\endgroup$
    – saulspatz
    Aug 3, 2018 at 18:11
0
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Hi Hening Makholm :) I don't understand what you really mean. Could you please explain it to me. Thank you! :) $\endgroup$
    – scalpula
    Jul 31, 2018 at 19:44
  • $\begingroup$ 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. $\endgroup$ Jul 31, 2018 at 21:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.