# Tagged Questions

33 views

### Expected Value on code

I'm trying to figure out the expected number of times this algorithm will print. I'm stuck on how to go about doing so. I used an indicator variable to keep track of the number of print statements ...
54 views

### What is the probability the best case occurs? (Comp Sci Type Question)

I'm having trouble figuring out what's the probability the best case occurs? It's my first time bringing together probabilistic knowledge into computer science. The question goes as such. Consider ...
37 views

### Analysis of the successive elimination algorithm for multi-armed bandits

I'm referring to page 7 (page 11 if you look at printed page numbers) of http://moodle.technion.ac.il/pluginfile.php/328871/mod_resource/content/1/Chapter1_bandits.pdf Here's what he claims, and I'm ...
99 views

### Expected running time

Suppose A = A[1] . . .A[n] of length n (where A[i] is either 0 or 1). We want to determine if at least half the elements in A are 1’s. ...
106 views

### Computation of the mean of a random variable to estimate algorithm complexity

I made an incremental algorithm which I would like to evaluate the complexity. The algorithm works with a sliding window of size n. To study the complexity, the window is considered full and the data ...
23 views

### How did we arrive at this form of Markov's Inequality in this proof?

In the book I am reading (complexity and cryptography by Talbot and Welsh, chapter 4), there is a proposition on $\textbf{ZPP}$($\textbf{ZPP} = \textbf{RP} \cap \textbf{coRP}$-proposition $4.13$), ...
47 views

### Problem understanding a proof

In the book I am reading (complexity and cryptography by Talbot and Welsh, chapter 4), there's this example: Choosing an integer $a \in_R \{0,\dots,n\}$ using random bits. We assume that we ...
41 views

### “Certificate” in the context of computational complexity

I can't find any definition for the word either in the book I am reading or online. What exactly does certificate mean in the context of computational complexity? For instance: [...]The above ...
319 views

### Proving that a function is negligible

In mathematics, a negligible function is a function $\mu(x):\mathbb{N}{\rightarrow}\mathbb{R}$ such that for every positive integer $c$ there exists an integer $N_c$ such that for all $x > N_c$, ...
61 views

### How big is $Z_n^*$?

I would like to find some upper bound on $\frac{n}{|Z_n^*|}$ i.e. to show that many of the elements in $Z_n$ are also in $Z_n^*$. I want to show that $\frac{n}{|Z_n^*|}=O(log^cn)$ for some $c \in N$. ...
74 views

### Maximum Independent Set on Path and Ring

I known this question is more appropriate to cs.stackexchange.com, nevertheless I want to ask it in Mathematics part because for solving the following problem strong understanding of probabilistic ...
86 views

### Solving a non-linear inequality related to geometric Brownian motion

Consider the non linear inequality $$\sum_{i=1}^{n}a_{i}u^{\sum\limits_{j=1}^{i}y_j} > c$$ $$y_j \in \{0,1\}, j=1,2,\dots,n$$ $$a_i \in \mathbb{R}, i=1,2,\dots,n$$ n \in \mathbb{N}, u>0, c ...
Let's define $PP_c$ as a set of languages: A language $L$ is in $PP_c$ iff there exists a polynomial $p: \mathbb{N} \rightarrow \mathbb{N}$ and a polynomial time turing machine $P$ s.t. if $x \in L$ ...
### Efficient computation of $E\left[\frac{1}{1+\sum_iX_i}\right]$ where $X_i$ is RV with Bernoulli distribution with different probabilities
Suppose we have the random variables $X_1, \ldots, X_n$ that have Bernoulli distributions with the (possibly different) probabilities $p_1, \ldots, p_n$. For example, $X_1$ = 1 with probability $p_1$ ...