2
votes
1answer
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 ...
0
votes
1answer
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 ...
0
votes
0answers
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 ...
0
votes
1answer
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. ...
2
votes
2answers
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 ...
1
vote
0answers
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$), ...
1
vote
2answers
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 ...
2
votes
1answer
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 ...
2
votes
1answer
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$, ...
2
votes
1answer
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$. ...
1
vote
0answers
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 ...
1
vote
0answers
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 ...
1
vote
1answer
49 views

Probabilistic Polynomial Time - arbitrary probability barrier?

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$ ...
11
votes
3answers
300 views

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$ ...