Given a probability $p$, what is the upper bound of how many columns in a row-stochastic matrix exceed $p$?

Question

Given a probability $p$ and a row $i$ of a stochastic matrix $M$, what is the maximum number of columns $j$ such that $M_{ij} \gt p$?

   void columnsGreaterThan(double prob, int state, int& columns[]) {
      ArrayResize(columns, stateCount());
      int count = 0;
      for (int j=0; j < stateCount(); j++)
      {
         if (probMatrix[state][j] > prob)
            columns[count ++] = j;
      }
      ArrayResize(columns, count);     
   }

This function gets called a lot and is part of a MarkovModel class. I want to return all columns that exceed probability prob.

Is there a simple formula for computing that?

As it is now, my code will always allocate numStates() in the columns array, which seems like way overkill for a large matrix, especially when I'm starting with $p = 0.7$.

---

Let $M_{ij}$ be an $m \times m$ matrix. If all $M_{ij}$ are the same, then $f(p)$, the formula should be $f(1/m) = m$.

I would guess $f(p) = \lceil 1/p \rceil$

Answer 1

I think the answer is $f(p) = \lfloor 1/p \rfloor$. Firstly, given $p$ there can be at least up to that many entries since you can have $\sum_{j=1}^{\lfloor 1/p \rfloor} p + \sum_{j= \lfloor 1/p \rfloor + 1}^m M_{ij} = 1$ where $M$ is an $m\times m$ matrix. This is true since $\lfloor 1/p \rfloor p \leq 1/p \cdot p = 1$. And $f(p)$ can't be any larger otherwise $p$ would further divide $1$.