Probability that the row in the table contain only one bit one?

Question

I am an electrical engineer that is currently working with an $m \times n$ matrix that only contains bit 0 and bit 1 in its cell. Assuming that bit 0 and bit 1 can appear in a cell with probability $p$ and $q$ respectively, where $p+q=1$. Also, assume that the probability of 1 and 0 in each cell is independent of any other cell.

1/ How can I evaluate the probability that a row contain only one bit 1 ?

For example, row 1, row 2, and final row contain only one bit 1

2/ On average, how many row will contain only one bit 1 ?

In my application, there is a row dropping action that can be describe as follows:

Starting at the row that contain only bit one (row 5) and begin to look up and look down (blue arrow), if we see bit 1 above (same column) or bit 1 right below it (same column) then we will initiate a drop row action for the corresponding row. Note that I have marked the bit 1 above and bit 1 below in a blue rectangular cell. So, in total 4 rows will be dropped. That is row 1, 2,7 and 8.

3/ On average, how many row will be dropped ?

I have a guts feeling that this may have something to do with the binomial distribution or geometric distribution but cannot get me head around it. Please help me with this ?

Edit for clarity:

1/ For question 3, it is possible that there are many rows that contains one bit 1.

2/ For question 3, row that contain one bit 1 will never be dropped !

Thank you for your enthusiasm !

Answer 1

First question

Let $A\in\mathcal{M}_{m\times n}$ be a matrix with $0,1$ entries. Then we define the random variable: $R_i$ = number of 1 in the $i$-th row. It is straigthforward to note that $R_i\sim B(n,q)$ for all $i\in\{1,\dots,m\}$ (here $B(n,q)$ is a binomial distribution of parameters $n$,$q$).

This implies that $P(R_i = 1) = \binom{n}{1}qp^{n-1}$ which solves the first question.

Second question

We define the random variable $R'$ which counts the number of rows with only one entry equal to 1. Then $R'\sim B(m,P(R_i = 1)) \sim B(m,\binom{n}{1}q(1-p)^{n-1})$ which has expcted value the product of its parameters:

