Wikipedia:Reference desk/Archives/Mathematics/2014 November 30

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

November 30

Permutations of N unique numbers subject to constraints

When V = N - 1, the answer isn't N - 1 but the V th triangular number. The iteration is shown in the material of sequence A130534 in OEIS. X(0, 0) = 1, X(N, V) = 0 if V > N, X(N, V) = X(N - 1, V - 1) + (N - 1) * X(N - 1, V) →86.171.209.142 (talk) 21:26, 30 November 2014 (UTC)

Thank you so much! WinterWall (talk) 23:58, 30 November 2014 (UTC)

Probability question involving simulations of picking balls from a bag

I’m working on a chemistry problem, which essentially translates to finding the answer to a related probability problem. However, my knowledge in probability is very limited and I'd be grateful if someone could help me out with it. The following is the problem:-

Suppose I have a bag containing $70$ red balls and $30$ blue balls. For the purpose of illustration, let’s call them $R$s (red balls) and $B$s (blue balls). Now, I am going to pick one ball at a time from this bag, without replacement. I define a run to be a sequence of consecutive $R$s (or alternately, $B$s) picked, along with the first $B$ (or $R$) that is picked. And I define a red (or blue) run length to be the number of consecutive $R$s (or $B$s) I pick in a run, before I encounter a $B$ (or $R$) or until the number of balls run out.

As examples, $RRRRRRB$ is a run (for simplicity, let me denote it by $R_{6}$ in shorthand) with red run length $6$, $RB$ is a run (denoted by $R_{1}$) with red run length $1$, $BBBR$ is a run (denoted by $B_{3}$) with blue run length $3$.

In each simulation, I keep doing runs until all the $100$ balls are picked out (since the balls are picked without replacement, the number of runs and the red/blue run lengths are both finite).

Let’s look at a typical simulation of ball-picking: $R_{50}R_{10}B_{28}R_{9}$. In this simulation, there are $4$ runs. The first run consists of $50$ consecutive red balls, until a blue ball is encountered. The second run consists of $10$ consecutive red balls until a ball is encountered. The third run consists of $28$ consecutive blue balls until a red ball is encountered. And the last run consists of $9$ consecutive red balls, and the simulation ends as there are no more balls to be picked.

It is easy to see that the minimum possible number of runs is $2$ (attained by $R_{70}$ followed by $B_{29}$, or $B_{30}$ followed by $R_{69}$) and the maximum possible number of runs is $31$ (attained by $R_{1}$ $30$ times followed by $R_{40}$, or $B_{1}$ $30$ times followed by $R_{70}$).

Also, the maximum possible value of red run length is $70$ and that of blue run length is $30$.

Now, I’m interested in knowing the probability distribution of the red and blue run lengths. For this, I believe that I must first find the expected value of the number of runs in a simulation. But I’m not sure how to proceed from here. So to sum up, the following are my questions:-

$1$. How do I find the expected value of the number of runs in a simulation?

$2$. For that expected value, how do I calculate the probability distribution of red and blue run lengths?

--Jobsism10 (talk) 10:29, 30 November 2014 (UTC)

I don't think your suggested method of first finding the expectation of total number of runs, then use that to find the value for each type of run, will work.

Instead, I'd define $f(b,r,X)$ as the expected number of times that run X will appear in a simulation with b blue balls and r red balls. Then you have:

$f(b,r,R_{i})={\frac {(b+r-i-1)!}{(b+r)!(r-i)!(b-1)!}}+\sum _{j=1}^{r}{\frac {(b+r-j-1)!}{(b+r)!(r-j)!(b-1)!}}f(b-1,r-j,R_{i})+\sum _{j=1}^{b}{\frac {(b+r-j-1)!}{(b+r)!(r-1)!(b-j)!}}f(b-j,r-1,R_{i})$

With some edge cases, and likewise for blue runs. Then I'd solve this using recursion (with memoization).

If you then want the expected number of runs, you can sum up these values over all kinds of runs.

(I haven't spent a lot of time verifying the above so there could be errors.) -- Meni Rosenfeld (talk) 15:21, 30 November 2014 (UTC)