User pradipta - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T12:01:14Z http://mathoverflow.net/feeds/user/5873 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/119744/completion-time-of-a-process-on-a-tree Completion time of a process on a tree Pradipta 2013-01-24T11:02:16Z 2013-01-26T23:21:55Z <p>Given is a constant degree rooted tree of depth $D$. It is also known that the total number of nodes in the tree is at most $D^2$. There is a probabilistic process with discrete time steps on the nodes that work as follows:</p> <ol> <li>A node becomes <b>eligible</b> to participate in the process when all of its children have <b>succeded</b>.</li> <li>Once eligible, the node <b>succeeds</b> in each time step with iid probably $\frac12$. Once successful, it is "done", i.e. stays succeeded.</li> </ol> <p>I would like a bound on how many steps it requires for all nodes to succeed with probability $1 - \delta$ where $\delta$ is potentially much smaller than $\frac1{D^2}$. </p> <p>I can see a bound of $O((D + \log{\frac{1}{\delta}})\log D)$ as outlined below. I was wondering if the $\log D$ is necessary?</p> <p>Outline of argument for $O((D + \log{\frac{1}{\delta}})\log D)$: Consider to be the number of steps required for the depth of tree of unsuccessful nodes to reduce by 1. Since there are at most $D^2$ leaves at any given time, the expected time for this reduction is $\log D$ steps. The situations for different depths are essentially independent (can be written as martingale), and then a concentration inequality would give us the required bound.</p> http://mathoverflow.net/questions/107202/minimum-spanning-tree-of-a-random-graph Minimum spanning tree of a random graph Pradipta 2012-09-14T17:55:51Z 2012-09-15T00:39:04Z <p>Consider $n$ points arbitrarily located on the plane. Consider a random graph $G$ drawn from $G(n, \frac12)$ on these points (i.e. the Erdos-Renyi random graph where every edge is selected with probability $\frac12$). </p> <p>What is known about the geometry of the minimum spanning tree of such a graph? I am interested in pointers to <b>any</b> literature on this, but something like the following might be a concrete example:</p> <blockquote> <b>Thm.</b> With high probability, the Minimum Spanning Tree has weight within a factor of $\alpha$ of the MST on the complete graph on the same points. </blockquote> http://mathoverflow.net/questions/86844/lower-bound-on-sum-of-independent-random-variables Lower bound on sum of independent random variables Pradipta 2012-01-27T17:44:40Z 2012-01-27T17:51:29Z <p>Assume $0 &lt; a_i \leq 1$ for $i = 1, 2 \ldots n$. I am interested in the random sum $X = \sum_i a_i X_i$ where $X_i$ are iid random Bernoulli variables with some mean $p \in (0, 0.5)$. I would like to know if one can relate $P(X \leq 1)$ to $P(X \leq \delta)$ for some $\delta &lt; 1$. Specifically, what are the tightest bounds of the form</p> <p>$$P(X \leq \delta) \geq f(\delta) P(X \leq 1)$$</p> <p>for some function $f(\delta)$?</p> http://mathoverflow.net/questions/55625/coin-flipping-and-a-recurrence-relation Coin flipping and a recurrence relation Pradipta 2011-02-16T15:16:28Z 2011-12-20T11:43:00Z <p>How can one solve the following recurrence relation?</p> <p>$f(n) = 1 + \frac{1}{2^n} \sum_{k = 0}^n {{n}\choose{k}} f(k)$</p> <p>$f(0) = 0$</p> <p>As it happens, I can show $f(n) = \Theta(\log n)$ through other means (see below). But I'd like to know how to solve the recurrence "directly".</p> <p>The recurrence relation comes from the following coin flipping problem. There are $n$ independent, unbiased coins, and we toss all of then for a number of rounds. Let $T(n)$ be the first round when each coin has got head at least once (ie, $T(n) = \text{arg} \min_t \text{s.t.} H_t(i) \geq 1; \forall i \in [n]$, where $H_t(i)$ is the number of heads the $i^{th}$ coin has got in the first $t$ rounds). Then one can see that $E(T(n))$ fulfills the recurrence relation mentioned above.</p> <p>To see that $E(T(n)) = O(\log n)$, note that we reduce the number of coins who haven't gotten head yet by a factor of 2, in expectation. The $\log n$ bound follows routinely from that. On the other direction (ie, $E(T(n)) = \Omega(\log n)$), let $S = \log n/20$. Then at time $S$ with high probability, a large number of coins will still be "headless", from which the lower bound follows.</p> http://mathoverflow.net/questions/82324/comparing-two-markov-chains Comparing two Markov chains Pradipta 2011-11-30T23:18:01Z 2011-11-30T23:18:01Z <p>I thought that this question is more appropriate for math.stackexchange, <a href="http://math.stackexchange.com/questions/86052/comparing-two-markov-chains" rel="nofollow">where I asked it</a>, but seeing how I got no response, here it goes:</p> <p>I am interested in the question of the positive recurrence of a Markov chain that "converges" to another Markov chain known to be positive recurrent. The following is, in the context of queueing theory, a concrete example of what I mean.</p> <p>Consider a system where a single server is serving two clients. Time is slotted. For client $i \in \{1, 2\}$, the number of packets arriving in each time step is a iid Bernoulli random variable with probability $p_i$.</p> <p>Each client has queues of infinite capacity.</p> <p>Assume $p_1 + p_2 &lt; \frac{1}{8}$.</p> <p>At each time slot, a client with non-empty queue may choose to submit one packet to the server for processing. This packet will be processed and leave the relevant queue if and only if the other client did not submit a packet in that time slot.</p> <p>Now consider the following simple algorithm. Assume that client $i$ knows $p_i$. Then at each time slot, client $i$ (if its queue is non-empty) will submit a packet to the server with iid probability $2 p_i$. Let $j$ be the other client.</p> <p>The probability of a packet submitted by client $i$ being processed is at least $1 - 2 \cdot p_j > \frac{3}{4}$. Thus, the probability of the size of a non-empty queue at client $i$ reducing by $1$ is at least $2 \cdot p_i \times \frac{3}{4} > p_i$. Since the departure process has a higher rate than the arrival process, it is clear that the corresponding Markov chain is positive recurrent and the queues are stable.</p> <p>Here comes my question. Assume the clients do not know their own $p_i$'s. Naturally, they could approximate it as follows: at time $T$, the approximation $\hat p_i(T)$ is defined by $\hat{p_i}(T) =$$\min \left\{ 1, \frac{A(T)}{T} \right\}$, where $A(T)$ is the number of packets that have arrived up to time $T$. The clients can now use $\hat p_i(T)$ instead of $p_i$ in the above algorithm. </p> <p>It seems to me that since $\hat p_i(T)$ converges almost surely to $p_i$, the resulting Markov chain will be positive recurrent too. But I am not sure this simply can be stated as true, and/or how to show that this holds. </p> <p>Thanks.</p> http://mathoverflow.net/questions/49532/partitioning-a-matrix-with-bounded-row-sums Partitioning a matrix with bounded row sums Pradipta 2010-12-15T14:30:50Z 2011-03-02T00:00:19Z <p>Let $A$ be a $n \times n$ matrix with non-negative entries $a_{ij}$, where $a_{ij}$ is the entry in the $i^{th}$ row and $j^{th}$ column. Assume $\sum_{1 \leq j \leq n} a_{ij} \leq 1$ for all $1 \leq i \leq n$. Also assume $a_{ii} = 0$ for all $1 \leq i \leq n$. </p> <p>I want to partition the index set <code>$I = \{1, 2 \ldots n\}$</code> into minimum number of sets $I_1, I_2, \ldots I_t$ so that the column sum is bounded by $1$ in each sub-matrix defined by the sets, or more formally:</p> <ol> <li>$\cup_{1 \leq k \leq t} I_k = I$</li> <li>For all $1 \leq k \leq t$, $\sum_{i \in I_k}a_{ij} \leq 1$ for all $j \in I_k$</li> <li>The number $t$ is minimized</li> </ol> <p>I can construct examples where $t$ has to be at least $2$, on the other hand, $t = \Theta(\log n)$ would suffice for all such matrices. I am wondering if a tighter bound exists.</p> <p>Motivation: this is a sort of generalization of the coloring problem in bounded out-degree digraphs. If a di-graph has out-degree upper bounded by $k$ it can be colored with $k + 1$ colors.</p> http://mathoverflow.net/questions/53454/maximum-of-a-set-of-sums-of-iid-random-variables Maximum of a set of sums of iid random variables Pradipta 2011-01-27T05:43:28Z 2011-01-28T21:26:25Z <p>Consider some probability distribution $D$ over non-negative reals with finite expectation $\mu$. Now for any positive $T$ consider sums of $T$ iid random variables drawn from $D$. A single sum of this sort would be $S(T) = \sum_{i = 1}^T x_i$ where each $x_i$ is a iid random sample from $D$.</p> <p>We will consider $n$ such sums $S_1(T), S_2(T) \ldots S_n(T)$.</p> <p>My question: Is it true that for any distribution $D$ and any finite positive $n$, there exists a finite positive $T$ (which may be a function of $n$ and $D$) such that $E(\max_{1 \leq j \leq n}S_j(T)) \leq 2 T \mu$?</p> <p>This is true for, say, Bernoulli random variables, but I'd like to know the mildest condition under which a statement like this can be made. For example, is it true for all distributions with finite $4^{th}$ moments?</p> http://mathoverflow.net/questions/49532/partitioning-a-matrix-with-bounded-row-sums/49657#49657 Answer by Pradipta for Partitioning a matrix with bounded row sums Pradipta 2010-12-16T15:58:01Z 2010-12-16T16:14:35Z <p>Ok, I think there are examples where $\Omega(\log n)$ colors are needed. </p> <p>Here’s an example, let $a_{ij} = \frac{1}{i}$ for $j &lt; i$ and $a_{ij} = \frac{1}{j^2}$ for $j > i$. Then $\sum_{j} a_{ij} = \frac{i-1}{i} + \sum_{j > i} \frac{1}{j^2} = O(1)$. Of course, the bound is $O(1)$ instead of $1$, but that can be normalized and all that. </p> <p>However, note that $\sum_j a_{j1} = \Omega(\log n)$ and if we only have $o(\log n)$ partitions, this sum cannot be "distributed" into small enough parts.</p> http://mathoverflow.net/questions/45683/stability-of-discrete-queue-new-twist Stability of discrete queue (new twist) Pradipta 2010-11-11T11:35:46Z 2010-11-12T15:52:18Z <p>Hi, I am new to queueing theory. I am interested in a question that I feel should be fairly basic, yet I haven’t really found a clear solution to it. Hopefully somebody here can help me.</p> <p>We have a single server system, with an infinite queue, and with slotted time. At the beginning of every slot, a number of jobs arrive in the queue. The number of jobs $X$ is a random variable over the non-negative integers, with expectation $\mu$. After these jobs arrive, the server processes some jobs, which leave the queue. The number of jobs the server can process is a Bernoulli random variable $C$. That is, $C = 1$ with some probability $p$, and $0$ otherwise. To state what is probably obvious, if $C = 1$, the queue size is reduced by $1$ (if the queue was non-empty), and the queue remains unchanged if $C= 0$ or if the queue was empty. Both $C$ and $X$ are iid across time.</p> <p>I want to understand the conditions under which this system is stable. By stable, I mean $\sup_{n \geq 1} E(Q(n)) &lt; M$ for some finite $M$, where $Q(n)$ is the size of the queue at the beginning of time slot $n$, and $E(Q(n))$ is the expectation of $Q(n)$. I am not necessarily interested in a explicit value of $M$, just knowledge that it is finite is fine. I am hoping that the condition would be $\mu &lt; p$ or something like that.</p> <p>I realize that probably some sort of assumption on the distribution on $X$ is needed, which is fine. Assumptions like finite variance, strong law of large numbers, or even large deviation inequalities are OK with me.</p> <p><strong>Edit:</strong> Additionally, I am interested in what would happen if $E(C)$ was not a fixed $p$ but $p(t)$ (ie, a function of time). Here $p(t)$ itself is a random variable where $E(p(t)) = p$ for all $t$, and $p(t)$ converges to $p$ almost surely. This question appears to be related to "time dependent Markov chains". However, the references for time dependent Markov chains that I could find do not consider $p(t)$ to be a random variable it self (such as <a href="http://portal.acm.org/citation.cfm?id=990738.990783" rel="nofollow">http://portal.acm.org/citation.cfm?id=990738.990783</a>). Asmussen’s book talks about time dependent properties of Markov chains, but that appears to be quite different.</p> http://mathoverflow.net/questions/119744/completion-time-of-a-process-on-a-tree/119790#119790 Comment by Pradipta Pradipta 2013-01-28T16:40:16Z 2013-01-28T16:40:16Z actually the tree cannot consist D disjoint paths of length D from the root since it is constant degree tree (assuming D is larger). I wonder if that improves the running time further. http://mathoverflow.net/questions/119744/completion-time-of-a-process-on-a-tree/119790#119790 Comment by Pradipta Pradipta 2013-01-26T12:55:01Z 2013-01-26T12:55:01Z sounds perfect! let me just ruminate on this for a bit more, and I'll accept the answer. Thanks! http://mathoverflow.net/questions/107202/minimum-spanning-tree-of-a-random-graph Comment by Pradipta Pradipta 2012-09-16T03:29:52Z 2012-09-16T03:29:52Z Thanks for the pointers! They seem to be only slightly different models (randomly placed points etc), but I will definitely take a look. http://mathoverflow.net/questions/49532/partitioning-a-matrix-with-bounded-row-sums Comment by Pradipta Pradipta 2011-03-02T00:00:02Z 2011-03-02T00:00:02Z You’re right...I must have been not thinking. http://mathoverflow.net/questions/55625/coin-flipping-and-a-recurrence-relation Comment by Pradipta Pradipta 2011-02-18T14:47:05Z 2011-02-18T14:47:05Z That’s great to know, Mike. http://mathoverflow.net/questions/55625/coin-flipping-and-a-recurrence-relation/55636#55636 Comment by Pradipta Pradipta 2011-02-17T16:50:42Z 2011-02-17T16:50:42Z Thanks. Great answer. http://mathoverflow.net/questions/55625/coin-flipping-and-a-recurrence-relation Comment by Pradipta Pradipta 2011-02-17T16:02:36Z 2011-02-17T16:02:36Z Yes, I tried that. Didn't get anywhere. http://mathoverflow.net/questions/55625/coin-flipping-and-a-recurrence-relation/55667#55667 Comment by Pradipta Pradipta 2011-02-17T15:37:43Z 2011-02-17T15:37:43Z Very useful comment, Mike. http://mathoverflow.net/questions/54820/physics-and-churchturing-thesis/54886#54886 Comment by Pradipta Pradipta 2011-02-16T16:28:18Z 2011-02-16T16:28:18Z Why does &quot;quantum computation shatters complexity theory&quot;? I thought, for example, that it wasn't known in quantum computation makes NP-hard problems easier. http://mathoverflow.net/questions/55625/coin-flipping-and-a-recurrence-relation Comment by Pradipta Pradipta 2011-02-16T15:33:00Z 2011-02-16T15:33:00Z yeah. with probability $\frac{1}{2^n}$ no coin succeeds in round 1, thus you are back where you started. http://mathoverflow.net/questions/55625/coin-flipping-and-a-recurrence-relation Comment by Pradipta Pradipta 2011-02-16T15:24:57Z 2011-02-16T15:24:57Z I think its working now. http://mathoverflow.net/questions/55625/coin-flipping-and-a-recurrence-relation Comment by Pradipta Pradipta 2011-02-16T15:18:01Z 2011-02-16T15:18:01Z something's wrong. I'll fix this. http://mathoverflow.net/questions/15238/how-to-estimate-the-growth-of-a-recurrence-sequence Comment by Pradipta Pradipta 2011-02-10T00:36:00Z 2011-02-10T00:36:00Z Isn't this the recurrence relation for Bell Numbers? http://mathoverflow.net/questions/53454/maximum-of-a-set-of-sums-of-iid-random-variables/53482#53482 Comment by Pradipta Pradipta 2011-01-28T16:11:28Z 2011-01-28T16:11:28Z Very nice. I'm curious about the quantitative bound as well, as it appears to mean that $T$ polynomial in $n$ suffices, which is really great. http://mathoverflow.net/questions/53454/maximum-of-a-set-of-sums-of-iid-random-variables/53518#53518 Comment by Pradipta Pradipta 2011-01-27T21:03:57Z 2011-01-27T21:03:57Z Guys, many many thanks. I'll read through these detailed answers and then respond. Thanks again :)