Tag Info

Accepted

• 223
Accepted

Probability of two vertices being connected by some path in a random directed graph

Consider a BFS exploration process, which proceeds in $k$ stages. Put $V_0 = \{u\}$. Given $V_0,\ldots,V_i$, explore all edges from $V_i$ to $V \setminus \bigcup_{j=0}^i V_j$ (where $V$ is the set of ...
• 14.1k

Upper bound to number of closed itemsets

The bound is $2^{\min(n, m)}$. It is an upper bound because no two "formal concepts" (i.e., closed itemsets with their respective transaction sets) can have the same subset of items or the same subset ...

computing maximal bit density over a FSM

The supremum bit density will either be achieved by a finite word $v$ in the language, or by the limiting bit density of some sequence $u v w, u v^2 w, u v^3 w, \ldots$ of words in the language, which ...
Accepted

• 427
1 vote

Probability of random variable $X$ less than $max(Y_i)$

We have $\Pr[\max(Y_1,Y_2) \leq k] = \Pr[Pois(\lambda) \leq k]^2 = e^{-2\lambda}(\sum_{j=0}^k\frac{\lambda^j}{j!})^2$. Therefore, \$\Pr[X \geq \max(Y_1,Y_2)] = \sum_{k \in \mathbb N} \Pr[X = k] \cdot \...
• 1,897

Only top scored, non community-wiki answers of a minimum length are eligible