$N$ nodes are uniformly distributed in a square whose side length is $1$.
There exists an undirected edge between two nodes, if and only if the distance between them is less than or equal to $r$.
Here we set a source $s$ and a destination $t$ in this square, and the distance between them is $d$.
Now I want to find a shortest path from $s$ to $t$, that is, more precisely, the expectation of the path length from $s$ to $t$.
Note that $r=\Theta\left(\sqrt{\frac{\log N}{N}}\right)$, and it can ensure that the graph is connected.
$d$ might be a constant or a variable.
Intuitively, the expectation of path length is $O(d)$.
I refer to many papers, Continuous Time Markov Chain is proposed to solve it. But they are aimed at the complete graph which does not apply to this case. Would you please provide me some idea to solve this problem ? Thank you!
2026-03-25 11:12:15.1774437135
Shortest path length when edge length is limited
89 Views Asked by Bumbble Comm https://math.techqa.club/user/bumbble-comm/detail AtRelated Questions in PROBABILITY-THEORY
- Is this a commonly known paradox?
- What's $P(A_1\cap A_2\cap A_3\cap A_4) $?
- Another application of the Central Limit Theorem
- proving Kochen-Stone lemma...
- Is there a contradiction in coin toss of expected / actual results?
- Sample each point with flipping coin, what is the average?
- Random variables coincide
- Reference request for a lemma on the expected value of Hermitian polynomials of Gaussian random variables.
- Determine the marginal distributions of $(T_1, T_2)$
- Convergence in distribution of a discretized random variable and generated sigma-algebras
Related Questions in RANDOM-GRAPHS
- Bound degrees of sparse random graphs
- Connectivity of random graphs - proof $\frac{logn}{n}$ is threshold
- In weighed random graph where the edge weight is restricted to $[0,1]$, what are the usual assumptions of edge weight distribution?
- Upper Bound on Vertices in SCC Graph of Directed Random Graph
- The degree of a vertex in $G(n,m)$ is approx. Poisson
- What is the expected length of the diameter of a special random graph?
- Clique numbers and Theorem 4.5.1 in "The Probabilistic Method" by Alon and Spencer
- Expected global clustering coefficient for Erdős–Rényi graph
- Probability of having a path of a given length in a random graph?
- Correlation for random graph (Erdos-Renyi)
Related Questions in GEOMETRIC-PROBABILITY
- planar Poisson line process & angles of inclination
- Probability that a triangle inscribed in an ellipse contains one of its foci
- Expected number of disks to fill square
- Size of $X\setminus g(X)$ for $g(x)$ the closest $y$ to $x$ with $X_k\sim Unif(A)$
- Geometric Probability - a circle within a circle
- Hidden variables in probability
- Solutions to Bertrand's Paradox in J. Neyman's Confidence Interval Paper
- Measuring a non-measurable set with probability?
- On the 1/2 assumption on concentration of measure on continuous cube
- Probability that a random triangle with vertices on a circle contains an arbitrary point inside said circle
Related Questions in PROBABILISTIC-METHOD
- Proof by probabilistic method for coins on chessboard puzzle
- Proving lower bound of row/column occurencies of numbers in 2D n-element grid
- Translating an Arithmetic Progression in $\mathbf Z/p\mathbf Z^*$, how much Overlap is Possible?
- Clique numbers and Theorem 4.5.1 in "The Probabilistic Method" by Alon and Spencer
- $\frac{N}{n}$; probability
- Why a randomly chosen element of a class satisfying property `p`, implies existence of an element of said class that satisfies `p`?
- Expected number of hamiltonian paths in a tournament
- Finding threshold for Erdos-Renyi random graph to be connected using branching process
- Theorem of Hardy & Ramanujan - second moment Method
- Deviating from the mean +-1 variables
Trending Questions
- Induction on the number of equations
- How to convince a math teacher of this simple and obvious fact?
- Find $E[XY|Y+Z=1 ]$
- Refuting the Anti-Cantor Cranks
- What are imaginary numbers?
- Determine the adjoint of $\tilde Q(x)$ for $\tilde Q(x)u:=(Qu)(x)$ where $Q:U→L^2(Ω,ℝ^d$ is a Hilbert-Schmidt operator and $U$ is a Hilbert space
- Why does this innovative method of subtraction from a third grader always work?
- How do we know that the number $1$ is not equal to the number $-1$?
- What are the Implications of having VΩ as a model for a theory?
- Defining a Galois Field based on primitive element versus polynomial?
- Can't find the relationship between two columns of numbers. Please Help
- Is computer science a branch of mathematics?
- Is there a bijection of $\mathbb{R}^n$ with itself such that the forward map is connected but the inverse is not?
- Identification of a quadrilateral as a trapezoid, rectangle, or square
- Generator of inertia group in function field extension
Popular # Hahtags
second-order-logic
numerical-methods
puzzle
logic
probability
number-theory
winding-number
real-analysis
integration
calculus
complex-analysis
sequences-and-series
proof-writing
set-theory
functions
homotopy-theory
elementary-number-theory
ordinary-differential-equations
circles
derivatives
game-theory
definite-integrals
elementary-set-theory
limits
multivariable-calculus
geometry
algebraic-number-theory
proof-verification
partial-derivative
algebra-precalculus
Popular Questions
- What is the integral of 1/x?
- How many squares actually ARE in this picture? Is this a trick question with no right answer?
- Is a matrix multiplied with its transpose something special?
- What is the difference between independent and mutually exclusive events?
- Visually stunning math concepts which are easy to explain
- taylor series of $\ln(1+x)$?
- How to tell if a set of vectors spans a space?
- Calculus question taking derivative to find horizontal tangent line
- How to determine if a function is one-to-one?
- Determine if vectors are linearly independent
- What does it mean to have a determinant equal to zero?
- Is this Batman equation for real?
- How to find perpendicular vector to another vector?
- How to find mean and median from histogram
- How many sides does a circle have?