$$ \mathbb{E}(R') = m\binom{n}{1}qp^{n-1} $$

Third question

We first find the first row such that it contains only a single 1 and it is in the first spot. Define $W_1$ the number of rows with these conditions. The probability for a row that there is a single and only 1 in the first spot is $qp^{n-1}$, then $W_1\sim B(m,qp^{n-1})$. We select one among them (not necessarely the first, it's really the same) and we do the drop action. We eliminate a number $E_1$ of rows, which is the number of all the $m-W_1$ rows with the first entry equal to 1. The probability for a row to have the first entry equal to 1 is exactly $q$, so $E_1\sim B(m-W_1,q)$.

We do the same process for the rows with the property that the second entry is 1, and that there is only a single 1 in it. $W_2\sim B(m-W_1-E_1,qp^{n-1})$ and we eliminate $E_2\sim B(m-W_2-W_1-E_1,q)$.

In general: $$W_k\sim B(m-\sum_{i = 1}^{k-1}(E_i+W_i),qp^{n-1})$$ and $$ E_k\sim B(m-W_k-\sum_{i = 1}^{k-1}(E_i+W_i),q) $$

Now the idea is to compute $\mathbb{E}(\sum_{k = 1}^{n}E_k) = \sum_{k = 1}^{n}\mathbb{E}(E_k)$, where $n$ is the number of columns of the matrix $A$.

I'll finish to write later

Answer 2

Question 1 & 2

(Kept short, as there is already an excellent answer.) The amount $R$ of ones in a row is binomially $B(n,q)$-distributed, so the probability for a one-1-row is $\binom n1qp^{n-1} = nqp^{n-1}$. Since there are $m$ rows, the expected amount is $m$ times this probability, $nmqp^{n-1}$.

Question 3

The trick for calculating the expected amount of elements that do something is usually just to calculate the probability of an element doing this and multiply it with the amount of elements.

But how big is the probability for a row, say the first, to be dropped? As I understand the question, a row is dropped if

• It has more than 1 one. (rows with only one 1 never get dropped)
• and it has a 1 in a column where a 1-one-row also has one.

Both of these events are strongly affected by the amount of 1 the row has, so let's condition on this amount being $k$. If a row has $k$ ones and $k≥2$, then it gets dropped when some of the $m-1$ other rows has only one 1, and this 1 is in some of the $k$ rows.

The probability of having only one 1 at a fixed place is $qp^{n-1}$ and so the probability of having it on one of $k$ places is $kqp^{n-1}$. The probability of this not happening is thus $$1-kqp^{n-1}.$$ The rows are independent, so the probability of there being no row that drops our row is $$ \bigl(1-kqp^{n-1}\bigr)^{m-1} $$ and the probability that our row is dropped is thus 1 minus the term above: $$ P(\text{Row 1 gets dropped}\mid \text{Row 1 has $k$ ones}) = 1-\bigl(1-kqp^{n-1}\bigr)^{m-1} $$ This k, amount of ones in our first row is, again, $B(n,q)$-distributed, so by the law of total probability \begin{align} P(\text{Row 1 gets dropped}) &= \sum_{k=2}^n P(\text{Row 1 gets dropped}\mid \text{Row 1 has $k$ ones})P(\text{Row 1 has $k$ ones}) \\ &= \sum_{k=2}^n \bigl(1-\bigl(1-kqp^{n-1}\bigr)^{m-1}\bigr)\binom nk q^kp^{n-k}. \end{align} The expected amount of dropped rows is then $$ mP(\text{Row 1 gets dropped}) = m\sum_{k=2}^n \bigl(1-\bigl(1-kqp^{n-1}\bigr)^{m-1}\bigr)\binom nk q^kp^{n-k}. $$ I see no obvious way to simplify this sum.

Answer 3

For the first question, all possible states are:

100...0
010...0
.......
000...1

So ${n}\choose{1}$$q.p^{n-1}$ will represent probability that a row contain only one bit $1$. Because we expect $n-1$ bit0's and $1$ bit1. And this can happen in ${n}\choose{1}$ different ways. See Binomial Distribution Wikipage for more information.

For the second question, you actually want expected value of containing one bit $1$ with respect to all rows. The probability of containing 1 bit is equal for all rows. This is called uniform distribution. Call this random variable as $R$. Simply multiplying by $m$ gives us the average number of rows that contain only one bit $1$.

$E[R]=$ $m$${n}\choose{1}$ $q.p^{n-1}$

Answer 4

Per the OP's request, below is Python code that I used to simulate question #3, the results of which agree with the (revised) answer of @Dodezw, i.e.,$$\mathbb{E}(N)= m\sum_{k=2}^n \bigl(1-\bigl(1-k\,q\,p^{n-1}\bigr)^{m-1}\bigr)\binom nk\,q^kp^{n-k}.$$

Here are contour plots of the above function, for $q=1/2$ and $q=1/3$, for $2\le m\le 100$ and $2\le n\le 20$. Each curve interpolates $(m,n)$-values for which $\mathbb{E}(N)$ approximates the labelled constant:

Numerical observations:

1. For all $q\in(0,1)$ and all $n\ge 1$, $f(m,n,q):=\mathbb{E}(N)$ is a strictly increasing function of $m$.
2. For all $q\in(0,1)$ and all $m\ge 2$, as $n$ increases, $f(m,n,q)$ first increases to a maximum, then decreases toward $0$: i.e., there exists $n^*$, such that $f(m,n^*,q)=\max_{n}f(m,n,q).\ $ (NB: $n^*(m,q)$ is the dotted line shown in each plot above, forming a "ridge line" along the top of the "hill" we're "viewing from above" in each of these plots.)
3. For $q=1/2$ and for $m$ up to $4$, Wolfram Alpha symbolically computes that $$\mathbb{E}(N)= m\,(m+1)\,n\,2^{-(n+1)}(1+\mathcal{O}(n\,2^{-(n+1)})) $$ which suggests the approximate formula $$f(m,n,1/2) \approx g(m,n):=m\,(m+1)\,n\,2^{-(n+1)} $$ for some range of $(m,n)$-values. The following plot shows error contours, such that for all points $(m,n)$ above a given labelled contour, $|g(m,n)-f(m,n,1/2)|$ is less than the label-value:

---

Python code for simulating question #3:

import math
import random

def get_M(m, n, q):
    """returns m x n matrix M with elements i.i.d Bernoulli(q), q=P(bit=1)"""
    M = []
    for i in range(m):
        row = [(1 if random.random()<q else 0) for j in range(n)]
        M += [row]
    return M

def trial(m, n, q):
    """return the number of dropped rows in one sample of M(m, n, q)"""
    M = get_M(m, n, q)
    indrows = []   # accumulates "indicator" rows (i.e. which rows have exactly one 1)
    indcols = []   # accumulates "indicator" cols (i.e. which cols have the 1 in the indicator rows)
    for i in range(m):       # for all rows ...
        if M[i].count(1)==1:     # if there's exactly one 1 in the row ...
            indrows += [i]                # accum. that row#
            indcols += [M[i].index(1)]    # accum. the index of the 1 in that row
    count = 0
    for i in range(m):           # for all rows ...
        if (i not in indrows):       # if the row does not contain exactly one 1 ...
            for j in range(n):       # then check each element in that row
                if M[i][j]==1 and j in indcols:   # if element==1 in an "indicator" column 
                    count += 1                    # then that row counts as dropped
                    break            # go on to the next row
    return count

def EN(m, n, q):  #q = P(bit=1)
    """return E(N) computed from the posted formula"""
    p = 1 - q
    return m*sum([(1-(1-k*q*p**(n-1))**(m-1))*math.comb(n,k)*q**k*p**(n-k) for k in range(2, n+1)])

def est_EN(nsamp, m, n, q): 
    """return (mean, sd) such that mean +- 3*sd is an approx 99% CI for E(N), using nsamp simulated random samples
    NB: this is generic code implementing a 'running' mean & variance algorithm"""
    mean = ssd = 0
    for i in range(1, nsamp+1):
        z = trial(m, n, q)
        dev = z - mean
        mean += dev/i
        ssd += dev*(z - mean)
    sd = math.sqrt(ssd/(nsamp-1)/nsamp)
    return mean, sd

Example:

m, n, q = 3, 2, .5
print(f"{(m, n, q)=}, {nsamp=}")

formula_EN = EN(m, n, q)
print(f"  {formula_EN = :.6f}")

nsamp = 10**8
(mean, sd) = est_EN(nsamp, m, n, q)
print(f"simulated_EN = {mean:.6f} +- {3*sd:.6f}")

Output for this example:

(m, n, q)=(3, 2, 0.5), nsamp=100000000
  formula_EN = 0.562500
simulated_EN = 0.562553 +- 0.000198

Wall time: 4min 52s